题目
给定一个整数,写一个函数来判断它是否是 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
}
}
复杂度分析
-
时间复杂度:
。
-
空间复杂度:
。
网友评论