判断int是否为4的幂—— Leetcode(342)

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

Example:
Given num = 16, return true. Given num = 5, return false.

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

判断一个数是不是4的幂。还是使用二进制。
在判断2的幂的基础上添加条件。
如：16(10000)是，8(1000)不是；可以与0x55(01010101)取并集即可。(即判断1的位数是不是在奇数位)

class Solution {
public:
    bool isPowerOfFour(int n) {
        return n>0 && ((n & (n-1)) == 0) && (n & 0x55555555);
    }
};

另一种思路的解法为：

1	return n>0 && ((n & (n-1)) == 0) && (（(n-1) %3 == 0);

先直觉上检验一下，发现的确是这样：$4 -1 = 3,16 - 1 = 15, 64 -1 = 63$，都是3的倍数。因此$(4^n - 1) % 3 == 0$是成立的。

下面给出简短证明：
$$4^n -1 = 2^{2n}-1 = (2^n+1)(2^n-1)$$
我们知道：$2^n+1$、$2^n$与$2^n-1$是三个连续数，其中必有一个为3的倍数，而且$2^n$必然不是3的倍数，因此，$2^n+1$与$2^n-1$中必有一个为3的倍数。也就是$4^n -1$必为3的倍数。