LeetCode 342. Power of Four

Posted on | In |
Words count in article: 183 | Reading time ≈ 1

题目

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

1
2
Input: 16
Output: true

Example 2:

1
2
Input: 5
Output: false

Follow up: Could you solve it without loops/recursion?

思路

Same as in power of two, we can use bit manipulation to solve this problem.

  • If num is the power of 4, there is only one 1 bit in the binary expression

  • 1 bit must be at the bit standing for the power of 4, i.e. 4, 16, 64. Those bits occur every two bits –> their location is shown below:

10101010101010100

Thus it follows that the length of the binary expression is odd.

not num & (num - 1) is to check whether it only has one 1 bit;

len(bin(num)[2:]) & 1) is to check whether the length of the num’s binary expression is odd

代码

1
2
3
4
5
6
7
class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        return bool (num > 0 and not num & (num - 1) and (len(bin(num)[2:]) & 1))