利用位运算实现计算2的幂

题目：

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

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

题目来源：231.2的幂

题目分析：

若 n=2
x
且 x 为自然数（即 n 为 2 的幂），则一定满足以下条件：

1.恒有n & (n – 1) == 0。因为二进制转为十进制公式为1 * 2^x + a₁ * 2^x-1 +···+ a_x * 2⁰，所以2的幂n的二进制为xxx00100000，所以n – 1的二进制为xxx00011111，所以n & (n – 1) == 0。

2.一定满足n > 0。

因此，通过n > 0 且 n & (n - 1) == 0 即可判定是否满足 n=2^x。

代码：

class Solution{
public:
    bool isPowerOfTwo(int n){
        if(n <= 0) return true;
        return !(n & n - 1);
    }
}

复杂度分析

• 时间复杂度：O(1)。
• 空间复杂度：O(1)。