LeetCode 231. 2 的幂
目录
题目描述
题意分析
输入是一个 32 位有符号整数
n，问是否存在非负整数 $x$ 使得 $n = 2^x$。要注意指数从 0 起算，所以1也算符合条件。输入范围覆盖了负数和 0，这两类必须在一开始就判掉：$2^x$ 恒为正，任何非正数都不可能满足；同时最小值
-2^31的补码位模式是「只有最高位是 1」，形式上和 2 的幂长得一模一样，如果不先做符号判断，纯位运算会把它误判成真。题目没有给出任何数组或序列，只给一个数并要求判定一个乘法结构上的性质，说明可用的信息只有这个数本身的二进制形态。这提示答案应当是常数时间的，而不是从 1 开始不断翻倍去比对。
解法：清除最低位的 1
核心思路
正的 $2$ 的幂在二进制中恰好只有一个
1，例如8 = 1000₂。对任意正整数n，n - 1会把最低位的1变成0，并把它右侧的0全变成1，所以n & (n - 1)会清除n的最低位1。因此，
n是 $2$ 的幂，当且仅当：
n > 0；- 清除最低位
1后结果为0。正数判断不能省略。
0 & (-1) == 0，而0不是 $2$ 的幂；32 位最小负数的补码也只有最高位为1，同样会被纯位运算误判。
解题步骤
- 用
n > 0排除零和负数。- 计算
n & (n - 1)。- 结果为
0，说明原数恰好只有一个二进制1，返回真；否则返回假。例如
16 = 10000₂，15 = 01111₂，按位与为0；而12 = 1100₂，与11 = 1011₂按位与后仍剩1000₂，所以不是 $2$ 的幂。
代码实现
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}
func isPowerOfTwo(n int) bool {
return n > 0 && n&(n-1) == 0
}
复杂度分析
- 时间复杂度：$O(1)$，只执行固定次数的整数运算。
- 空间复杂度：$O(1)$。
关键点总结
- $2$ 的幂的二进制特征是“正数且只有一个
1”。n & (n - 1)清除最低位1；n & -n则提取最低位1。- 面试中不仅要写出一行代码，还要能解释
n - 1的借位变化。- 判断 $4$ 的幂时还需额外限制这个
1出现在偶数位，这是常见追问。
易错点总结
- 漏掉
n > 0：0和最小负数都会被误判。- 写成
n >= 0：仍然没有排除0。- 用浮点对数判断：边界附近可能受精度影响，且没有位运算直接。
- 从
1开始反复乘2：能做，但需要处理溢出，复杂度也变为 $O(log n)$。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 342. 4的幂 | 简单 | 在单个 1 的基础上追加「1 必须落在偶数位」 |
| 326. 3 的幂 | 简单 | 底数非 2，二进制无捷径，改用整除或最大幂取模 |
| 191. 位1的个数 | 简单 | 把「抹最低位 1」变成循环，统计总次数 |
| 338. 比特位计数 | 简单 | 用 i & (i - 1) 建立递推，批量求一段区间 |
| 136. 只出现一次的数字 | 简单 | 考的是异或的自反性而非单个数的位模式 |