题目描述

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

样例

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

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

输入：218
输出：false

算法

(位运算) $O(1)$

• 如果 n <= 0 则显然是 false；否则，有如下两种做法（不限于这两种）：
  1. 判断 (n & (-n)) == n，取负运算是将 n 的二进制位取反然后再加 1。这种运算有个名称叫 lowbit，即取出 n 二进制位中从低位数第一个 1 的位置 k ，并返回 $2^k$。判断 (n & (-n)) == n 成立即意味着 n 二进制位中从低位数第一个 1 的位置就是最高位。
  2. 判断 n & (n - 1) == 0，若成立，则显然 n 只有最高的二进制位是 1，后续的二进制位都是 0，符合 2 的幂次。

时间复杂度

• 位运算时间复杂度为 $O(1)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return (n > 0) ? ((n & -n) == n) : false;
    }
};