14-分享｜从集合论到位运算，常见位运算技巧分类总结！

本文由简悦 SimpRead 转码，原文地址 leetcode.cn

图：集合交、按位与之间存在某种联系。

前言

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

在高中，我们学了集合论（set theory）的相关知识。例如，包含若干整数的集合 S={0,2,3}。在编程中，通常用哈希表（hash table）表示集合。例如 Java 中的 HashSet，C++ 中的 std::unordered_set。

在集合论中，有交集 ∩、并集 ∪、包含于 ⊆ 等等概念。如果编程实现「求两个哈希表的交集」，需要一个一个地遍历哈希表中的元素。那么，有没有效率更高的做法呢？

该二进制登场了。

集合可以用二进制表示，二进制从低到高第 i 位为 1 表示 i 在集合中，为 0 表示 i 不在集合中。例如集合 {0,2,3} 可以用二进制数 1101(2) 表示；反过来，二进制数 1101(2) 就对应着集合 {0,2,3}。

正式地说，包含非负整数的集合 S 可以用如下方式「压缩」成一个数字：

f(S)=i∈S∑2i

例如集合 {0,2,3} 可以压缩成 20+22+23=13，也就是二进制数 1101(2)。

利用位运算「并行计算」的特点，我们可以高效地做一些和集合有关的运算。按照常见的应用场景，可以分为以下四类：

集合与集合
集合与元素
遍历集合
枚举集合

一、集合与集合

其中 & 表示按位与，∣ 表示按位或，⊕ 表示按位异或，∼ 表示按位取反。

两个集合的「对称差」是只属于其中一个集合，而不属于另一个集合的元素组成的集合，也就是不在交集中的元素组成的集合。

术语	集合	位运算	集合示例	位运算示例
交集	$A\cap B$ A∩B	$a\&b$ a&b	$\begin{aligned}&\{0,2,3\}\\\cap\ &\{0,1,2\}\\=\ &\{0,2\}\end{aligned}$ ∩ = {0,2,3}{0,1,2}{0,2}	$\begin{aligned}&1101\\\&\ &0111\\=\ &0101\end{aligned}$ & = 110101110101
并集	$A\cup B$ A∪B	$a\ \vert\ b$ a ∣ b	$\begin{aligned}&\{0,2,3\}\\\cup\ &\{0,1,2\}\\=\ &\{0,1,2,3\}\end{aligned}$ ∪ = {0,2,3}{0,1,2}{0,1,2,3}	$\begin{aligned}&1101\\\vert\ \ &0111\\=\ &1111\end{aligned}$ ∣ = 110101111111
对称差	$A\ \Delta\ B$ A Δ B	$a\oplus b$ a⊕b	$\begin{aligned}&\{0,2,3\}\\\Delta\ &\{0,1,2\}\\=\ &\{1,3\}\end{aligned}$ Δ = {0,2,3}{0,1,2}{1,3}	$\begin{aligned}&1101\\\oplus\ &0111\\=\ &1010\end{aligned}$ ⊕ = 110101111010
差	$A\setminus B$ A∖B	$a\&\sim b$ a&∼b	$\begin{aligned}&\{0,2,3\}\\\setminus\ &\{1,2\}\\=\ &\{0,3\}\end{aligned}$ ∖ = {0,2,3}{1,2}{0,3}	$\begin{aligned}&1101\\\&\ &1001\\=\ &1001\end{aligned}$ & = 110110011001
差（子集）	$A\setminus B,\ B\subseteq A$ A∖B, B⊆A	$a\oplus b$ a⊕b	$\begin{aligned}&\{0,2,3\}\\\setminus\ &\{0,2\}\\=\ &\{3\}\end{aligned}$ ∖ = {0,2,3}{0,2}{3}	$\begin{aligned}&1101\\\oplus\ &0101\\=\ &1000\end{aligned}$ ⊕ = 110101011000
包含于	$A\subseteq B$ A⊆B	$a\& b = a$ a&b=a $a\ \vert\ b = b$ a ∣ b=b	$\{0,2\}\subseteq \{0,2,3\}$ {0,2}⊆{0,2,3}	$0101\& 1101 = 0101$ 0101&1101=0101 $0101\ \vert\ 1101 = 1101$ 0101 ∣ 1101=1101

