LeetCode Power of Four 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的幂，之前那些通用方法还是可以用的。 首先4的幂肯定是2的幂，所以可以先用LeetCode Power of Two的方法判断是否为2的幂，如果是2的幂，进一步找4的幂和2的幂的差别。 首先，4的幂减1肯定能够被3整除，所以有下面的解法： [cpp] class Solution { public: bool isPowerOfFour(int n) { return (n > 0) && ((n & (n-1)) == 0) &&((n – 1) % 3 == 0); } }; [/cpp] 本代码提交AC，用时3MS。 其次，观察一下4的幂的二进制表示：

• 1:1
• 4:100
• 16:10000

从右往左数，其最高位1所在的位置都是奇数位，所以如果把4的幂num和$$0x55555555_2=1010101010101010101010101010101$$相与，得到的还是num本身，所以有下面的解法： [cpp] class Solution { public: bool isPowerOfFour(int n) { return (n > 0) && ((n & (n-1)) == 0) && ((n & 0x55555555) == n); } }; [/cpp] 本代码提交AC，用时3MS。 以上解法参考这个题解。]]>