LeetCode 231. 2 的幂
题目描述
题意分析
判断整数
n能否写成2的某个非负整数次幂。指数可以为0，所以1也符合；零和所有负数都不符合。返回布尔值，不需要求出指数，也不需要构造小于
n的所有幂。题目使用固定宽度整数，可以直接利用它的二进制位。
解法：清除最低位的 1
核心思路
[!blue]
2每乘一次自身，二进制中的那一个1就向左移动一位，所以正数是2的幂，当且仅当它的二进制恰好有一个1。问题因此转化为判断是否只有一个置位。对任意正整数做
n - 1，减法会从最低位的1借位：这个1变成0，它右边原来的所有0变成1，更高的位保持不变。再将
n与n - 1按位与。最低的那个1因另一侧为0而被清除，它右侧各位因原数为0也全部为0，高位则保持原样。因此n & (n - 1)恰好清掉原数最低的一个1，其他1不受影响。如果结果为
0，说明原来只有这一个1；如果仍非零，说明还有其他置位。这个推理以正数为前提，所以先检查n > 0，再做位判断，才能排除零和有符号负数。
解题步骤
- 若
n <= 0，返回false。- 对正数计算
n & (n - 1)，清除最低的一个二进制1。- 结果为
0就返回true，否则返回false。代码用短路与把两步合并成一个表达式。
代码实现
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)$。
关键点总结
[!green]
- “正数且恰好一个二进制
1”是二的幂的完整判定条件。- 减一产生借位变化，按位与利用这一变化只清除最低置位。
- 正数检查与位判断缺一不可，
1则自然通过，不需要单独处理指数为零。
易错点总结
[!yellow]
- 只检查按位与结果，会把同样得到零的
n = 0放行，必须先排除非正数。- 写成
n >= 0仍然接受了零；正确条件是严格大于零。- 把
1当作不符合，会漏掉2⁰。- 忽略括号容易混淆按位与和比较的运算顺序；Java 应明确先算
n & (n - 1)，再与零比较。- 将十进制位数或偶数性当作充分条件，只能排除一部分数，无法保证二进制仅有一个
1。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 342. 4的幂 | 简单 | 4的幂首先必须是2的幂，还要要求唯一的1落在偶数位位置。 |
| 326. 3 的幂 | 简单 | 3的幂没有二进制单一置位特征，不能照搬x&(x-1)判定。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！