【Leetcode】231. 2的幂

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

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

示例 1：

输入：n = 1
输出：true
解释：20 = 1

示例 2：

输入：n = 16
输出：true
解释：24 = 16

示例 3：

输入：n = 3
输出：false

提示：

-231 <= n <= 231 - 1

• 进阶：你能够不使用循环/递归解决此问题吗？

AC:

classSolution{public:boolisPowerOfTwo(intn){if(n<=0)returnfalse;// 2 的幂的二进制表示中只有一个 1，// 所以 n & (n - 1) 应该等于 0return(n&(n-1))==0;}};

• 这是道很典型2的幂判断题型
• 至于为何能够判断？

解释如下：

2 的幂的二进制表示里，只有一个 1

1 -> 0001
2 -> 0010
4 -> 0100
8 -> 1000

发生了什么？

n - 1会把n最高位的那个1变成0
并把该位右边的所有低位0变成1

例如：

n=8(1000)n -1=7(0111)n&(n -1)=1000&0111=0000

对于任意只有一个1的数，n和n-1在那个位置上一定互斥，所以 按位与为0。

为什么不是其它数?

如果n不是2的幂，例如n = 6:

6 = 0110
5 = 0101
6 & 5 = 0100，不是 0

∵6有两个1，n-1只会清掉最右边的1，剩下的高位1仍然在结果中。
∴ 这个表达式的逻辑

n > 0
n 只有一个 1 位
n & (n - 1) 结果就是 0

因此(n & (n - 1)) == 0能返回true，表示n是2的幂。

附上官方题解