231. 2 的幂

题目描述

输入一个整数 n。

如果能找到某个整数 x，满足 n == 2^x，就说 n 是 2 的幂，此时返回 true；找不到时返回 false。

示例 1

输入：n = 1
输出：true

解释：2^0 = 1。

示例 2

输入：n = 16
输出：true

解释：2^4 = 16。

示例 3

输入：n = 3
输出：false

解释：没有整数 x 能让 2^x 等于 3。

进阶：能否不写循环、也不用递归就得出结果？

2 的幂在二进制中恰好只有一个 1（形如 100…0）。n - 1 会把这个 1 变成 0、把它右边的 0 全变成 1，于是 n & (n - 1) == 0。反之若 n 有两个及以上的 1，n & (n - 1) 只消掉最低的一个，结果仍非 0。再加上 n > 0 排除 0 和负数即可。

对正整数 n：n & (n - 1) 等于 n 去掉最低位的 1，因此结果为 0 当且仅当 n 只有一个 1。

时间 O(1)；空间 O(1)。

别漏掉 n > 0：0 & (-1) = 0 会被误判为 true；-2^31 在补码中也只有一个 1（符号位），同样必须靠 n > 0 排除。另外 & 的优先级低于 ==，C/Java/JS 中要给 n & (n - 1) 加括号。

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

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

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

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

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

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

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

三种方法都是 O(1)。n & (n - 1) 去掉最低位的 1，n & -n 取出最低位的 1，约数法则利用数论性质并依赖输入范围。

在补码表示下，n & -n 只保留 n 二进制中最低位的 1。n 是 2 的幂当且仅当它只有一个 1，也就是 n > 0 且 n & -n 等于 n。

和主解法一样是 O(1)。n & -n 这个“取最低位”技巧在树状数组中经常用到，值得一起掌握。

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

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

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

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

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

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

在 32 位有符号整数范围内，最大的 2 的幂是 2³⁰。2³⁰ 的约数只有 2 的幂，所以 n 是 2 的幂当且仅当 n > 0 且 2³⁰ 能被 n 整除。

不需要位运算，只用一次取模。依赖输入范围的上界，范围变化时要换常数。

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        BIG = 1 << 30
        return n > 0 and BIG % n == 0

class Solution {
    public boolean isPowerOfTwo(int n) {
        final int BIG = 1 << 30;
        return n > 0 && BIG % n == 0;
    }
}

class Solution {
public:
    bool isPowerOfTwo(int n) {
        const int BIG = 1 << 30;
        return n > 0 && BIG % n == 0;
    }
};

func isPowerOfTwo(n int) bool {
	const BIG = 1 << 30
	return n > 0 && BIG%n == 0
}

var isPowerOfTwo = function(n) {
    const BIG = 1 << 30;
    return n > 0 && BIG % n === 0;
};

function isPowerOfTwo(n: number): boolean {
    const BIG = 1 << 30;
    return n > 0 && BIG % n === 0;
}