注 1：按位取反的例子中，仅列出最低 4 个比特位取反后的结果，即 0110 取反后是 1001。

注 2：包含于（判断子集）的两种位运算写法是等价的，在编程时只需判断其中任意一种。此外，还可以用 (a & ~b) == 0 判断，如果成立，也表示 A 是 B 的子集。

注 3：编程时，请注意运算符的优先级。例如 == 在某些语言中优先级比位运算更高。

二、集合与元素

通常会用到移位运算。

其中 << 表示左移，>> 表示右移。

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

术语	集合	位运算	集合示例	位运算示例
空集	$\varnothing$ ∅	$0$ 0
单元素集合	$\{i\}$ {i}	$1\ \texttt{<<}\ i$ 1 << i	$\{2\}$ {2}	$1\ \texttt{<<}\ 2$ 1 << 2
全集	$U=\{0,1,2,\cdots n-1\}$ U={0,1,2,⋯n−1}	$(1\ \texttt{<<}\ n) - 1$ (1 << n)−1	$\{0,1,2,3\}$ {0,1,2,3}	$(1\ \texttt{<<}\ 4)-1$ (1 << 4)−1
补集	$\complement_US = U\setminus S$ ∁US=U∖S	$((1\ \texttt{<<}\ n) - 1)\oplus s$ ((1 << n)−1)⊕s	$U=\{0,1,2,3\}$ U={0,1,2,3} $\complement_U \{1,2\} = \{0,3\}$ ∁U{1,2}={0,3}	$\begin{aligned}&1111\\\oplus\ &0110\\=\ &1001\end{aligned}$ ⊕ = 111101101001
属于	$i\in S$ i∈S	$(s\ \texttt{>>}\ i)\ \&\ 1 =1$ (s >> i) & 1=1	$2\in \{0,2,3\}$ 2∈{0,2,3}	$(1101\ \texttt{>>}\ 2)\ \&\ 1 =1$ (1101 >> 2) & 1=1
不属于	$i\notin S$ i∈/S	$(s\ \texttt{>>}\ i)\ \&\ 1 =0$ (s >> i) & 1=0	$1\notin\{0,2,3\}$ 1∈/{0,2,3}	$(1101\ \texttt{>>}\ 1)\ \&\ 1 =0$ (1101 >> 1) & 1=0
添加元素	$S\cup \{i\}$ S∪{i}	$s\ \vert\ (1\ \texttt{<<}\ i)$ s ∣ (1 << i)	$\{0,3\}\cup \{2\}$ {0,3}∪{2}	$1001\ \vert\ (1\ \texttt{<<}\ 2)$ 1001 ∣ (1 << 2)
删除元素	$S\setminus \{i\}$ S∖{i}	$s\&\sim (1\ \texttt{<<}\ i)$ s&∼(1 << i)	$\{0,2,3\}\setminus \{2\}$ {0,2,3}∖{2}	$1101\&\sim (1\ \texttt{<<}\ 2)$ 1101&∼(1 << 2)
删除元素（一定在集合中）	$S\setminus \{i\},\ i\in S$ S∖{i}, i∈S	$s\oplus (1\ \texttt{<<}\ i)$ s⊕(1 << i)	$\{0,2,3\}\setminus \{2\}$ {0,2,3}∖{2}	$1101\oplus (1\ \texttt{<<}\ 2)$ 1101⊕(1 << 2)
删除最小元素		$s\& (s-1)$ s&(s−1)		见下

      s = 101100
    s-1 = 101011 // 最低位的 1 变成 0，同时 1 右边的 0 都取反，变成 1
