2 的幂 图解题解
这道题到底在问什么
- 输入
- n = 16
- 输出
- true（16 = 2⁴）
- 输入
- n = 12
- 输出
- false（12 不是 2 的整数次方）
最优解：一步一步想明白
- 3记住这句话：2 的幂在二进制里「只有一个 1」。把每一位扫一遍数 1 的个数，恰好一个就是答案。
- 4先把 16 写成二进制 00010000（左边是高位）。我们要从左到右扫每一位，数里面总共有几个 1。
- 5指针走到第 0 位，这一位是 0。是 0，不是 1，直接跳过。
- 6这一位是 0，1 的个数不变，仍然是 0。继续看下一位。
- 7指针走到第 1 位，这一位是 0。是 0，不是 1，直接跳过。
- 8这一位是 0，1 的个数不变，仍然是 0。继续看下一位。
- 9指针走到第 2 位，这一位是 0。是 0，不是 1，直接跳过。
- 10这一位是 0，1 的个数不变，仍然是 0。继续看下一位。
- 11指针走到第 3 位，这一位是 1。是 1，把 1 的个数加一。
- 12这一位是 1，1 的总个数变成 1（绿色高亮的就是目前数到的所有 1）。
- 13指针走到第 4 位，这一位是 0。是 0，不是 1，直接跳过。
- 14这一位是 0，1 的个数不变，仍然是 1。继续看下一位。
- 15指针走到第 5 位，这一位是 0。是 0，不是 1，直接跳过。
- 16这一位是 0，1 的个数不变，仍然是 1。继续看下一位。
- 17指针走到第 6 位，这一位是 0。是 0，不是 1，直接跳过。
- 18这一位是 0，1 的个数不变，仍然是 1。继续看下一位。
- 19指针走到第 7 位，这一位是 0。是 0，不是 1，直接跳过。
- 20这一位是 0，1 的个数不变，仍然是 1。继续看下一位。
- 21扫完所有位，二进制 00010000 里只有 1 个 1（绿色那位）。恰好一个 1，所以 16 是 2 的幂，返回 true。
- 22换个反例：把 12 写成二进制 00001100。还是从左到右逐位数 1，看它能不能满足「恰好一个 1」。
- 23指针走到第 0 位，这一位是 0。是 0，跳过。
- 24这一位是 0，1 的个数不变，仍然是 0。
- 25指针走到第 1 位，这一位是 0。是 0，跳过。
- 26这一位是 0，1 的个数不变，仍然是 0。
- 27指针走到第 2 位，这一位是 0。是 0，跳过。
- 28这一位是 0，1 的个数不变，仍然是 0。
- 29指针走到第 3 位，这一位是 0。是 0，跳过。
- 30这一位是 0，1 的个数不变，仍然是 0。
- 31指针走到第 4 位，这一位是 1。是 1，把 1 的个数加一。
- 32这一位是 1，1 的总个数变成 1。
- 33指针走到第 5 位，这一位是 1。是 1，把 1 的个数加一。
- 34这一位是 1，1 的总个数变成 2（已经超过一个了）。
- 35指针走到第 6 位，这一位是 0。是 0，跳过。
- 36这一位是 0，1 的个数不变，仍然是 2。
- 37指针走到第 7 位，这一位是 0。是 0，跳过。
- 38这一位是 0，1 的个数不变，仍然是 2。
- 39扫完反例：12 的二进制里有 2 个 1（标红那两位），多于一个。所以 12 不是 2 的幂，返回 false。
⚠️ 容易写错的地方
✗ 错：忘了排除 n ≤ 0
✓ 对：先判 n > 0 再继续
0 和负数都不是 2 的幂；尤其 n & (n-1) 对 0 会得 0 而被误判成 true
✗ 错：以为「偶数」就是 2 的幂
✓ 对：必须恰好一个二进制 1
12、20 都是偶数但不是 2 的幂，它们二进制里有不止一个 1
✗ 错：用 n % 2 反复除 2 时漏判中途出现奇数
✓ 对：中途只要除不尽（出现奇数且 ≠1）就返回 false
如 12÷2=6、6÷2=3，3 是奇数且不为 1，说明 12 不是 2 的幂
完整代码（Python / C++ / Java）
Python
def isPowerOfTwo(n):
if n <= 0: # 2 的幂一定是正数
return False
# 数二进制里 1 的个数，恰好一个才是 2 的幂
return bin(n).count('1') == 1
# 位运算一行版（更快）:
# return n > 0 and n & (n - 1) == 0C++
bool isPowerOfTwo(int n) {
if (n <= 0) return false; // 必须是正数
int ones = 0;
for (int x = n; x; x >>= 1) // 逐位数 1 的个数
ones += x & 1;
return ones == 1;
// 一行版: return n > 0 && (n & (n - 1)) == 0;
}Java
class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0) return false; // 必须是正数
int ones = 0;
for (int x = n; x != 0; x >>= 1)
ones += x & 1; // 数 1 的个数
return ones == 1;
// 一行版: return n > 0 && (n & (n - 1)) == 0;
}
}复杂度
时间
O(1)
int 最多 32 位，数 1 的个数最多看 32 位，与 n 大小无关，是常数级
空间
O(1)
只用一个计数器，不开额外数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 2 的幂 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么「二进制只有一个 1」就等价于「是 2 的幂」？+
二进制第 k 位上的 1 代表数值 2^k。只有一个 1、其余全 0，整个数就正好等于那一个 2^k，也就是 2 的幂；有多个 1 则是若干个 2 的幂相加，不再是单个 2 的幂。
n & (n-1) == 0 为什么能判断 2 的幂？+
如果 n 只有一个 1（如 10000），n-1 会把那个 1 借位变成它后面全是 1（01111），两者按位与正好全为 0。所以 n>0 且 n&(n-1)==0 就说明只有一个 1。但要先保证 n>0，否则 0 会被误判。
如果允许负数输入怎么办？+
2 的幂必须是正数，所以一上来就判 n ≤ 0 返回 false。负数在补码下二进制有很多 1，本来也过不了「恰好一个 1」。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 2 的幂 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。