4的幂

试题来源：力扣（英文），力扣（中文）

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

Input:n = 16
Output: true

Input:n = 8
Output: false    

问题分析：

前面我们讲过2的幂，这里来看下 4 的幂，4 的幂和 2 的幂一样，也是二进制中只有一个 1 ，但 4 的幂的二进制中 1 只在奇数位（从右边往左边数编号分别为 1,2,3,……）

1    的二进制：00000000 00000000 00000000 00000001 
4    的二进制：00000000 00000000 00000000 00000100 
16   的二进制：00000000 00000000 00000000 00010000 
64   的二进制：00000000 00000000 00000000 01000000 
256  的二进制：00000000 00000000 00000001 00000000 
1024 的二进制：00000000 00000000 00000100 00000000 

因为 4 的幂肯定也是 2 的幂，所以我们可以使用前面讲的2的幂，判断是否是 2 的幂，然后在进一步判断是否是 4 的幂。这里写法比较多，我们来看几个。

public boolean isPowerOfFour(int num) {
    return num > 0 && (num & (num - 1)) == 0 && (num & 0x55555555) != 0;
}

public boolean isPowerOfFour(int num) {
    return num > 0 && (num & (num - 1)) == 0 && (num & 0x55555555) == num;
}

public boolean isPowerOfFour(int num) {
    return num > 0 && ((num & (num - 1)) == 0) && (num & 0xaaaaaaaa) == 0;
}

public boolean isPowerOfFour(int num) {
    return num > 0 && (num == 1 || (num % 4 == 0 && isPowerOfFour(num / 4)));
}

如果看不明白，可以把上面的数字转化为二进制，通过和上面的数字进行 与运算 即可判断二进制中的 1 是在奇数位还是偶数位。

0x55555555 的二进制：01010101 01010101 01010101 01010101 
0xaaaaaaaa 的二进制：10101010 10101010 10101010 10101010 

我们来看一下 4 的幂次方的一些特点， 4 的幂次方不好观察，我们来研究一下 4 的幂次方减 1 ，研究这个特点之前一定要明白这样一条规律： 任何连续的 n 个自然数的乘积一定能被 n 整除。

所以我们判断一个数是 2 的幂次方之后，如果减去 1 还能被 3 整除，那么这个数一定是 4 的幂。

public boolean isPowerOfFour(int num) {
    return num > 0 && (num & (num - 1)) == 0 && (num - 1) % 3 == 0;
}

有没有一种可能就是一个数是 2 的幂，减去 1 还能被 3 整除，但它不是 4 的幂呢？其实是没有这种可能的，如果一个数是 2 的幂但不是 4 的幂，那么这个数一定是 2 的奇次幂，类似于 2^(2k+1) ，我们来证明一下。