leetcode-342

342. 4的幂

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 $n == 4^x$。

示例

输入：n = 16
输出：true

输入：n = 5
输出：false

输入：n = 1
输出：true

解法

解法1

取两位余数，取完以后左移两位。

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

解法2：官方题解

如果 $n$是 $4$ 的幂，那么 $n$ 一定也是 $2$ 的幂。因此我们可以首先判断 $n$ 是否是 $2$ 的幂，在此基础上再判断 $n$ 是否是 $4$ 的幂。在下面的题解中使用n&(n-1)这一形式进行判断。

方法一：二进制表示中 1 的位置

如果 $n$ 是 $4$ 的幂，那么 $n$ 的二进制表示中有且仅有一个 $1$，并且这个 $1$ 出现在从低位开始的第偶数个二进制位上（这是因为这个 $1$ 后面必须有偶数个 $0$）。这里我们规定最低位为第$0$位，例如$n=16$时，$n$的二进制表示为：
$$
(10000)_2
$$
唯一的 1 出现在第 4 个二进制位上，因此 $n$ 是 4 的幂。

由于题目保证了 $n$ 是一个 $32$ 位的有符号整数，因此我们可以构造一个整数 $mask$，它的所有偶数二进制位都是 $0$，所有奇数二进制位都是 $1$。

这样一来，我们将$n$和$mask$进行按位与运算，如果结果为$0$，说明$n$二进制表示中的$1$出现在偶数位置，否则说明其出现在奇数的位置。

根据上面的思路，$mask$的二进制表示为：
$$
mask= ( 10101010101010101010101010101010 )_2
$$
我们也可以将其表示成$16$进制的形式，使其更加美观：
$$
mask== ( \text { AAAAAAAA } )_16
$$

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