231.2的幂

给你一个整数n，请你判断该整数是否是2的幂次方。如果是，返回true；否则返回false。如果存在一个整数x使得n==2^x，则认为n是2的幂次方。

示例 1：

输入：n = 1
输出：true
解释：20 = 1
示例 2：

输入：n = 16
输出：true
解释：24 = 16
示例 3：

输入：n = 3
输出：false
示例 4：

输入：n = 4
输出：true
示例 5：

输入：n = 5
输出：false

方法一：二进制表示

思路与算法

一个数n是2的幂，当且仅当n是正整数，并且n的二进制表示中仅包含一个1。因此我们可以考虑使用位运算，将n的二进制表示中最低位的那个1提取出来，再判断剩余的数值是否为0即可。

第一个技巧是 n&(n-1),其中&表示按位与运算。该位运算可以直接将n二进制表示的最低位1移除。因此，如果n是正整数并且n&（n-1）==0那么n就是2的幂数。

第二个技巧是n&(-n)，其中-n是n的相反数，是一个负数。该位运算技巧可以直接获取n二进制表示的最低位的1。由于负数是按照补码规则在计算机中储存的，-n的二进制表示为每一位取反再加1。因此，如果n是正整数并且n&(-n)==n，那么n就是2的幂。

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

bool isPowerOfTwo(int n) { return n > 0 && (n & -n) == n;      }

时间复杂度：O（1）

空间复杂度：O（1）

方法二：判断是否为最大2的幂的约数

思路与算法：除了使用二进制表示判断之外，还有一种较为取巧的做法。在题目给定的32位有符号整数的范围内，最大的2的幂为2^30==1073741824。我们只需要判断n是否为2^30的约数即可。

const int BIG = 1 << 30;

bool isPowerOfTwo(int n) {

    return n > 0 && BIG % n == 0;

}

时间复杂度：O（1）

空间复杂度：O（1）