2的幂

这道题出自LeetCode,题目如下:

给你一个整数 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

示例 4:

输入:n = 4
输出:true

示例 5:

输入:n = 5
输出:false

这道题有3种比较trick的解法。首先,如果一个整数它是2的幂次方,那么它的二进制表示必然为:

\[n = 1 \underbrace{0...0}_{k} \]

也就是它只有一个二进制位为1。那么问题显然可以转换为计算n的二进制位为1的数量,我们这里只需要判断是否数量为1即可,也就是去计算n & (n - 1)的值是否为0即可:

\[n = 1 \underbrace{0...0}_{k} \\ n - 1 = 0 \underbrace{1...1}_{k} \\ \]

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

第二种解法是计算n的最低二进制位为1的数是否与n相等。如果相等,说明n只有一个二进制位为1。计算n的最低二进制位为1的数的方法是去计算n & (-n)的值:

\[n = 1 \underbrace{0...0}_{k} \\ -n = 0 \underbrace{1..1}_k + 1 = 1 \underbrace{0...0}_{k} \]

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

最后还有一种比较取巧的做法,就是我们已知最大的2的幂的值为\(2^{30}=1073741824\),那么只要判断n是否为其约数即可:

class Solution {
private:
    static constexpr int BIG = 1 << 30;

public:
    bool isPowerOfTwo(int n) {
        return n > 0 && BIG % n == 0;
    }
};
上一篇:【LaTeX】函树


下一篇:Python使用Plotly绘图工具,绘制面积图