2^31. 2 的幂
2^31. 2 的幂
题目
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) 是00012(2^1) 是00104(2^2) 是01008(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的幂 | [✓] | 位运算 递归 数学 | 🟢 | 🀄️ 🔗 |