231. 2的幂

Easy

题目描述

给你一个整数 n，如果 n 是 2 的幂次方，则返回 true；否则，返回 false。

如果存在一个整数 x 使得 n == 2^x，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1
输出：true
解释：2^0 = 1

示例 2：

输入：n = 16
输出：true
解释：2^4 = 16

示例 3：

输入：n = 3
输出：false

提示：

• -2^31 <= n <= 2^31 - 1

进阶： 你能够不使用循环/递归解决此问题吗？

解题思路

这道题有多种解法，我们来分析几种常见方法：

方法一：位运算（推荐） 这是最优雅的解法。观察2的幂次方的二进制特点：

• 2^0 = 1 → 二进制：1
• 2^1 = 2 → 二进制：10
• 2^2 = 4 → 二进制：100
• 2^3 = 8 → 二进制：1000

可以发现，2的幂次方在二进制中只有一个1。利用位运算技巧：n & (n-1) 可以消除最右边的1。如果n是2的幂，消除唯一的1后结果应该是0。

方法二：循环除法 不断除以2，检查是否能整除，最终结果是否为1。

方法三：数学方法 使用对数函数，检查log₂(n)是否为整数。

方法四：预计算 由于int范围有限，2的幂次方只有32个，可以预先计算所有值。

位运算方法时间复杂度O(1)，空间复杂度O(1)，是最优解。

代码实现

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0

public class Solution {
    public bool IsPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

var isPowerOfTwo = function(n) {
    return n > 0 && (n & (n - 1)) === 0;
};

复杂度分析

相关题目

• . Number of 1 Bits (Easy)

• . Power of Three (Easy)

• . Power of Four (Easy)