集合论&位运算的算法应用

xor 作者：灵茶山艾府 发布时间：2023.06.16

前言

本文将扫清位运算的迷雾，在集合论与位运算之间建立一座桥梁。

在高中，我们学了集合论（set theory）的相关知识。例如，包含若干整数的集合 $S = \{0, 2, 3\}$ 。在编程中，通常用哈希表（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$ 可以用如下方式「压缩」成一个数字：

$f(S) = \sum\_{i \in S} 2^i$

例如集合 $\{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\}$
并集	$A \cup B$	`a \| b`	$\{0, 2, 3\} \cup \{0, 1, 2\} = \{0, 1, 2, 3\}$
对称差	$A \triangle B$	`a ^ b`	$\{0, 2, 3\} \triangle \{0, 1, 2\} = \{1, 3\}$
差集	$A \setminus B$	`a & ~b`	$\{0, 2, 3\} \setminus \{1, 2\} = \{0, 3\}$
差集 (子集)	$A \setminus B, B \subseteq A$	`a ^ b`	$\{0, 2, 3\} \setminus \{0, 2\} = \{3\}$
包含于	$A \subseteq B$	`(a & b) == a` 或 `(a \| b) == b`	$\{0, 2\} \subseteq \{0, 2, 3\}$

二、集合与元素

通常会用到移位运算。其中 << 表示左移，>> 表示右移。

注：左移 $i$ 位相当于乘以 $2^i$ ，右移 $i$ 位相当于除以 $2^i$ 。

术语	集合	位运算	说明/示例
空集	$\varnothing$	`0`
单元素集合	$\{i\}$	`1 << i`
全集	$U = \{0, 1, \dots, n-1\}$	`(1 << n) - 1`
补集	$\complement_U S = U \setminus S$	`((1 << n) - 1) ^ s`	也就是全集异或 $S$
属于	$i \in S$	`(s >> i) & 1 == 1`
不属于	$i \notin S$	`(s >> i) & 1 == 0`
添加元素	$S \cup \{i\}$	`s \| (1 << i)`
删除元素	$S \setminus \{i\}$	`s & ~(1 << i)`
删除元素 (一定在集合中)	$S \setminus \{i\}, i \in S$	`s ^ (1 << i)`
删除最小元素		`s & (s - 1)`	最低位的 1 变成 0

特别说明 s & (s - 1)：

s   = 101100
s-1 = 101011  // 最低位的 1 变成 0，同时右边的 0 都变成 1
s & (s-1) = 101000 // 结果：最低位的 1 被移除了

特别地，如果 $s$ 是 $2$ 的幂，那么 s & (s - 1) == 0。

库函数支持

编程语言提供了一些和二进制有关的库函数，调用这些函数的时间复杂度都是 $O(1)$ 。

术语	Python	Java	C++ (GCC/Clang)
集合大小 (1 的个数)	`s.bit_count()`	`Integer.bitCount(s)`	`__builtin_popcount(s)`
集合最大元素 (二进制长度 -1)	`s.bit_length() - 1`	`32 - Integer.numberOfLeadingZeros(s) - 1`	`31 - __builtin_clz(s)`
集合最小元素 (尾零个数)	`(s & -s).bit_length() - 1`	`Integer.numberOfTrailingZeros(s)`	`__builtin_ctz(s)`

注意：

请特别注意 $s=0$ 的情况。对于 C++ 来说，__builtin_clz(0) 和 __builtin_ctz(0) 是未定义行为。其他语言请查阅 API 文档。

对于 C++ 的 long long，需使用相应的 __builtin_popcountll 等函数（后缀添加 ll）。__lg 支持 long long。

Lowbit：只包含最小元素的子集，即二进制最低 1 及其后面的 0，可以用 s & -s 算出。原理：~s + 1 即为 -s (补码定义)。 s & -s = 101100 & 010100 = 000100。

三、遍历集合

设元素范围从 $0$ 到 $n-1$ ，枚举范围中的元素 $i$ ，判断 $i$ 是否在集合 $s$ 中。

