0231.md

title	description	keywords
2^31. 2 的幂	LeetCode 2^31. 2 的幂题解，Power of Two，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 2^31. 2 的幂 2 的幂 Power of Two 解题思路 位运算 递归 数学

2^31. 2 的幂

🟢 Easy  🔖  位运算 递归 数学  🔗 力扣 LeetCode

题目

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

Example 1:

Input: n = 1

Output: true

Explanation: 20 = 1

Example 2:

Input: n = 16

Output: true

Explanation: 24 = 16

Example 3:

Input: n = 3

Output: false

Constraints:

• -2^31 <= n <= 2^31 - 1

Follow up: Could you solve it without loops/recursion?

题目大意

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：

输入： n = 1

输出： true

解释： 20 = 1

示例 2：

输入： n = 16

输出： true

解释： 24 = 16

示例 3：

输入： n = 3

输出： false

提示：

• -2^31 <= n <= 2^31 - 1

进阶： 你能够不使用循环/递归解决此问题吗？

解题思路

思路一：逐步除以 2

• 不断将 n 除以 2，直到 n 为 1。如果途中有无法整除的情况，则说明 n 不是 2 的幂。
• 如果 n <= 0，直接返回 false，因为负数和 0 不可能是 2 的幂。

代码

var isPowerOfTwo = function (n) {
	if (n <= 0) return false;
	while (n > 1) {
		if (n % 2 !== 0) return false;
		n = n / 2;
	}
	return true;
};

复杂度分析

• 时间复杂度：O(log n)，n 每次被除以 2，最多进行 log n 次操作。
• 空间复杂度：O(1)，不需要额外空间。

---

思路二：按位与操作

• 2 的幂次方的特点是它的二进制表示中只有一位是 1，例如：
  • 1 (2^0) 是 0001
  • 2 (2^1) 是 0010
  • 4 (2^2) 是 0100
  • 8 (2^3) 是 1000
• 判断是否是 2 的幂次方，只需检查 n 是否大于 0 且满足 n & (n - 1) == 0。
  • n & (n - 1) 会将 n 的最低位的 1 变为 0，而其他位保持不变。如果结果为 0，则 n 是 2 的幂次方。

代码

var isPowerOfTwo = function (n) {
	return n > 0 && (n & (n - 1)) === 0;
};

复杂度分析

• 时间复杂度：O(1)，只需一次按位操作。
• 空间复杂度：O(1)。

---

思路三：对数判断

• 如果 n 是 2 的幂次方，则 log2(n) 是整数。
• 用 Math.log2(n) 计算 log2(n)，检查是否为整数。

代码

var isPowerOfTwo = function (n) {
	if (n <= 0) return false;
	return Math.log2(n) % 1 === 0;
};

复杂度分析

• 时间复杂度：O(1)，Math.log2() 是常数时间操作。
• 空间复杂度：O(1)。

---

思路四：模运算与整数溢出

• 使用最大范围内的 2 的幂次方数（如 2^30 = 1073741824，因为 2^31 已超过 32 位整数范围）。
• 如果 n 是 2 的幂次方，则它一定能整除 2^30。

代码

var isPowerOfTwo = function (n) {
	return n > 0 && 1073741824 % n === 0;
};

复杂度分析

• 时间复杂度：O(1)，只有一次取模操作。
• 空间复杂度：O(1)。

---

思路五：递归法

• 如果 n 是 2 的幂次方，则 n 应该等于 1 或者能被 2 整除后递归调用自身继续判断。

代码

var isPowerOfTwo = function (n) {
	if (n <= 0) return false;
	if (n === 1) return true;
	return n % 2 === 0 && isPowerOfTwo(n / 2);
};

复杂度分析

• 时间复杂度：O(log n)，n 每次递归减小一半。
• 空间复杂度：O(log n)，递归调用栈的深度。

---

思路六：预计算法

• 预先存储所有 2 的幂次方（例如 2^0, 2^1, ..., 2^30）。
• 用一个集合存储这些值，判断时直接查找。

代码

const powersOfTwo = new Set();
for (let i = 0; i <= 30; i++) {
	powersOfTwo.add(1 << i); // 2^i
}

var isPowerOfTwo = function (n) {
	return powersOfTwo.has(n);
};

复杂度分析

• 时间复杂度：O(1)，查找集合中的元素是常数时间操作。
• 空间复杂度：O(1)，集合的大小固定为 31 个元素。

---

比较总结

解法	时间复杂度	空间复杂度	优缺点
逐步除以 2	O(log n)	O(1)	简单易懂，但不够高效
按位与操作	O(1)	O(1)	最优解，高效且简洁
对数判断	O(1)	O(1)	需依赖浮点运算，可能有精度问题
模运算	O(1)	O(1)	易于实现，但需硬编码最大范围
递归法	O(log n)	O(log n)	直观，但递归调用消耗较大
预计算法	O(1)	O(1)	适合范围固定的场景

推荐使用 按位与操作 解法，兼具高效性和代码简洁性。

相关题目

题号	标题	题解	标签	难度	力扣
191	位1的个数	[✓]	位运算 分治	🟢	🀄️ 🔗
326	3 的幂	[✓]	递归 数学	🟢	🀄️ 🔗
342	4的幂	[✓]	位运算 递归 数学	🟢	🀄️ 🔗