题目
给定一个整数，写一个函数来判断它是否是 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
}
}
复杂度分析
时间复杂度：
空间复杂度：
