从集合论到位运算，常见位运算技巧分类总结！¶
前言¶
本文将扫清位运算的迷雾，在集合论与位运算之间建立一座桥梁。
在高中，我们学了集合论（set theory）的相关知识。例如，包含若干整数的集合 。在编程中，通常用哈希表（hash table）表示集合。例如 Java 中的 HashSet，C++ 中的 std::unordered_set。
在集合论中，有交集\(\cap\) 、并集\(\cup\) 、包含于\(\subseteq\) 等等概念。如果编程实现「求两个哈希表的交集」，需要一个一个地遍历哈希表中的元素。那么，有没有效率更高的做法呢？
该二进制登场了。
集合可以用二进制表示，二进制从低到高第 i 位为 1 表示 i 在集合中，为 0 表示 i 不在集合中。例如集合 {0, 2, 3} 可以用二进制数 \(1101_{(2)}\) 表示；反过来，二进制数 \(1101_{(2)}\) 就对应着集合 {0, 2, 3}。
正式地说，包含非负整数的集合 S 可以用如下方式「压缩」成一个数字：
例如集合 {0, 2, 3} 可以压缩成 \(2^0 + 2^2 + 2^3 = 13\)，也就是二进制数 \(1101_{(2)}\) 。
利用位运算「并行计算」的特点，我们可以高效地做一些和集合有关的运算。按照常见的应用场景，可以分为以下四类：
- 集合与集合
- 集合与元素
- 遍历集合
- 枚举集合
一、集合与集合¶
其中 & 表示按位与，| 表示按位或，⨁ 表示按位异或，~ 表示按位取反。
两个集合的「对称差」是只属于其中一个集合，而不属于另一个集合的元素组成的集合，也就是不在交集中的元素组成的集合。
| 术语 | 集合 | 位运算 | 集合示例 | 位运算示例 |
|---|---|---|---|---|
| 交集 | \( A \cap B \) | a & b |
\(\{0, 2, 3\} \cap \{0, 1, 2\} = \{0, 2\}\) | 0b1101 (13) |
| 并集 | \( A \cup B \) | a \| b |
\(\{0, 2, 3\} \cup \{0, 1, 2\} = \{0, 1, 2, 3\}\) | 0b1101 (13) |
| 对称差 | \( A \Delta B \) | a ^ b |
\(\{0, 2, 3\} \Delta \{0, 1, 2\} = \{1, 3\}\) | 0b1101 (13) |
| 差 | \( A \setminus B \) | a & ~b |
\(\{0, 2, 3\} \setminus \{1, 2\} = \{0, 3\}\) | 0b1101 (13) |
| 差（子集） | \( A \setminus B, B \subseteq A \) | a ^ b |
\(\{0, 2, 3\} \setminus \{0, 2\} = \{3\}\) | 0b1101 (13) |
| 包含于 | \( A \subseteq B \) | (a & b) == a或 (a \| b) == b |
\(\{0, 2\} \subseteq \{0, 2, 3\}\) | 0b0101 (5) |
注 1：按位取反的例子中，仅列出最低 4 个比特位取反后的结果，即 0b00110 取反后是 ...1001（补码形式）。
注 2：包含于（判断子集）的两种位运算写法是等价的，在编程时只需判断其中任意一种。此外，还可以用 (a & ~b) == 0 判断，如果成立，也表示 A 是 B 的子集。
注 3：编程时，请注意运算符的优先级。例如 == 在某些语言中优先级比位运算更高。
二、集合与元素¶
通常会用到移位运算。
其中 << 表示左移，>> 表示右移。
注：左移 i 位相当于乘以 2^i，右移 i 位相当于除以 2^i。
| 术语 | 集合 | 位运算 | 集合示例 | 位运算示例 |
|---|---|---|---|---|
| 空集 | ∅ | 0 |
- | 0 |
| 单元素集合 | {i} | 1 << i |
{2} |
1 << 2 = 0b100 |
| 全集 | U | (1 << n) - 1 |
{0, 1, 2, 3} (n=4) |
(1 << 4) - 1 = 0b1111 |
| 补集 | U S | ((1 << n) - 1) ^ s |
- | - |
| 属于 | i ∈ S | (s >> i) & 1 |
检查 2 是否在 {0, 2, 3} 中 |
(0b1101 >> 2) & 1 = 1 |
| 不属于 | i ∉ S | ((s >> i) & 1) == 0 |
检查 1 是否不在 {0, 2, 3} 中 |
((0b1101 >> 1) & 1) == 0 |
| 添加元素 | S ∪ {i} | s \| (1 << i) |
{0, 2, 3} ∪ {1} = {0, 1, 2, 3} |
0b1101 \| (1 << 1) = 0b1111 |
| 删除元素 | S {i} | s & ~(1 << i) |
{0, 2, 3} \ {2} = {0, 3} |
0b1101 & ~(1 << 2) = 0b1001 |
| 删除元素（一定在集合中） | S {i} | s ^ (1 << i) |
{0, 2, 3} \ {2} = {0, 3} |
0b1101 ^ (1 << 2) = 0b1001 |
| 删除最小元素 | S {min(S)} | s & (s - 1) |
见下 | 见下 |
| s = 101100 | ||||
| s-1 = 101011 // 最低位的 1 变成 0，同时 1 右边的 0 都取反，变成 1 | ||||
| s&(s-1) = 101000 |
text
特别地，如果 n 是 2 的幂，那么 (n & (n - 1)) == 0。
此外，编程语言提供了一些和二进制有关的库函数，例如：
- 计算二进制中的 1 的个数，也就是集合大小；
- 计算二进制长度，减一后得到集合最大元素；
- 计算二进制尾零个数，也就是集合最小元素。
调用这些函数的时间复杂度都是 O(1)。
| 术语 | Python | Java | C++ | Go |
|---|---|---|---|---|
| 集合大小 | s.bit_count() |
Integer.bitCount(s) |
__builtin_popcount(s) |
bits.OnesCount(s) |
| 二进制长度 | s.bit_length() |
32-Integer.numberOfLeadingZeros(s) |
__lg(s)+1 |
bits.Len(s) |
| 集合最大元素 | s.bit_length()-1 |
31-Integer.numberOfLeadingZeros(s) |
__lg(s) |
bits.Len(s)-1 |
| 集合最小元素 | (s&-s).bit_length()-1 |
Integer.numberOfTrailingZeros(s) |
__builtin_ctz(s) |
bits.TrailingZeros(s) |
请特别注意 s=0 的情况。对于 C++ 来说，__lg(0) 和 __builtin_ctz(0) 是未定义行为。其他语言请查阅 API 文档。
此外，对于 C++ 的 long long，需使用相应的 __builtin_popcountll 等函数，即函数名后缀添加 ll（两个小写字母 L）。__lg 支持 long long。
特别地，只包含最小元素的子集，即二进制最低位的 1 及其后面的 0，也叫 lowbit，可以用 s & -s 算出。举例说明：
s = 101100
~s = 010011
(~s)+1 = 010100 // 根据补码的定义，这就是 -s => s 的最低 1 左侧取反，右侧不变
s & -s = 000100 // lowbit
text
三、遍历集合¶
设元素范围从 0 到 n-1，枚举范围中的元素 i，判断 i 是否在集合 s 中。
Python3 ```python for i in range(n): if (s >> i) & 1: # i 在 s 中 # 处理 i 的逻辑 也可以直接遍历集合 s 中的元素：不断地计算集合最小元素、去掉最小元素，直到集合为空。
Python3
python t = s while t: lowbit = t & -t t ^= lowbit i = lowbit.bit_length() - 1 # 处理 i 的逻辑 四、枚举集合 §4.1 枚举所有集合 设元素范围从 0 到 n-1，从空集 0 枚举到全集 (1 << n) - 1：
Python3
python for s in range(1 << n): # 处理 s 的逻辑 §4.2 枚举非空子集 设集合为 s，从大到小枚举 s 的所有非空子集 sub：
Python3
python sub = s while sub: # 处理 sub 的逻辑 sub = (sub - 1) & s 为什么要写成 sub = (sub - 1) & s 呢？
暴力做法是从 s 出发，不断减一，直到 0。但这样做，中途会遇到很多并不是 s 的子集的情况。例如 s=0b1011 时，减一得到 0b1010，这是 s 的子集。但再减一就得到 0b1001 了，这并不是 s 的子集，下一个子集应该是 0b1000。
把所有的合法子集按顺序列出来，会发现我们做的相当于「压缩版」的二进制减法，例如
如果忽略掉 0b1011 中的两个 0，数字的变化和二进制减法是一样的，即
如何快速跳到下一个子集呢？比如，怎么从 0b1010 跳到 0b1000？
普通的二进制减法，是 0b1010 - 1 = 0b1001，也就是把最低位的 1 变成 0，同时把最低位的 1 右边的 0 都变成 1。
压缩版的二进制减法也是类似的，对于 0b1010，也会把最低位的 1 变成 0，对于最低位的 1 右边的 0，并不是都变成 1，只有在 s 中的 0 才会变成 1。怎么做到？减一后 & s 就行，也就是 (0b1010 - 1) & 0b1011 = 0b1001 & 0b1011 = 0b1000。
§4.3 枚举子集（包含空集） 如果要从大到小枚举 s 的所有子集 sub（从 s 枚举到空集 0），可以这样写：
Python3
python sub = s while True: # 处理 sub 的逻辑 if sub == 0: break sub = (sub - 1) & s 其中 Java 和 C++ 的原理是，当 sub = 0 时（空集），再减一就得到 -1，对应的二进制为 ...1111，再 & s 就得到了 s。所以当循环到 sub == s 时，说明最后一次循环的 sub 是空集，s 的所有子集都枚举到了，退出循环。
注：还可以枚举全集 (1<