2018-05-17 342. Power of Four

题意：给你一个数，判断该数是不是4的次幂（ check whether it is a power of 4）.
解题思路：是4的次幂的数依次是1,4,16,64,512...
转换成二进制就是
1:1
4:100
16:10000
64:1000000
512:100000000
所以满足4的次幂的数：首先得是正数，而且有且仅有一个二进制位为1，又由于4%3==1, （44）%3 = （（4%3）（4%3））%3= 1.即4n %3 = (4%3)n %3 =1.
需要注意的是操作符的优先级，位操作符（与或非亦或）优先级排在相等==操作符后面，所以位操作需要加括号。
时间复杂度：O(1)
空间复杂度：O(1)

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

或者不适用取余操作，直接对位进行操作

 public boolean isPowerOfFour(int num) {
        return num > 0 && (num&(num-1)) == 0 && (num & 0x55555555) != 0;
        //0x55555555 is to get rid of those power of 2 but not power of 4
        //so that the single 1 bit always appears at the odd position 
    }

0x55555555 is 1010101010101010101010101010101 in binary with a length of 32.仅有一位1并且落在这些相应的位上的数一定是4的次幂数。