二进制枚举

一句话理解

二进制枚举：用 0 到 2^n-1 表示所有开关组合。

为什么要学

n≤20 的子集暴力。

讲解

for (int s=0; s<(1<<n); s++) 枚举。第 i 位表示元素 i 在不在。

比递归写起来短，调试也直观。

例子

for (int s = 0; s < (1 << n); s++) {
    for (int i = 0; i < n; i++)
        if (s >> i & 1) { /* 用 i */ }
}

外层每个子集，内层看哪些元素被选。

常见错误

• n=31 用 int 的 1<<n 溢出。
• 忘记 1LL。