如何用位运算判断一个数是不是 4 的幂？（LeetCode 342）

简化版

判断 4 的幂可以拆成三步：n > 0，n 必须是 2 的幂，即 (n & (n - 1)) == 0，并且唯一的 1 必须在偶数位。32 位整数中可以用掩码 0x55555555 保留偶数位：(n & 0x55555555) != 0。合起来就是 n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0。

详细版

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

4 的幂一定是 2 的幂，所以二进制中只有一个 1。
4^k = 2^(2k)，唯一的 1 只会出现在第 0、2、4、6 等偶数位。
0x55555555 的二进制是偶数位为 1、奇数位为 0，用它检查唯一的 1 是否落在偶数位。
也可以用 n % 3 == 1 区分 4 的幂和其他 2 的幂，但掩码法更能体现位运算考点。

完整版教学

一、4 的幂和 2 的幂是什么关系

4^k = (2^2)^k = 2^(2k)，所以 4 的幂一定也是 2 的幂。二进制里，2 的幂有且只有一个 1，例如 1=1、2=10、4=100、8=1000、16=10000。

但不是所有 2 的幂都是 4 的幂。8=2^3，虽然只有一个 1，却不是 4^k。区别在于指数是否为偶数，也就是唯一的 1 是否落在偶数位。

二、第一道门：必须是正数且只有一个 1

判断 2 的幂的经典条件是：

n > 0 且 (n & (n - 1)) == 0

原因是 2 的幂二进制形态为 1000...000。减 1 后变成 0111...111，两者相与为 0。比如：

16     = 10000
15     = 01111
16&15  = 00000

n > 0 不能省，因为 0 满足 (0 & -1) == 0，但 0 不是任何正整数幂。

三、第二道门：唯一的 1 要在偶数位

从最低位开始按 0 编号，4 的幂位置如下：

4^0 = 1   -> bit 0
4^1 = 4   -> bit 2
4^2 = 16  -> bit 4
4^3 = 64  -> bit 6

所以只要确认唯一的 1 在偶数位，就能排除 2、8、32 这类 2 的奇数次幂。32 位掩码 0x55555555 的模式是：

0x55555555 = 01010101010101010101010101010101

它在 bit 0、2、4、6 等偶数位为 1。若 n 是 2 的幂，那么 n & 0x55555555 非 0 就说明唯一的 1 落在偶数位。

记忆钩子：4 的幂先过“只有一个 1”的门，再过“这个 1 坐偶数位”的门。

四、掩码法和取模法怎么比较

方法	条件	优点	注意点
掩码法	`powerOfTwo && (n & 0x55555555) != 0`	完全位运算，直观对应偶数位	要记住偶数位掩码
取模法	`powerOfTwo && n % 3 == 1`	代码短	原理需要解释 `4^k mod 3 = 1`，其他 `2^(2k+1) mod 3 = 2`
循环除 4	不断除以 4	容易想到	时间不是常数级位技巧

面试里优先讲掩码法，因为它直接回应“位运算判断”的考点。若面试官追问其他写法，再补充取模法。

五、用 16 和 8 手推一遍

16 的二进制是 10000，唯一 1 在 bit 4：

n > 0                         true
16 & 15 = 10000 & 01111 = 0   true
16 & 0x55555555 != 0          true，因为 bit 4 是偶数位

8 的二进制是 1000，唯一 1 在 bit 3：

n > 0                       true
8 & 7 = 1000 & 0111 = 0     true
8 & 0x55555555 != 0         false，因为 bit 3 是奇数位

这两个例子能说明第二道门的必要性：只判断 2 的幂会误把 8 当成 4 的幂。

六、复杂度和语言边界

整个判断只做固定次数的比较、减法和按位与，因此时间 O(1)，空间 O(1)。对 Java int 来说，0x55555555 正好覆盖 32 位偶数位；如果使用 64 位整数，需要换成 0x5555555555555555L。

Python 中整数没有固定 32 位宽度，但原题输入在有界整数范围内，仍可使用数学法或根据范围准备掩码。面试答 Java/C++ 时要强调固定宽度掩码与题目整数范围一致。

七、常见误区与追问

误区：只判断 (n & (n-1)) == 0。 这只能判断 2 的幂，会把 8、32 等误判为 4 的幂。
误区：忘记 n > 0。 0 会通过清最低位 1 的表达式，但它不是 4 的幂。
误区：把 0xAAAAAAAA 和 0x55555555 用反。 前者通常是奇数位掩码，后者是偶数位掩码；用哪个取决于判断写成等于 0 还是不等于 0。
追问：为什么 4 的幂唯一 1 在偶数位？ 因为 4^k = 2^(2k)，指数 2k 是偶数。
追问：能不能用 n % 3 == 1？ 可以，在已确认是 2 的幂后，4 的幂模 3 为 1，其他相邻的 2 的幂模 3 为 2。
追问：64 位整数怎么办？ 掩码要扩展到 64 位偶数位，例如 Java long 使用 0x5555555555555555L。

八、加强记忆

判断 4 的幂分两层：先判断它是不是 2 的幂，再判断唯一的 1 是否在偶数位。代码主线是 n > 0、(n & (n-1)) == 0、(n & 0x55555555) != 0。2 的幂负责“只有一个 1”，偶数位掩码负责“这个 1 的位置对不对”。

简化版

详细版