题目

给你一个整数 ，请你判断该整数是否是 的幂次方。如果是，返回 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
    }
}

复杂度分析

• 时间复杂度：。

• 空间复杂度：。