跳转至

231. 2 的幂

题目描述

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

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

 

示例 1：

输入：n = 1
输出：true
解释：20 = 1

示例 2：

输入：n = 16
输出：true
解释：24 = 16

示例 3：

输入：n = 3
输出：false

 

提示：

  • -231 <= n <= 231 - 1

 

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

解法

方法一：位运算

根据位运算的性质，执行 \(\texttt{n\&(n-1)}\) 可以消去二进制形式的 \(n\) 的最后一位 \(1\)。因此，如果 \(n \gt 0\)，并且满足 \(\texttt{n\&(n-1)}\) 结果为 \(0\)，则说明 \(n\) 是 \(2\) 的幂。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

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

1
2
3
4
5
class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

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

1
2
3
func isPowerOfTwo(n int) bool {
    return n > 0 && (n&(n-1)) == 0
}

1
2
3
function isPowerOfTwo(n: number): boolean {
    return n > 0 && (n & (n - 1)) === 0;
}

1
2
3
4
5
impl Solution {
    pub fn is_power_of_two(n: i32) -> bool {
        n > 0 && (n & (n - 1)) == 0
    }
}

1
2
3
4
5
6
7
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function (n) {
    return n > 0 && (n & (n - 1)) == 0;
};

方法二：Lowbit

根据 \(\text{lowbit}\) 的定义，我们知道 \(\text{lowbit}(x) = x \& (-x)\)，可以得到 \(n\) 的最后一位 \(1\) 表示的十进制数。因此，如果 \(n > 0\)，并且满足 \(\text{lowbit}(n)\) 等于 \(n\)，则说明 \(n\) 是 \(2\) 的幂。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

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

1
2
3
4
5
class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && n == (n & (-n));
    }
}

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

1
2
3
func isPowerOfTwo(n int) bool {
    return n > 0 && n == (n&(-n))
}

1
2
3
function isPowerOfTwo(n: number): boolean {
    return n > 0 && n === (n & -n);
}

1
2
3
4
5
impl Solution {
    pub fn is_power_of_two(n: i32) -> bool {
        n > 0 && n == (n & (-n))
    }
}

1
2
3
4
5
6
7
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function (n) {
    return n > 0 && n === (n & -n);
};

评论