[数据结构与算法]【C语言刷LeetCode】342. 4的幂（E）

【

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

示例 1：

输入：n = 16
输出：true
示例 2：

输入：n = 5
输出：false
示例 3：

输入：n = 1
输出：true
?

提示：

-231 <= n <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/power-of-four
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

】

这道题并不简单，首先好几个异常场景要判断，比如负数和1。

然后要知道x&（x-1）操作：

x = x&(x-1)表达式的作用：把x转化为2进制，看含有的1的个数
一般用来：
１)将最低的为1的位变成0。
２)当x为2的N次幂时,结果为0，这可以用来快速判断一个数是否为２的ｎ次方。

接着怎么判断4的幂，而不是2的幂：

4的幂一定是2的。
4的幂和2的幂一样，只会出现一位1。但是，4的1总是出现在奇数位。
0x5 = 0101b可以用来校验奇数位上的1。代码如下：

bool isPowerOfFour(int num){
    int cnt = 0;

    if (num < 0) return false; // 当负数的时候不满足

    if (num == 1) return true; // 4的0次幂，容易漏考虑

    if (num & 0xaaaaaaaa) return false;  // 奇数位上如果存在1，肯定不满足
    
    while (num) {
        num = num & (num - 1); // 核心部分
        cnt++;
    }
    
    if (cnt == 1)  {
        return true;
    }
    
    return false;
}

但是我没想到，4的幂一共也没多少个，直接查表就行了，这样看，说是简单题也合理。

[1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824, 4294967296]