企业官网建设流程全解析

• 教程
• 文档

导读

本文基于开源仓库 LogicStack-LeetCode 中「刷穿 LeetCode」系列的 231. 2 的幂（简单） 题解文档，系统讲解如何判断一个整数是否为 2 的幂次方。文章完整覆盖原文档的「朴素试除」与「lowbit 位运算」两种解法，并结合仓库中 191. 位1的个数、342. 4的幂 等关联题解，深入剖析lowbit的底层原理、负数与溢出边界，以及该题在「位运算」知识体系中的位置。读完本文，你将掌握 2 的幂判断的完整套路，并能在面试与工程中直接复用lowbit这一高频位运算技巧。

一、题目背景与题意分析

该题出自 LeetCode/231-240 目录，是「刷穿 LeetCode」系列的第No.231篇，Tag 为「数学」「位运算」，难度为简单。在仓库的 位运算索引 中，本题与 137. 只出现一次的数字 II、191. 位1的个数、260. 只出现一次的数字 III、342. 4的幂 等题同属于「位运算」专题索引。

题目描述：给你一个整数n，判断该整数是否是 2 的幂次方。如果是，返回true；否则返回false。若存在一个整数x使得n == 2^x，则认为n是 2 的幂次方。

示例：

提示与约束：

• 数据范围：$-2^{31} \le n \le 2^{31} - 1$，即n是 32 位有符号整数int；
• 进阶要求：不使用循环/递归解决此问题。

进阶条件直接指向位运算方向——因为 2 的幂在二进制表示中具有极强的结构特征（只有一个位为 1），完全可以在 $O(1)$ 时间内完成判定。

二、朴素做法：循环试除

这是最容易想到、也最容易写对的解法。

2.1 核心思路

• 首先处理边界：小于等于 0 的数必然不是2 的幂（$2^x > 0$ 恒成立）；
• 1 必然是（$2^0 = 1$）；
• 处理完上述边界后，尝试将n对 2 反复试除，只要n还能被 2 整除就继续除；
• 如果最后剩余数值为1，说明最初的n是 2 的幂。

2.2 完整代码

原文档给出的 Java 实现如下：

class Solution { public boolean isPowerOfTwo(int n) { if (n <= 0) return false; while (n % 2 == 0) n /= 2; return n == 1; } }

2.3 复杂度分析

• 时间复杂度：$O(\log n)$。n每次除以 2，最多执行 $\log_2 n$ 次循环；
• 空间复杂度：$O(1)$，仅使用常数级额外空间。

2.4 正确性验证

以几个典型输入验证：

• n = 1：跳过while，返回1 == 1，即true；
• n = 16：16 → 8 → 4 → 2 → 1，循环结束返回true；
• n = 3：3 % 2 != 0，不进入循环，3 == 1为false；
• n = 0/n = -8：n <= 0直接返回false。

朴素解法的局限在于：即使n的二进制表示中只有一位为 1，也必须通过多次除法逐步"剥掉"低位的 0，无法利用二进制本身的位级特征，这也是进阶要求（不用循环/递归）要突破的点。

三、lowbit 解法：一行代码的位运算判定

3.1 什么是 lowbit

熟悉树状数组的同学都知道，lowbit可以快速求得x二进制表示中最低位 1 所表示的值。

lowbit(x) = x & (-x)

在 191. 位1的个数 的题解中，对lowbit有更详细的展开：

使用lowbit即可做到，lowbit会在 $O(1)$ 复杂度内返回二进制表示中最低位 1 所表示的数值。 例如 $(0000...111100)_2$ 传入lowbit返回 $(0000...000100)_2$；$(0000...00011)_2$ 传入lowbit返回 $(0000...00001)_2$ ...

其原理是：-x在计算机中按二进制补码表示，等价于对x取反再加 1。x & (-x)的结果恰好只保留了x最低位的那个 1，其余位全部归零。

3.2 核心结论：2 的幂 ⇔ lowbit(n) = n

如果一个数n是 2 的幂，那么有lowbit(n) = n的性质。

原因在于：2 的幂的二进制表示中必然是最高位为 1，其余低位全为 0。此时最低位的 1 就是最高位本身，因此lowbit(n)取出的值恰好等于n自身。例如：

• n = 1：二进制1，lowbit = 1 = n；
• n = 16：二进制10000，lowbit = 10000 = 16 = n；
• n = 12：二进制1100，lowbit = 100 = 4 ≠ 12，不是 2 的幂。

3.3 完整代码

原文档给出的 Java 实现极其简洁：

class Solution { public boolean isPowerOfTwo(int n) { return n > 0 && (n & -n) == n; } }

这里n > 0承担了双重职责：

1. 排除所有非正数（包括 0 与所有负数）；
2. 避免n为Integer.MIN_VALUE（即 $-2^{31}$）时对-n取负发生整型溢出——由于负值已被短路排除，(n & -n)只会在正数上求值，因而安全。

3.4 复杂度分析

• 时间复杂度：$O(1)$，一次按位与运算，与n的大小无关；
• 空间复杂度：$O(1)$。

