快速判断n是否为2的幂

实现方案（C）： n > 0 && (n & (n - 1)) == 0

判断一个数是否为 2 的幂，利用的是 2 的幂在二进制中的特殊形式。

2 的幂的二进制特征

n	二进制	说明
1	0001	只有 1 个 1
2	0010	只有 1 个 1
4	0100	只有 1 个 1
8	1000	只有 1 个 1
16	0001 0000	只有 1 个 1

规律：2 的幂的二进制表示中恰好只有一个位是 1，其余全为 0。

n - 1 的二进制特征

当 n 是 2 的幂时，n-1 的二进制会将那个唯一的 1 变成 0，并将其右侧所有低位的 0 变成 1。

例如：

n   = 8 = 1000
n-1 = 7 = 0111

n   = 4 = 0100
n-1 = 3 = 0011

n   = 16 = 0001 0000
n-1 = 15 = 0000 1111

按位与运算的结果

将 n 和 n-1 做按位与：

  1000   (8)
& 0111   (7)
--------
  0000   (0)

由于 n 中唯一的 1 在 n-1 中变成了 0，且其他位也完全不同，按位与的结果一定是 0。

所以 (n & (n-1)) == 0 可以判断 n 是否为 2 的幂。

为什么要加上 n > 0？

• 当 n = 0 时，0 & (-1) 在二进制中：

  0000 & 1111 = 0000
  

  结果也是 0，但 0 不是 2 的幂，所以必须排除 n = 0。
• 当 n 是负数时，例如 -8，其补码表示中可能有很多 1，(n & (n-1)) 不一定为 0，但为了严格正确，我们限定 n > 0（2 的幂必须是正整数）。
  ※ 补码表示法的使用，参见有符号整数的补码表示法。

举例验证

是 2 的幂的情况

n = 8  →  8 & 7 = 1000 & 0111 = 0000 → 是
n = 16 → 16 & 15 = 10000 & 01111 = 00000 → 是

不是 2 的幂的情况

n = 6  →  6 & 5 = 0110 & 0101 = 0100 (≠0) → 不是
n = 10 → 10 & 9 = 1010 & 1001 = 1000 (≠0) → 不是
n = 12 → 12 & 11 = 1100 & 1011 = 1000 (≠0) → 不是

其他实现方式

也可以这样写：

bool is_power_of_2(int n) {
    if (n <= 0) return false;
    while (n % 2 == 0) n /= 2;
    return n == 1;
}

但位运算版本时间复杂度 O(1)，且效率更高。

总结

(n & (n - 1)) == 0 的本质是：

• 2 的幂只有一个 1 位；
• 减 1 后该位变 0，低位全变 1；
• 两者按位与后必然为 0。