# Python3
for i in range(n):
    if (s >> i) & 1:
        # i 在 s 中，处理 i 的逻辑
        pass

也可以直接遍历集合 $s$ 中的元素：不断地计算集合最小元素、去掉最小元素，直到集合为空。

# Python3 (通用逻辑)
t = s
while t:
    lowbit = t & -t
    t ^= lowbit  # 去掉最低位的 1
    i = lowbit.bit_length() - 1  # 获取元素数值
    # 处理 i 的逻辑

四、枚举集合

§4.1 枚举所有集合

设元素范围从 $0$ 到 $n-1$ ，从空集 $\varnothing$ 枚举到全集 $U$ ：

for s in range(1 << n):
    # 处理 s 的逻辑
    pass

§4.2 枚举非空子集

设集合为 $s$ ，从大到小枚举 $s$ 的所有非空子集 $sub$ ：

sub = s
while sub:
    # 处理 sub 的逻辑
    sub = (sub - 1) & s

为什么要写成 sub = (sub - 1) & s 呢？

暴力做法是从 $s$ 出发，不断减一，直到 $0$ 。但这会遇到很多并不是 $s$ 的子集的情况。

例如 $s = 10101$ 时，减一得到 $10100$ ，这是 $s$ 的子集。但再减一就得到 $10011$ 了，这并不是 $s$ 的子集（最高位变了），下一个子集应该是 $10001$ 。

把所有的合法子集按顺序列出来，会发现我们做的相当于**「压缩版」的二进制减法**。

例如 $10101 \to 10100 \to 10001 \to 10000 \to 00101 \to \dots$

如果忽略掉 $10101$ 中的两个 $0$ ，数字的变化和二进制减法是一样的：

$111 \to 110 \to 101 \to 100 \to 011 \to \dots$

如何快速跳到下一个子集呢？ 比如，怎么从 $10100$ 跳到 $10001$ ？

普通的二进制减法： $10100 - 1 = 10011$ 。也就是把最低位的 $1$ 变成 $0$ ，同时把最低位的 $1$ 右边的 $0$ 都变成 $1$ 。
压缩版的二进制减法：对于 $10100 \to 10001$ ，也会把最低位的 $1$ 变成 $0$ ，但对于最低位 $1$ 右边的 $0$ ，并不是都变成 $1$ ，只有在 $s = 10101$ 中的 $1$ 才会变成 $1$ 。

怎么做法？减一后 按位与 $s$ 就行，也就是 (sub - 1) & s。

$(10100 - 1) \& 10101 = 10011 \& 10101 = 10001$ 。

§4.3 枚举子集（包含空集）

如果要从大到小枚举 $s$ 的所有子集 $sub$ （从 $s$ 枚举到空集 $\varnothing$ ），可以这样写：

sub = s
while True:
    # 处理 sub 的逻辑
    if sub == 0:
        break
    sub = (sub - 1) & s

其中 Java 和 C++ 的原理是，当 sub = 0 时（空集），再减一就得到 $-1$ ，对应的二进制为 $111\dots1$ ，再 & s 就得到了 $s$ 。所以当循环到 $sub = s$ 时，说明最后一次循环的 $sub = 0$ （空集）的所有子集都枚举到了，退出循环。

注：还可以枚举全集 $U$ 的所有大小恰好为 $k$ 的子集，这一技巧叫做 Gosper’s Hack。

§4.4 枚举超集

如果 $T$ 是 $S$ 的子集，那么称 $S$ 是 $T$ 的超集（superset）。

枚举超集的原理和上文枚举子集是类似的，这里通过或运算保证枚举的集合 $s$ 一定包含集合 $t$ 中的所有元素。

枚举 $s$ ，满足 $s$ 是 $t$ 的超集，也是全集 $U = \{0, 1, \dots, n-1\}$ 的子集。

s = t
while s < (1 << n):
    # 处理 s 的逻辑
    s = (s + 1) | t

练习

完成位运算题单的第一章。

其他关联题单：

数据结构题单中的「前缀异或和」
动态规划题单中的「状压 DP」

整理自灵茶山艾府的分享