高效判断2的幂次方：位运算技巧与应用

1. 问题背景与基础解法

判断一个数是否为2的整数幂是编程面试和算法竞赛中的经典问题。我们先从一个直观的解法开始，逐步深入探讨更高效的实现方式。

1.1 循环除法解法

最直接的想法是通过循环除以2来判断：

cpp复制bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    while (n % 2 == 0) {
        n /= 2;
    }
    return n == 1;
}

这个解法的时间复杂度是O(log n)，对于32位整数来说最多需要31次循环。虽然正确，但效率不够理想。

注意：必须处理n<=0的情况，因为负数和零显然不是2的幂

1.2 位运算优化

观察二进制表示可以发现，2的幂次方数在二进制中只有一个1：

• 2 (10)
• 4 (100)
• 8 (1000)
• 16 (10000)

而n-1的二进制表示则是全1：

• 1 (1)
• 3 (11)
• 7 (111)
• 15 (1111)

因此，n & (n-1)的结果为0时，n就是2的幂次方。这个操作可以直接清除最低位的1。

2. 位运算解法详解

2.1 核心原理

对于任何2的幂次方数n，满足：

1. n > 0
2. n的二进制表示中只有一个1
3. n & (n-1) == 0

2.2 实现代码

cpp复制bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

这个解法的时间复杂度是O(1)，只需要几次位运算操作。

2.3 边界情况处理

需要特别注意的边界情况：

1. n = 0：0不是2的幂
2. n = 1：2^0 = 1
3. n = INT_MIN：在补码表示中，-2147483648的二进制是100...000，虽然满足n&(n-1)==0，但根据数学定义不算2的幂

3. 性能对比与优化

3.1 时间复杂度分析