Swift - LeetCode - 2 的幂
题目
给你一个整数 ，请你判断该整数是否是
的幂次方。如果是，返回
true；否则，返回 false。
如果存在一个整数 使得
，则认为
是
的幂次方。
示例 1：
- 输入：
n = 1- 输出：
true- 解释：
= 1
示例 2：
- 输入：
n = 16- 输出：
true- 解释：
= 16
示例 3：
- 输入：
n = 3- 输出：
false
示例 4：
- 输入：
n = 4- 输出：
true
方法一：二进制表示
思路及解法
一个数 是 2 的幂，当且仅当
是正整数，并且
的二进制表示中仅包含 1 个 1。
因此我们可以考虑使用位运算，将 的二进制表示中最低位的那个 1 提取出来，再判断剩余的数值是否为 0 即可。下面介绍两种常见的与「二进制表示中最低位」相关的位运算技巧。
第一个技巧是
其中 表示按位与运算。该位运算技巧可以直接将
二进制表示的最低位
移除，它的原理如下：
假设
的二进制表示为
，其中
表示若干个高位，
表示最低位的那个 1，
表示后面的若干个
，那么
的二进制表示为：
我们将
进行按位与运算，高位
因此，如果 是正整数并且
，那么
就是
的幂。
第二个技巧是
其中 是
的相反数，是一个负数。该位运算技巧可以直接获取
二进制表示的最低位的
。
由于负数是按照补码规则在计算机中存储的， 的二进制表示为
的二进制表示的每一位取反再加上
，因此它的原理如下：
假设
表示后面的若干个
的二进制表示为：
其中
表示将
进行按位与运算，高位全部变为
因此，如果 是正整数并且
，那么
就是
的幂。
代码
class Solution {
func isPowerOfTwo(_ n: Int) -> Bool {
return n > 0 && (n & (n - 1)) == 0
}
}
class Solution {
func isPowerOfTwo(_ n: Int) -> Bool {
return n > 0 && (n & -n) == n
}
}
复杂度分析
-
时间复杂度：
。
-
空间复杂度：
方法二：判断是否为最大 2 的幂的约数
思路及解法
除了使用二进制表示判断之外，还有一种较为取巧的做法。
在题目给定的 位有符号整数的范围内，最大的
的幂为
。我们只需要判断
是否是
的约数即可。
代码
class Solution {
func isPowerOfTwo(_ n: Int) -> Bool {
let BIG = 1 << 30
return n > 0 && BIG % n == 0
}
}
复杂度分析
-
时间复杂度：
-
空间复杂度：
