LeetCode第231题：2的幂 · 江川个人博客

问题描述

给你一个整数 n，请你判断该整数是否是 2 的幂。

如果是，返回 true ；否则，返回 false 。

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

难度：简单

示例

示例 1：

输入：n = 1
输出：true
解释：2^0 = 1

示例 2：

输入：n = 16
输出：true
解释：2^4 = 16

示例 3：

输入：n = 3
输出：false

示例 4：

输入：n = 4
输出：true

示例 5：

输入：n = 5
输出：false

约束条件

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

解题思路

判断一个数是否为2的幂有几种常见的方法：

方法一：循环迭代

最直接的方法是不断将 n 除以 2，检查是否每次都能整除，直到 n 变为 1。如果在这个过程中出现了不能被 2 整除的情况，那么 n 就不是 2 的幂。

方法二：位运算

2的幂在二进制表示中有一个重要特性：它只有一个位是1，其余位都是0。例如：

1 的二进制是 0001
2 的二进制是 0010
4 的二进制是 0100
8 的二进制是 1000

有几种位运算技巧可以用来判断：

n & (n-1) == 0：这个技巧利用了将 n 减去 1 后，二进制中最右边的 1 会变成 0，其右边的 0 都会变成 1。对于 2 的幂，这会把唯一的 1 变成 0，其他位不变，所以 n & (n-1) 应该为 0。
n & (-n) == n：这个技巧利用了负数在计算机中以补码表示，-n 的二进制表示是对 n 的二进制表示取反加 1。对于 2 的幂，n & (-n) 会保留最右边的 1，其他位变为 0，等于 n 本身。

另外，还需要考虑 n 为负数或零的情况，因为负数和零不是 2 的幂。

代码实现

C#实现

public class Solution {
    public bool IsPowerOfTwo(int n) {
        // 负数和零不是2的幂
        if (n <= 0) return false;
        
        // 使用位运算检查是否只有一个位是1
        return (n & (n - 1)) == 0;
    }
}

Python实现

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        # 负数和零不是2的幂
        if n <= 0:
            return False
        
        # 使用位运算检查是否只有一个位是1
        return (n & (n - 1)) == 0

C++实现

class Solution {
public:
    bool isPowerOfTwo(int n) {
        // 负数和零不是2的幂
        if (n <= 0) return false;
        
        // 使用位运算检查是否只有一个位是1
        return (n & (n - 1)) == 0;
    }
};

性能分析

各种实现方法的性能比较：

方法	时间复杂度	空间复杂度	执行时间	内存消耗
循环迭代	O(log n)	O(1)	较慢	小
位运算 (n & (n-1))	O(1)	O(1)	最快	小
位运算 (n & (-n))	O(1)	O(1)	很快	小

其中位运算的方法在处理整数时效率最高，因为它能在常数时间内直接判断，而不需要多次迭代。C++和C#的位运算实现通常比Python更快，因为Python需要处理大整数的情况，而且位运算在某些Python环境中可能不会被优化。

代码特点

解法简洁明了，一行代码即可判断
利用了二进制表示和位运算的特性
处理了边界情况（负数和零）
时间复杂度为O(1)，空间复杂度也为O(1)

优化方向

这个问题的最佳解法已经是O(1)时间复杂度的位运算方法，很难进一步优化时间或空间复杂度。不过，根据具体语言的特性，可能有一些微小的优化：

在某些语言中，使用内置的位操作函数可能会更快
对于特殊情况（如已知n不会是负数）可以省略边界检查

常见错误

忘记检查n是否为负数或零
使用循环方法时，忘记处理n为1的特殊情况
误用位运算技巧，如写成 (n & n-1) 而不是 (n & (n-1))