s&(s-1) = 101000

特别地，如果 s 是 2 的幂，那么 s&(s−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

三、遍历集合

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

Python3
Java
C++
Go

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

for (int i = 0; i < n; i++) {
    if (((s >> i) & 1) == 1) { // i 在 s 中
        // 处理 i 的逻辑
    }
}

for (int i = 0; i < n; i++) {
    if ((s >> i) & 1) { // i 在 s 中
        // 处理 i 的逻辑
    }
}

for i := 0; i < n; i++ {
    if s>>i&1 == 1 { // i 在 s 中
        // 处理 i 的逻辑
    }
}

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

Python3
Java
C++
Go

t = s
while t:
    lowbit = t & -t
    t ^= lowbit
    i = lowbit.bit_length() - 1
    # 处理 i 的逻辑

for (int t = s; t > 0; t &= t - 1) {
    int i = Integer.numberOfTrailingZeros(t);
    // 处理 i 的逻辑
}

for (int t = s; t; t &= t - 1) {
    int i = __builtin_ctz(t);
    // 处理 i 的逻辑
}

for t := uint(s); t > 0; t &= t - 1 {
    i := bits.TrailingZeros(t)
    // 处理 i 的逻辑
}

四、枚举集合

§4.1 枚举所有集合

设元素范围从 0 到 n−1，从空集 ∅ 枚举到全集 U：

Python3
Java
C++
Go

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

for (int s = 0; s < (1 << n); s++) {
    // 处理 s 的逻辑
}

for (int s = 0; s < (1 << n); s++) {
    // 处理 s 的逻辑
}

for s := 0; s < 1<<n; s++ {
    // 处理 s 的逻辑
}

§4.2 枚举非空子集

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

Python3
Java
C++
Go

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

for (int sub = s; sub > 0; sub = (sub - 1) & s) {
    // 处理 sub 的逻辑
}

for (int sub = s; sub; sub = (sub - 1) & s) {
    // 处理 sub 的逻辑
}

for sub := s; sub > 0; sub = (sub - 1) & s {
    // 处理 sub 的逻辑
}

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

暴力做法是从 s 出发，不断减一，直到 0。但这样做，中途会遇到很多并不是 s 的子集的情况。例如 s=10101 时，减一得到 10100，这是 s 的子集。但再减一就得到 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。怎么做到？减一后 & 10101 就行，也就是 (10100−1) & 10101=10001。

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

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

Python3
Java
C++
Go

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

int sub = s;
do {
    // 处理 sub 的逻辑
    sub = (sub - 1) & s;
} while (sub != s);

int sub = s;
do {
    // 处理 sub 的逻辑
    sub = (sub - 1) & s;
} while (sub != s);

for sub := s; ; {
    // 处理 sub 的逻辑
    sub = (sub - 1) & s
    if sub == s {
        break
    }
}

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

注：还可以枚举全集 U 的所有大小恰好为 k 的子集，这一技巧叫做 Gosper’s Hack，具体请看视频讲解。

§4.4 枚举超集

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

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

枚举 S，满足 S 是 T 的超集，也是全集 U={0,1,2,⋯,n−1} 的子集。

Python3
Java
C++
Go

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

for (int s = t; s < (1 << n); s = (s + 1) | t) {
    // 处理 s 的逻辑
}

for (int s = t; s < (1 << n); s = (s + 1) | t) {
    // 处理 s 的逻辑
}

for s := t; s < 1<<n; s = (s + 1) | t {
    // 处理 s 的逻辑
}

关联题单

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

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B 站 @灵茶山艾府

🪴 ped-Yc's Garden

探索

前言

一、集合与集合

二、集合与元素

三、遍历集合

四、枚举集合

§4.1 枚举所有集合

§4.2 枚举非空子集

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

§4.4 枚举超集

关联题单

分类题单

关系图谱

目录

反向链接

最近的笔记

index

todos

» 播客笔记工作流