前言
本文将扫清位运算的迷雾，在集合论与位运算之间建立一座桥梁。
在高中，我们学了集合论（set theory）的相关知识。例如，包含若干整数的集合 S={0,2,3}。在编程中，通常用哈希表（hash table）表示集合。例如 Java 中的 HashSet，C++ 中的 std::unordered_set。
在集合论中，有交集 ∩、并集 ∪、包含于 ⊆等等概念。如果编程实现「求两个哈希表的交集」，需要一个一个地遍历哈希表中的元素。那么，有没有效率更高的做法呢？
该二进制登场了。
集合可以用二进制表示，二进制从低到高第 i 位为 1表示 i 在集合中，例如集合{0,2,3}可以用二进制1101表示；反过来，1101就对应集合{0,2,3}。正式地说，包含非负整数的集合S可以用以下方式压缩成一个数字：
例如集合{0,2,3}可以压缩成也就是二进制的1101。
利用位运算「并行计算」的特点，我们可以高效地做一些和集合有关的运算。按照常见的应用场景，可以分为以下四类：
- 集合与集合
- 集合与元素
- 遍历集合
- 枚举集合
一、集合与集合
其中 & 表示按位与，∣ 表示按位或，⊕ 表示按位异或，∼ 表示按位取反。
两个集合的「对称差」是只属于其中一个集合，而不属于另一个集合的元素组成的集合，也就是不在交集中的元素组成的集合。
| 术语 | 集合 | 位运算 | 集合示例 | 位运算示例 |
|---|---|---|---|---|
| 交集 | A∩B | a&b | {0,2,3}∩{0,1,2} = {0,2} | 1101 & 0111 = 0101 |
| 并集 | A∪B | a ∣ b | {0,2,3}∪{0,1,2} = {0,1,2,3} | 1101 | 0111 = 1111 |
| 对称差 | A Δ B | a⊕b | {0,2,3}Δ{0,1,2} = {1,3} | 1101 ⊕ 0111 = 1010 |
| 差 | A\B | a&∼b | {0,2,3}\{1,2} = {0,3} | 1101 & 1001 = 1001 |
二、集合与元素
通常会用到移位运算。
其中 << 表示左移，>> 表示右移。
| 术语 | 集合 | 位运算 | 集合示例 | 位运算示例 |
|---|---|---|---|---|
| 空集 | ∅ | 0 | ||
| 单元素集合 | {i} | 1<<i | {2} | 1<<2 |
| 全集 | U={0,1,2,⋯n−1} | (1<<n)-1 | {0,1,2,3} | (1<<4)-1 |
| 补集 | CuS=U\S | ((1<<n)-1)⊕s | U={0,1,2,3} Cu{1,2}={0,3} | 1111 ⊕ 0110 = 1001 |
| 属于 | (s >> i) & 1=1 | (1101 >> 2) & 1=1 | ||
| 不属于 | (s >> i) & 1=0 | (1101 >> 1) & 1=0 | ||
| 添加元素 | S∪{i} | s | (1<<i) | {0,3}∪{2} | 1001 ∣ (1 << 2) |
| 删除元素 | S \ {i} | s&∼(1 << i) | {0,2,3}\{2} | 1101&∼(1 << 2) |
特别地，如果 𝑠 是 2 的幂，那么 𝑠 &( 𝑠 − 1) =0。
此外，编程语言提供了一些和二进制有关的库函数，例如：
- 计算二进制中的 1 的个数，也就是集合大小；
- 计算二进制长度，减一后得到集合最大元素；
- 计算二进制尾零个数，也就是集合最小元素。
三、遍历集合
设元素范围从0到n-1，挨个判断每个元素是否在集合s中
for (int i = 0; i < n; i++) {
if ((s >> i) & 1) { // i 在 s 中
// 处理 i 的逻辑
}
}
四、枚举集合
枚举所有集合
设元素范围从 0 到 n−1，从空集 ∅ 枚举到全集 U：
for (int s = 0; s < (1 << n); s++) {
// 处理 s 的逻辑
}枚举非空子集
设集合为 𝑠，从大到小枚举 𝑠 的所有非空子集 sub：
for (int sub = s; sub; sub = (sub - 1) & s) {
// 处理 sub 的逻辑
}为什么要写成 sub = (sub - 1) & s 呢？
暴力做法是从s开始，不断减一，直到0但这样做，中途会遇到很多不是s的子集的情况。例如s=10101时，减1得到10100，这是s的子集，但是再减1就得到10011了。这并不是s的子集。下一个子集应该是10001。
把所有的合法子集按顺序列出来，会发现我们做的相当于「压缩版」的二进制减法，例如
10101→10100→10001→10000→00101→⋯
如果忽略掉 10101 中的两个 0，数字的变化和二进制减法是一样的，即
111→110→101→100→011→⋯
如何快速跳到下一个子集呢？比如，怎么从 10100 跳到 10001？
- 普通的二进制减法，是10100-1=10011，也就是把最低位的1变成0，对于最低位的1右边的0都变成1。
- 压缩版的二进制减法也是类似的，对于10100->10001,也会把最低位的1变成0，对于最低位的1右边的0，并不是都变成1，只有在s=10101中的1才会变成1。怎么做到？减1后&10101就行，也就是（10100-1）&10101 = 10001
枚举子集（包含空集）
如果要从大到小枚举 𝑠 的所有子集 sub（从 𝑠 枚举到空集 ∅），可以这样写：
int sub = s;
do {
// 处理 sub 的逻辑
sub = (sub - 1) & s;
} while (sub != s);原理是当sub=0时（空集），再减1就得到-1，对应的二进制位111...1，在&s就得到了s，所以循环到sub=s时，说明最后一次循环sub=0（空集），s的所有子集都枚举到了。退出循环。
