题目

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

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

示例 1：

• 输入： n = 16
• 输出： true

示例 2：

• 输入： n = 5
• 输出： false

示例 3：

• 输入： n = 1
• 输出： true

提示：

• -231 <= n <= 231 - 1

前言

如果 是 的幂，那么 一定也是 的幂。因此我们可以首先判断 是否是 的幂，在此基础上再判断 是否是 的幂。

判断 是否是 的幂可以参考 2的幂的题解。由于这一步的方法有很多种，在下面的题解中，我们使用

这一方法进行判断。

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

思路及解法

如果 是 的幂，那么 的二进制表示中有且仅有一个 ，并且这个 出现在从低位开始的第偶数个二进制位上（这是因为这个 后面必须有偶数个 ）。这里我们规定最低位为第 位，例如 时， 的二进制表示为

唯一的 出现在第 个二进制位上，因此 是 的幂。

由于题目保证了 是一个 位的有符号整数，因此我们可以构造一个整数 ，它的所有偶数二进制位都是 ，所有奇数二进制位都是 。这样一来，我们将 和 进行按位与运算，如果结果为 ，说明 二进制表示中的 出现在偶数的位置，否则说明其出现在奇数的位置。

根据上面的思路， 的二进制表示为：

我们也可以将其表示成 进制的形式，使其更加美观：

代码

class Solution {
    func isPowerOfFour(_ n: Int) -> Bool {
        return n > 0 && n & (n - 1) == 0 && n % 3 == 1
    }
}

复杂度分析

• 时间复杂度：。

• 空间复杂度：。

方法二：取模性质

思路及解法

如果 是 的幂，那么它可以表示成 的形式，我们可以发现它除以 的余数一定为 ，即：

如果 是 的幂却不是 的幂，那么它可以表示成 的形式，此时它除以 的余数一定为 。

因此我们可以通过 除以 的余数是否为 来判断 是否是 的幂。

代码

class Solution {
    func isPowerOfFour(_ n: Int) -> Bool {
        return n > 0 && n & (n - 1) == 0 && n & 0xaaaaaaaa == 0
    }
}

复杂度分析

• 时间复杂度：。

• 空间复杂度：。