相比朴素试除的 $O(\log n)$，lowbit解法做到了严格的常数时间，完美满足题目的进阶要求。

3.5 边界推演

四、从 lowbit 到同类问题：仓库内的位运算专题串联

lowbit并非孤例，它在仓库的「位运算」与「树状数组」体系中反复出现，理解本题是掌握这一技巧的最佳切入点。

4.1 在 191. 位1的个数 中的复用

191. 位1的个数 展示了lowbit的另一个经典用法——只对位数为 1 的二进制位进行处理，从而统计 1 的个数：

public class Solution { int lowbit(int x) { return x & -x; } public int hammingWeight(int n) { int ans = 0; for (int i = n; i != 0; i -= lowbit(i)) ans++; return ans; } }

每次用i -= lowbit(i)把最低位的 1 消掉，循环次数等于二进制中 1 的个数，而不是固定的 32 位。这与本题lowbit(n) == n的判定形成呼应：2 的幂恰好是"只含一个 1"的数，所以lowbit一次就能把它"完整取出"。

4.2 在 342. 4的幂 中的直接引用

342. 4的幂 的题解明确引用了本题的判定结论：

判断某个数是否为 2 的幂的分析在（题解）231. 2 的幂 这里。

其思路是：一个数n如果是 4 的幂，等价于n为质因数只有 2 的平方数，因此可将问题转换为——判断 $\sqrt{n}$ 是否为 2 的幂：

class Solution { public boolean isPowerOfFour(int n) { if (n <= 0) return false; int x = (int)Math.sqrt(n); return x * x == n && (x & -x) == x; } }

可以看到(x & -x) == x正是本题lowbit判定的直接复用——这正是本系列"一个结论打通多题"的价值体现。

4.3 在 326. 3的幂 中的对照

326. 3的幂 给出了"倍数 & 约数"的 $O(1)$ 解法：

题目要求不能使用循环或递归来做，而传参n的数据类型为int，这引导我们首先分析出int范围内的最大 3 次幂是多少，约为 $3^{19} = 1162261467$。如果n为 3 的幂的话，那么必然满足 $n \times 3^k = 1162261467$，即n与 1162261467 存在倍数关系。

class Solution { public boolean isPowerOfThree(int n) { return n > 0 && 1162261467 % n == 0; } }

题解中特别强调："这并不是快速判断x的幂的通用做法，当且仅当x为质数可用。"对照本题可以更深刻地理解两者的差异：2 是质数，用lowbit判定依赖的是二进制表示的结构特征（恰好一位为 1），这是 2 的幂独有的性质；而 3 的幂没有类似的位级特征，只能依赖"最大幂的约数"这一数学性质。两条路径分别展示了"位运算解法"与"数学解法"的典型范式。

4.4 在仓库位运算索引中的定位

Index/位运算.md 收录了包括本题在内的 20 余道位运算题目，如 137（只出现一次的数字 II）、190（颠倒二进制位）、191（位1的个数）、260（只出现一次的数字 III）、342（4的幂）、371（两整数之和）等。建议在刷完本题后，按索引顺序补全lowbit在"统计 1 的个数""异或消去"等场景下的应用，形成完整的位运算知识闭环。

五、补充：n & (n - 1) 判定法（通用位运算常识）

除lowbit外，位运算领域还有一个等价的经典判定：n > 0 && (n & (n - 1)) == 0。其依据是——2 的幂的二进制只有一个位为 1；对这样的数减 1，会让该位变 0、其右侧所有低位变 1，因此n & (n - 1)必为 0。反之，若n含两个及以上为 1 的位，n & (n - 1)至少会保留一个 1，结果不为 0。

class Solution { public boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; } }

该方法同样为 $O(1)$ 时间、$O(1)$ 空间，与lowbit判定殊途同归。二者的本质都是"2 的幂 = 二进制中恰好一个 1"这一性质的不同位运算表达。需要说明的是，此写法属于通用位运算常识，并非本文档原文内容，作为补充拓展供读者对比记忆。

六、解法总览与复杂度对比

工程与面试实践中推荐lowbit写法，因为它同时是树状数组、统计二进制中 1 的个数等场景的核心原语，一次掌握、多处受益。

七、仓库阅读指引

若想深入本专题，可在仓库中按以下路径继续阅读：

• 231. 2 的幂（简单）题解原文：本文的原始依据，含朴素做法与 lowbit 两套代码；
• 191. 位1的个数（简单）：lowbit原理详解与三种$O(k)$统计方案；
• 342. 4的幂（简单）：对 231 结论的直接复用，展示"化为 2 的幂"的转换思路；
• 326. 3的幂（简单）：数学解法（最大幂约数）与打表解法的对照参考；
• 位运算专题索引：位运算类题目的完整索引，便于按 Tag 刷题；
• 数学专题索引：包含 231、326、342 等题目，适合从数学视角横向比较。

所有题解均位于 LeetCode 目录 下按题号区间分目录组织，PDF 版本题解合集位于 PDF 目录，可离线阅读对照。

• 教程
• 文档