一天一道LeetCode
本系列文章已全部上传至我的github，地址：ZeeCoder‘s Github
欢迎大家关注我的新浪微博，我的新浪微博
欢迎转载，转载请注明出处
（一）题目
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的n次方数。
解题思路：可以参考：【一天一道LeetCode】#326. Power of Three和【一天一道LeetCode】#231. Power of Two
首先，最简单的方法，采用循环来做：
class Solution {
public:
bool isPowerOfFour(int num) {
int n = num;
while(n>0&&n%4==0)
{
n/=4;
}
return n==1;
}
};题目中有提问说能不能不用循环和递归来做，和判断3的n次方数一样，4的n次方数在整形数内只有16个，很快就能列举出来，也不失为一个好办法。
另外观察4的n次方数和2的n次方数，可以看出，2的n次方数中能开方得到整数的均为4的n次方数。
class Solution {
public:
//三个条件：大于0，是2的n次方数，开方后得到整数
bool isPowerOfFour(int num) {
return (num>0)&&!(num&(num-1))&&(sqrt(num)*sqrt(num)==num);
}
};在leetcode的讨论区看到这样一个答案，很巧妙。
首先判断num是不是2的n次方数，在判断他与0xaaaaaaaa相与是否为0。
4的n次方数有一个特点就是，在bit位上，第0,2,4,6,8,10….位上为1,
所以，先判断是不是3的n次方数，就保证了有且仅有一位上为1的数，然后在剔除奇数位上为1的数，剩下的就是4的n次方数了。
class Solution {
public:
bool isPowerOfFour(int num) {
//三个条件：大于0，是2的n次方数，有且仅有偶数位上为1
return (num>0)&&!(num&(num-1))&&!(num&0xaaaaaaaa);
}
};