LeetCode342 Power of Four


描述

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

样例

1
2
3
4
Input:
16
Output:
true

思路

判断一个数是否是4的次幂。

做过这题LeetCode231 Power of Two的话,应该知道怎么判断一个数是否是2的次幂。

4次幂数显然满足2次幂数的性质,进一步观察发现,4次幂数二进制下“1”的位置只能在第0、2、…等偶数位。

因此,4次幂数如果和0x55555555相与的话,可以得到非零数,这就剔除了那些是2次幂数但不是4次幂数的数。

代码

1
2
3
4
5
6
class Solution {
public:
bool isPowerOfFour(int num) {
return num > 0 && !(num & (num-1)) && (num & 0x55555555);
}
};