位运算

---

题目详情

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4^x

---

示例1：

输入：n = 16
输出：true
1
2

示例2:

输入：n = 5
输出：false
1
2

示例3:

输入：n = 1
输出：true
1
2

思路:
当一个数字n是2的整数次方时:那么它的二进制一定是0...010...0这样的形式(只有一位是1)
n-1的二进制就是0...001...1 则可以得到: n & (n-1) == 0 ==> 这个数是2的整数次方
那么如果n也是4的整数次方呢?那么二进制中的1的位置一定得是奇数位(且只有这一个),例如0...01
0...100 0...10000 题目中n的范围是-2^31 <= n <= 2^31 - 1 即二进制的32位
所以我们可以利用10101...101(32位奇数位全为1偶数位全为0) 让n和它做与运算
结果如果不为0说明n的二进制中奇数位有一个1,即n是4的整数次方

我的代码：

class Solution 
{
public:
    bool isPowerOfFour(int n) 
    {
        //               n为2的整数次方   10101...101的十六进制表示
        return n > 0 && !(n & (n - 1)) && (n & 0x55555555); 
    }
};
1
2
3
4
5
6
7
8
9

位运算常用技巧