0342. 4的幂

0342. 4的幂 #

  • 标签:位运算
  • 难度:简单

题目大意 #

给定一个整数 n,判断 n 是否是 4 的幂次方,如果是的话,返回 True。不是的话,返回 False。

解题思路 #

通过循环可以直接做。但有更好的方法。

n 如果是 4 的幂次方,那么 n 肯定是 2 的幂次方,2 的幂次方二进制表示只含有一个 1,可以通过 n & (n - 1) 将 n 的最后位置上 的 1 置为 0,通过判断 n 是否满足 n & (n - 1) == 0 来判断 n 是否是 2 的幂次方。

若根据上述判断,得出 n 是 2 的幂次方,则可以写为:$n = x^{2k}$ 或者 $n = x^{2k+1}$。如果 n 是 4 的幂次方,则 $n = 2^{k}$。

下面来看一下 $2^{2x}、2^{2x}+1$ 的情况:

  • $(2^{2x} % 3) = (4^x % 3) = ((3+1)^x % 3) == 1$
  • $(2^{2x+1} % 3) = ((24^x) % 3) = ((2(3+1)^x) % 3) == 2$

则如果 n % 3 == 1,则 n 为 4 的幂次方。

代码 #

1
2
3
class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & (n-1)) == 0 and (n-1) % 3 == 0
本站总访问量  次  |  您是本站第  位访问者