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

本文转载自力扣讨论区，作者：灵茶山艾府（endlesscheng）。原文链接：https://leetcode.cn/circle/discuss/CaOJ45/

位运算入门位运算教程位运算技巧力扣位运算leetcode位运算灵茶山艾府灵神

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

前言

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

在高中，我们学了集合论（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)}$ 。

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

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

一、集合与集合

其中 $&$ 表示按位与， $|$ 表示按位或， $\oplus$ 表示按位异或， $\sim$ 表示按位取反。

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

术语	集合	位运算	集合示例	位运算示例
交集	$A \cap B$	$a & b$	$\begin{aligned} {0, 2, 3} \\ \cap & {0, 1, 2} \\ = & {0, 2} \end{aligned}$	$\begin{aligned} 1101 \\ & & 0111 \\ = & 0101 \end{aligned}$
并集	$A \cup B$	$a \| b$	$\begin{aligned} {0, 2, 3} \\ \cup & {0, 1, 2} \\ = & {0, 1, 2, 3} \end{aligned}$	$\begin{aligned} 1101 \\ \| & 0111 \\ = & 1111 \end{aligned}$
对称差	$A Δ B$	$a \oplus b$	$\begin{aligned} {0, 2, 3} \\ Δ & {0, 1, 2} \\ = & {1, 3} \end{aligned}$	$\begin{aligned} 1101 \\ \oplus & 0111 \\ = & 1010 \end{aligned}$
差	$A ∖ B$	$a & \sim b$	$\begin{aligned} {0, 2, 3} \\ ∖ & {1, 2} \\ = & {0, 3} \end{aligned}$	$\begin{aligned} 1101 \\ & & 1001 \\ = & 1001 \end{aligned}$
差（子集）	$A ∖ B, B \subseteq A$	$a \oplus b$	$\begin{aligned} {0, 2, 3} \\ ∖ & {0, 2} \\ = & {3} \end{aligned}$	$\begin{aligned} 1101 \\ \oplus & 0101 \\ = & 1000 \end{aligned}$
包含于	$A \subseteq B$	$a & b = a$ $a \| b = b$	${0, 2} \subseteq {0, 2, 3}$	$0101 & 1101 = 0101$ $0101 \| 1101 = 1101$

注 1：按位取反的例子中，仅列出最低 $4$ 个比特位取反后的结果，即 $0110$ 取反后是 $1001$ 。
注 2：包含于（判断子集）的两种位运算写法是等价的，在编程时只需判断其中任意一种。此外，还可以用 (a & ~b) == 0 判断，如果成立，也表示 $A$ 是 $B$ 的子集。
注 3：编程时，请注意运算符的优先级。例如 == 在某些语言中优先级比位运算更高。

二、集合与元素

通常会用到移位运算。

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

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

术语	集合	位运算	集合示例	位运算示例
空集	$\emptyset$	$0$
单元素集合	${i}$	$1 << i$	${2}$	$1 << 2$
全集	$U = {0, 1, 2, \dots, n - 1}$	$(1 << n) - 1$	${0, 1, 2, 3}$	$(1 << 4) - 1$
补集	$∁_{U} S = U ∖ S$	$((1 << n) - 1) \oplus s$	$U = {0, 1, 2, 3}$ $∁_{U} {1, 2} = {0, 3}$	$\begin{aligned} 1111 \\ \oplus & 0110 \\ = & 1001 \end{aligned}$
属于	$i \in S$	$(s >> i) & 1 = 1$	$2 \in {0, 2, 3}$	$(1101 >> 2) & 1 = 1$
不属于	$i \notin S$	$(s >> i) & 1 = 0$	$1 \notin {0, 2, 3}$	$(1101 >> 1) & 1 = 0$
添加元素	$S \cup {i}$	$s \| (1 << i)$	${0, 3} \cup {2}$	$1001 \| (1 << 2)$
删除元素	$S ∖ {i}$	$s & \sim (1 << i)$	${0, 2, 3} ∖ {2}$	$1101 & \sim (1 << 2)$
删除元素（一定在集合中）	$S ∖ {i}, i \in S$	$s \oplus (1 << i)$	${0, 2, 3} ∖ {2}$	$1101 \oplus (1 << 2)$
删除最小元素		$s & (s - 1)$		见下

java

      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 算出。举例说明：

java

     s = 101100
    ~s = 010011
(~s)+1 = 010100 // 根据补码的定义，这就是 -s  =>  s 的最低 1 左侧取反，右侧不变
s & -s = 000100 // lowbit

三、遍历集合

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

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

java

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

cpp

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$ 中的元素：不断地计算集合最小元素、去掉最小元素，直到集合为空。

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

java

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

cpp

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$ ，从空集 $\emptyset$ 枚举到全集 $U$ ：

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

java

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

cpp

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

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

§4.2 枚举非空子集

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

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

java

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

cpp

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 \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$ 。怎么做到？减一后 $& 10101$ 就行，也就是 $(10100 - 1) & 10101 = 10001$ 。

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

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

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

java

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

cpp

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

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

其中 Java 和 C++ 的原理是，当 $sub = 0$ 时（空集），再减一就得到 $- 1$ ，对应的二进制为 $111 \dots 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, \dots, n - 1}$ 的子集。

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

java

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

cpp

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站@灵茶山艾府

数据结构

数据库

离散数学

数字电路

概率论

数学建模

软件工程

面向对象程序设计

Python 与数据分析

计算机组成

操作系统

计算机网络

编译原理

图形学

自然语言处理

Linux 实验

分布式系统

Internet原理与技术

BlogWeb

Stars Saying

黑马商城

苍穹外卖

黑马点评

黑马商城单体版

JavaWeb AI Tlias

RuoYi DKD

LinkQwen

InterX

LeetCode Agent Lab

00-预备知识

01-PR1108-逐代码段解析

02-PR1135-Cube化逐代码段解析

03-两个Bug深度剖析

04-开发心得与数值性能实测

01-PR1169-模型推理性能优化

02-PR1194-固定Shape及分档推理适配

NumPy

PyTorch

Python 八股文

LeetCUDA

LeetGPU

Triton

前言 ​

一、集合与集合 ​

二、集合与元素 ​

三、遍历集合 ​

四、枚举集合 ​

§4.1 枚举所有集合 ​

§4.2 枚举非空子集 ​

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

§4.4 枚举超集 ​

练习 ​

分类题单 ​

前言

一、集合与集合

二、集合与元素

三、遍历集合

四、枚举集合

§4.1 枚举所有集合

§4.2 枚举非空子集

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

§4.4 枚举超集

练习

分类题单