LeetCode 231. 2 的幂
本节目标
用正数判断和清除最低位的 1，识别二进制中恰好有一个 1 的数。
这道题承接二进制与位运算基础：不必逐位计数，只需判断清除最低位的 1 后是否为 0。
题意与约束
给定整数 n，判断它是否能写成 2^k，其中 k 是非负整数。也就是说，1 = 2^0 是答案，0 和负数都不是。
2 的幂为什么只有一个 1
每乘一次 2，二进制中的唯一 1 左移一位：1 = 1₂、2 = 10₂、8 = 1000₂。反过来，任何正整数只要二进制中恰好有一个 1，就正好是某个 2 的幂。
清除最低位的 1
对正数执行 n & (n - 1)，会清除其最低位的 1。因此，二进制只有一个 1 时，结果恰好为 0；有多个 1 时，清除一个后仍非零。
例如 8 & 7 = 0，而 12 & 11 = 8，所以 8 是 2 的幂，12 不是。
非正数边界
必须先判断 n > 0。若只检查 (n & (n - 1)) == 0，0 & (-1) 也是 0，会把 0 误判为 2 的幂。负数同样不符合题意；先做正数判断也让后续位运算只处理有效范围。
代码实现
两种语言都以同一个短路条件完成判断：先排除非正数，再检查清除一个最低位 1 后是否为 0。
- C++
- Python
C++17
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
};
Python 3
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and (n & (n - 1)) == 0
复杂度分析
- 时间复杂度：
O(1)，只执行常数次位运算。 - 空间复杂度：
O(1)。
易错点
- 漏掉
n > 0：会把0误判为真。 - 将“只有一个
1”理解成十进制只含一个数字：判断对象是二进制表示。 - 用循环不断除以
2：能够通过，但没有直接利用位模式，且需要额外迭代。
模式迁移
“正数且只有一个置位 1”是位运算中的常见判定模板。判断 4 的幂时还需确认该 1 位于偶数位置；枚举子集或提取最低位 1 时，则可继续使用 n & -n 与 n & (n - 1)。