给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
示例 1:
输入: 1 输出: true 解释: 2^0 = 1示例 2:
输入: 16 输出: true 解释: 2^4 = 16示例 3:
输入: 218 输出: false 解法 1：判断整数 \(x\) 的二进制表示中是否只有一位为1 实现方式 1：除以 2让我们先来看一下 2 的幂有什么规律，
n 2 的幂 二进制表示0 \(2^0 = 1\) 0000 0001
1 \(2^1 = 2\) 0000 0010
2 \(2^2 = 4\) 0000 0100
3 \(2^3 = 8\) 0000 1000
... ... ...
从上面可以看出，如果整数 \(x\) 是 2 的幂，将整数不断除以 2，除了 1 之外，其余的约数一定能被 2 整除。按照这样的想法，我们就能写出解法 1 的第一种实现。
Java 实现（非递归） class Solution { public boolean isPowerOfTwo(int x) { if (x <= 0) { return false; } while (x % 2 == 0) { x /= 2; } return x == 1; } } Python 实现（非递归） class Solution: def isPowerOfTwo(self, x): """ :type n: int :rtype: bool """ if x <= 0: return False while x % 2 == 0: x = x // 2 return x == 1 Java 实现（递归） class Solution { public boolean isPowerOfTwo(int x) { return x > 0 && (x == 1 || (x % 2 == 0 && isPowerOfTwo(x / 2))); } } Python 实现（递归） class Solution: def isPowerOfTwo(self, x): """ :type n: int :rtype: bool """ return x > 0 and (x == 1 or (x % 2 == 0 and self.isPowerOfTwo(x // 2))) 复杂度分析时间复杂度：两种实现（递归和非递归）的时间复杂度都是 \(O(\log(x))\) 的，其中 \(x\) 表示该整数
空间复杂度：非递归实现的空间复杂度是 \(O(1)\) 的，而递归实现的空间复杂度是 \(O(\log(x))\)，因此递归实现占用系统栈的空间，递归的深度最多为 \(\log(x)\)
实现方式 2：位运算对于实现方式 1，如果用二进制的角度看，就是判断整数的二进制表示的最右边一位是否为 1，如果为 1，则将该整数与 1 进行比较从而得到结果；如果不为 1，则将整数 \(x\) 右移一位（最高位补 0）。因此，我们就会想，是否有一种方式可以直接通过位运算就能达到目的，答案是肯定的。
让我们再来看看下面的表格有什么规律，
\(2^n\) \(2^n\) 的二进制表示 \(2^n - 1\) 的二进制表示1 0000 0001 0000 0000
2 0000 0010 0000 0001
4 0000 0100 0000 0011
8 0000 1000 0000 0111
... ... ...
从表格中可以看出，如果整数 \(x\) 是 2 的幂的话，整数 \(x\) 与 \(x - 1\) 的二进制表示进行与运算，结果为 0，因此我们就可以写出解法 1 的第二种实现方式。
Java 实现 class Solution { public boolean isPowerOfTwo(int x) { return x > 0 && ((x & (x - 1)) == 0); } } Python 实现 class Solution: def isPowerOfTwo(self, x): """ :type n: int :rtype: bool """ return x > 0 and (x & x - 1 == 0) 复杂度分析时间复杂度：\(O(1)\)
空间复杂度：\(O(1)\)