Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
Example 1:
Input: 16
Output: true
Example 2:
Input: 5
Output: false
Follow up: Could you solve it without loops/recursion?
Credits:
Special thanks to @yukuairoy for adding this problem and creating all test cases.
这道题让我们判断一个数是否为4的次方数，那么最直接的方法就是不停的除以4，看最终结果是否为1，参见代码如下：
解法一：
class Solution {
public:
bool isPowerOfFour(int num) {
while (num && (num % 4 == 0)) {
num /= 4;
}
return num == 1;
}
};
还有一种方法是跟 Power of Three 中的解法三一样，使用换底公式来做，讲解请参见之前那篇博客：
解法二：
class Solution {
public:
bool isPowerOfFour(int num) {
return num > 0 && int(log10(num) / log10(4)) - log10(num) / log10(4) == 0;
}
};
下面这种方法是网上比较流行的一种解法，思路很巧妙，首先根据 Power of Two 中的解法二，我们知道 num & (num - 1) 可以用来判断一个数是否为2的次方数，更进一步说，就是二进制表示下，只有最高位是1，那么由于是2的次方数，不一定是4的次方数，比如8，所以我们还要其他的限定条件，我们仔细观察可以发现，4的次方数的最高位的1都是计数位，那么我们只需与上一个数 (0x55555555) <==> 1010101010101010101010101010101，如果得到的数还是其本身，则可以肯定其为4的次方数：``
解法三：
class Solution {
public:
bool isPowerOfFour(int num) {
return num > 0 && !(num & (num - 1)) && (num & 0x55555555) == num;
}
};
或者我们在确定其是2的次方数了之后，发现只要是4的次方数，减1之后可以被3整除，所以可以写出代码如下：
解法四：
class Solution {
public:
bool isPowerOfFour(int num) {
return num > 0 && !(num & (num - 1)) && (num - 1) % 3 == 0;
}
};
类似题目：
参考资料：
https://leetcode.com/problems/power-of-four/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
