leetcode-231

231. 2 的幂

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

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

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

输入：n = 3
输出：false

输入：n = 5
输出：false

解法

解法1

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        ret = 0
        if n < 0:
            return False
        while n:
            ret += n&1
            n = n>>1

        return True if ret  == 1 else False

解法二：官方题解

一个数 $n$ 是 $2$ 的幂，当且仅当 $n$ 是正整数，并且 $n$ 的二进制表示中仅包含 1 个 1。

因此我们可以考虑使用位运算，将 $n$ 的二进制表示中最低位的那个 $1$ 提取出来，再判断剩余的数值是否为 $0$ 即可。下面介绍两种常见的与「二进制表示中最低位」相关的位运算技巧。

第一个技巧是
$$
n & (n - 1)
$$
其中 $&$ 表示按位与运算。该位运算技巧可以直接将 $n$ 二进制表示的最低位 $1$ 移除，它的原理如下：

假设 $n$ 的二进制表示为$( a 10 \cdots 0 )_2$，其中$a$表示若干个高位，$1$表示最低位那个$1$，$0\cdots 0$表示后面的若干个0，那么$n-1$的二进制表示为：
$$
(a01\cdots 1)_2
$$
我们将$(a10\cdots 1)_2$与$(a01\cdots 1)_2$进行按位与运算，高位$a$不变，在这之后的所有位都会变为0，这样就将最低位的那个1移除了。

因此，如果$n$是正整数并且$n & ( n - 1 ) = 0$，那么$n$就是$2$的幂。

第二个技巧：
$$
n&(-n)
$$
其中 $-n$ 是 $n$ 的相反数，是一个负数。该位运算技巧可以直接获取 $n$ 二进制表示的最低位的 1。

由于负数是按照补码规则在计算机中存储的，$-n$ 的二进制表示为 $n$ 的二进制表示的每一位取反再加上 $1$，因此它的原理如下：

假设$n$的二进制表示为$(a10\cdots 0)2$，其中$a$表示若干个高位，$1$表示最低位那个$1$，$0\cdots 0$表示后面的若干个0，那么$-n$的二进制表示为：
$$
( \bar { a } 01 \cdots 1 ) 2 + ( 1 ) 2 = ( \bar { a } 10 \cdots 0 ) 2
$$
其中,$\bar{a}$表示将$a$每一位取反。我们将$( a 10 \cdots 0 ) 2$与$( \bar { a } 10 \cdots 0 ) _2$进行按位与运算，高位全部变为 0，最低位的 1 以及之后的所有 0 不变，这样我们就获取了 $n$ 二进制表示的最低位的 1。

因此，如果$n$的正整数并且$n&(-n)=n$，那么$n$就是2的幂。

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & -n) == n