判断是否是4的幂

2021年5月31日2021年5月31日
算法
cxs

解题思路：
1. 先判断是否是2的幂，参考之前的代码
2. 然后两种解法：
  1. 如果n是4的次方的数，其二进制位表示中有且仅有1个1，这是由是否是2的幂得到的，其次1只出现在偶数位置，比如1的二进制就是1，1出现在第0位，4的二进制是100，1出现在第二位等等，因此可以构造一个32位数，1010101010…进行与运算，其所有偶数位置都为0，奇数位置都为1，这样进行与运算的时候，如果n是4的幂，其有一个偶数位置为1，奇数位置为0，结果==0。
  2. 4^x=(3+1)^x=1^x=1(mod)3，除以的余数一定为 $1$ ，如果n是2的幂，不是4的幂，其可以表示成4^x*2，其与3的模为2。
```
class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
};

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

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/power-of-four/solution/4de-mi-by-leetcode-solution-b3ya/
来源：力扣（LeetCode）
```

浏览量: 341

发表评论取消回复