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

简化版

判断正整数 n 是否是 2 的幂（1、2、4、8、16…）。位运算一行搞定：2 的幂的二进制表示有且仅有一个 1（如 4 = 100、8 = 1000），所以 n > 0 && (n & (n - 1)) == 0 即是——n & (n-1) 会消掉最低位的 1，若结果为 0 说明原本只有一个 1。另一等价写法 n > 0 && (n & (-n)) == n（最低位的 1 就是它自己）。别忘了先判 n > 0（0 和负数不是 2 的幂）。

详细版

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

等价写法（lowbit）：

boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (-n)) == n;   // 最低位的 1 恰好等于 n 本身
}

关键性质：2 的幂 ⇔ 二进制只有一个 1。
n & (n-1) == 0：消掉唯一的 1 后变 0 ⇒ 原来只有一个 1。
n > 0 不可省：0 和负数都要排除。0 满足 n&(n-1)==0 但不是 2 的幂；负数补码有多个 1。
复杂度：O(1)。

完整版教学

一、核心洞察：2 的幂只有一个 1

2 的幂是 2^k，二进制表示是「第 k 位是 1、其余全 0」：1 = 1、2 = 10、4 = 100、8 = 1000……有且仅有一个 1。反过来，二进制中只有一个 1 的正数，一定是某个 2^k。所以「判断 2 的幂」 = 「判断二进制中恰好一个 1」。位运算判断「只有一个 1」有现成的技巧。

二、`n & (n - 1) == 0` 的原理

前面数 1 的题讲过，n & (n - 1) 会消掉 n 最低位的那个 1。

如果 n 只有一个 1，消掉后就变成 0；
如果 n 有两个及以上的 1，消掉最低位的 1 后还剩别的 1，结果非 0。

所以 (n & (n-1)) == 0 恰好判断「n 只有一个 1」——即 2 的幂（配合 n > 0）。这是最常用的写法。

三、为什么 `n > 0` 不能省

两个反例说明必须先判正：

n = 0：0 & (-1) = 0，(n & (n-1)) == 0 成立，但 0 不是 2 的幂。必须用 n > 0 排除。
n < 0（负数）：Java 补码下负数最高位是 1、通常有多个 1，n & (n-1) 一般非 0，但个别负数可能碰巧……总之 2 的幂定义在正整数上，负数一律排除。n > 0 一并处理。

所以完整条件是 n > 0 && (n & (n-1)) == 0，两个条件缺一不可。

四、等价写法：lowbit `n & (-n) == n`

n & (-n) 取出 n 最低位的 1（lowbit）。如果 n 本身就只有一个 1，那么「最低位的 1」就等于 n 自己，即 (n & -n) == n。若 n 有多个 1，n & -n 只是其中最低的那个，小于 n，不相等。所以 n > 0 && (n & -n) == n 也能判 2 的幂，和 n&(n-1)==0 等价。两种写法记一个即可。

五、相关变体

4 的幂（342）：不仅要只有一个 1，这个 1 还要在偶数位（4^k 的 1 在第 0、2、4… 位）。判断：n > 0 && (n & (n-1)) == 0 && (n & 0x55555555) != 0（0x55555555 的 1 都在偶数位）。
3 的幂（326）：3 不是 2 的幂族，没有漂亮的位技巧，用循环除 3 或「最大 3 的幂能否整除」判断。
判断只有一个 1 的通用场景：状态压缩里判断「某状态是否只选了一个元素」也用 n & (n-1) == 0。

六、把判定条件拆成必要与充分两面

正整数是 2 的幂，当且仅当其二进制恰有一个 1。必要性来自 2^k 就是 1 左移 k 位；充分性来自任何只有第 k 位为 1 的正整数都等于 2^k。n&(n-1) 清掉唯一的 1 后为 0，因此它正好把“只有一个 1”变成可执行判定。

n=16:  00010000
n-1:   00001111
相与:    00000000  => 通过
n=18:  00010010
n-1:   00010001
相与:    00010000  => 不通过
n=0 也得到 0，所以必须先检查 n>0

校验维度	本题必须保持的结论
循环/递推不变量	判定只针对正整数；通过位表达式等价于 popcount(n)=1。
边界条件	1 是 `2^0`，应返回 true；0 和所有负数都应返回 false。
复杂度与代价	固定宽度整数只做比较、减法和按位与，时间与空间均 O(1)。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

位运算题的代码通常很短，真正容易错的是把数学整数、固定宽度位模式和语言移位规则混在一起。本题应先复述这条不变量：判定只针对正整数；通过位表达式等价于 popcount(n)=1。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“n=16: 00010000”开始手推，最后应得到“n=0 也得到 0，所以必须先检查 n>0”。
边界复核：1 是 2^0，应返回 true；0 和所有负数都应返回 false。
代价复核：固定宽度整数只做比较、减法和按位与，时间与空间均 O(1)。
用全 0、只有一个 1、最高位为 1 三类位模式检查掩码。
涉及负数时把值写成固定宽度补码，确认使用 >> 还是 >>>。
涉及左移时检查移位距离和溢出后是否仍符合题目的位模式语义。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“判定只针对正整数；通过位表达式等价于 popcount(n)=1。”这条正确性主线不能省。

八、常见误区与追问

误区：1 不是 2 的幂。 1=2^0，二进制只有最低位一个 1，属于 2 的幂。
误区：只写 (n&(n-1))==0 已经完整。 0 会误判，负数也不在题意的正幂集合中，必须加 n>0。
误区：用浮点对数判断更可靠。 浮点舍入可能让接近整数的对数产生误判，位判定既精确又更简单。
追问：如何判断 4 的幂？ 先判 2 的幂，再要求唯一的 1 位于偶数下标，可配合掩码 0x55555555。
追问：n&-n==n 为什么等价？ 左侧取 lowbit；若它等于 n，说明 n 除最低位 1 外没有其他 1。
追问：如何判断某整数是否恰有 k 个 1？ 反复执行 n&=n-1 并计数，或使用语言提供的 bitCount。

九、加强记忆

判断 2 的幂 = 「二进制只有一个 1」，用 n > 0 && (n & (n - 1)) == 0（n&(n-1) 消掉唯一的 1 后为 0）。等价写法 n > 0 && (n & -n) == n（最低位的 1 即自身）。n > 0 绝不能省——0 会误判、负数要排除。变体：4 的幂再加 (n & 0x55555555) != 0（1 在偶数位）。核心一行：n>0 && (n&(n-1))==0。

简化版

详细版