题目

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

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

示例 1：

1 2	输入：n = 16 输出：true

示例 2：

1 2	输入：n = 5 输出：false

示例 3：

1 2	输入：n = 1 输出：true

提示：

**进阶：**你能不使用循环或者递归来完成本题吗？

解题

在位运算章节中我们讲过，要想判断给定数 n 是否为 2 的正整数次幂，只需这样：

1
2
3

public static boolean isPowerOfTwo(int n){
    return n > 0 && (n & (n - 1)) == 0;
}

其中，位运算技巧n & (n - 1)可以直接将 n 二进制表示的最低位 1 移除。

现在，我们要来判断一个数n是否是 4 的幂次方。这该怎么算？

通过观察我们发现，如果n是 4 的幂，那么n的二进制表示中，1所在的位置一定是从低位开始的第偶数个二进制位上（注意，最低位规定是第0位）。

举例：

 4 = {100}
16 = {10000}
32 = {1000000}
...

因此，我们只需构造一个所有偶数二进制位都是0，奇数二进制位都是1的数字mask，然后将这个数字和n进行按位与运算。

如果结果是0，那么这个数n一定是 4 的幂次方（因为其二进制位中1出现的位置是偶数位）

1	mask = {10101010101010101010101010101010}2 = {AAAAAAAA}16

解题代码如下：

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