判断一个数字是否为2的幂

思路

首先需要区分开 2^N 和 2N。2N 很好判断，直接看数字能否被2整除即可。如果想用类似 2N 的思路去判别 2^N，可能就需要递归计算 N=N/2。

不过借助二进制表示的性质，可以简化 2^N 的判别。

假设一个正整数 val 的表示形式为1XX...X。

• 假如它是2的幂，val 的表示形式必然是 100...0，并且 val-1 的表示形式会是 011..1。则有 val & (val-1) == 0

• 假如它不是2的幂， val 的表示形式会是 1XX...X，它的末尾数字中至少有一位为1, 则 val-1 无需借最开始的1，val-1 表示形式会是 1XX...X。则有 val & (val-1) != 0

而任意一个正整数 val 要么是2的幂，要么不是2的幂，上面讨论已经概括了所有的正整数。

上述两个命题的逆否命题分别为：

对于一个正整数 val：

• 假如 val & (val-1) != 0，则它不是2的幂
• 假如 val & (val-1) == 0，则它是2的幂

代码

bool isPowOf2(int val) {
    // == 优先级高于 &
    return (val & (val - 1)) == 0;
}