跳转至

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\) 移除，若移除后为 \(0\)，说明 \(n\) 是 \(2\) 的幂。

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
6
7
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function (n) {
    return n > 0 && (n & (n - 1)) == 0;
};

方法二：lowbit

\(\texttt{n\&(-n)}\) 可以得到 \(n\) 的最后一位 \(1\) 表示的十进制数，若与 \(n\) 相等，说明 \(n\) 是 \(2\) 的幂。

注意：要满足 \(n\) 是 \(2\) 的幂次方，需要保证 \(n\) 大于 \(0\)。

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 - 1)) === 0;
}

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

评论