231. 2的幂
难度：简单 | 主题：位运算、数学
题目
给你一个整数 n，请你判断 n 是否为 2 的幂次方。如果是，返回 true；否则返回 false。如果存在一个整数 x 使得 n == 2^x，则认为 n 是 2 的幂次方。
示例
输入：n = 1
输出：true
解释：1 = 2⁰
思路
先讲个故事：掰巧克力
一块巧克力是 2 的幂（1, 2, 4, 8, 16 块）。你每次只能对半掰。如果能恰好掰成两半，再把每一半恰好掰成两半……一直掰到最后只剩一块——那就是 2 的幂。
在二进制里，2 的幂只有一个 1：1=1, 2=10, 4=100, 8=1000。n & (n-1) 清掉这个 1 后，结果必须是 0。
引导式推导：n & (n-1) == 0
核心：n & (n-1) == 0。2 的幂的二进制表示有且只有一个 1。
graph LR subgraph 2的幂的二进制 A["1 = 0001"] B["2 = 0010"] C["4 = 0100"] D["8 = 1000"] end subgraph n & n-1 E["8 & 7 = 1000 & 0111 = 0000 ✅"] F["6 & 5 = 0110 & 0101 = 0100 ❌"] end
同时需要 n > 0 排除 0 和负数：0 不是 2 的幂，且 0 & (-1) == 0 会误判。
| 方法 | 时间 | 空间 |
|---|---|---|
n & (n-1) | O(1) | O(1) |
| 循环除 2 | O(log n) | O(1) |
代码
def isPowerOfTwo(self, n):
return n > 0 and (n & (n - 1)) == 0
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(1) | 一次位运算 |
| 空间 | O(1) | 无额外空间 |
实战考量
频率分析
出现在：位运算经典题。考察
n & (n-1)的理解。字节/美团常考。
延伸思考
Q：n & (n-1) == 0 为什么能判断 2 的幂？
A：2 的幂的二进制只有最高位是 1，其余是 0（如 8 = 1000）。n-1 把最高位 1 变成 0、后面的 0 全变成 1（7 = 0111）。n & (n-1) = 1000 & 0111 = 0000 = 0。
Q：为什么还要 n > 0？
A：0 不是 2 的幂。0 & (0-1) = 0 & (-1) = 0，会错误返回 True。负数的二进制补码表示中有多个 1，也不满足。
Q：不用位运算怎么做？
A：循环除 2：while n % 2 == 0: n //= 2; return n == 1，O(log n)。
易错点
-
必须
n > 0（0 和负数） -
n & (n-1) == 0括号不能漏（==优先级高于&）
生活类比
2 的幂 → 完美的对称
2 的幂就像一个完美的金字塔：最顶层 1 块，第二层 2 块，第三层 4 块……每一层都是上一层的两倍。在二进制里，它只有一个 1，孤零零地站在最高位——像金字塔的尖顶。
相关题目
| 题目 | 关系 |
|---|---|
| 191位1的个数 | n & (n-1) 同族技巧 |
| 136只出现一次的数字 | 位运算经典题 |
→ 返回题单：LeetCode学习路线图 > 十四、数学与位运算
速记卡（面试闪卡）
Q1：一句话讲清「231. 2 的幂」到底是什么？
A：判断整数 n 是否为 2 的幂（即存在 x 使 n = 2^x），是则返回 true。本质是位运算的巧解。
Q2：题目与掰巧克力 —— 怎么理解？
A：像一块巧克力是 2 的幂（1、2、4、8……），每次只能对半掰，能恰好掰到只剩一块就是 2 的幂。在二进制里，2 的幂只有一个 1：1=1、2=10、4=100、8=1000。
Q3：核心 trick —— 怎么理解？
A：核心公式 n & (n-1) == 0。因为 2 的幂的二进制最高位是 1、其余是 0，n-1 把那个 1 变 0、后面全变 1，两者与运算即得 0。同时必须 n > 0——否则 0 & (-1) == 0 会误判 0 为 2 的幂。
Q4：代码与易错 —— 怎么理解？
A：一句话 return n > 0 and (n & (n-1)) == 0。括号不能漏，因为 == 优先级高于 &。不用位运算也能循环除 2（while n%2==0: n//=2; return n==1），但那是 O(log n)。
Q5：同类与延伸 —— 怎么理解？
A：时间空间都是 O(1)。同族技巧：191 题统计位 1 的个数也用 n & (n-1) 不断清最低位的 1；136 题只出现一次的数字用异或。
Q6：核心速记主线有哪些？
A：题目、二进制单 1、n&(n-1)==0、n>0 排除、O(1) 位运算、同类题。
口诀
A：二的幂次二进制，最高位上独一个；
n 与 n-1 清零为零，莫忘正数别漏掉。