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

本文非原创，转载自灵茶山艾府，具体出处见文章底部

前言

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

在高中，我们学了集合论（set theory）的相关知识。例如，包含若干帧数的集合 $S=\left\{ 0,2,3 \right\}$。在编程中，通常用哈希表（hash table）实现集合，例如 Java 中的 HashSet，Golang 中的 map。

在集合论中，有交集 $ \cap$、并集 $\cup$、包含于 $\subseteq$ 等等概念。如何编程实现「求两个哈希表的交集」，需要一个个遍地遍历哈希表中的元素。有没有更高效的做法呢？

该二进制上场了。

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

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

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

上面举例的 ${0,2,3}$ 可以压缩成 $2^0+2^2+2^3=13$，也就是二进制数 1101。

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

1. 集合与集合
2. 集合与元素
3. 遍历集合
4. 枚举集合

一、集合与集合

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

其中「对称差」指仅在其中一个集合的元素。

术语	集合	位运算	举例	二进制
交集	$A \cap B$	$a \& b$	$\left\{ 0,2,3 \right\} \cap \left\{ 0,1,2 \right\} = \left\{ 0,2 \right\}$	$1101 \& 0111 = 0101$
并集	$A \cup B$	$a | b$	$\left\{ 0,2,3 \right\} \cup \left\{ 0,1,2 \right\} = \left\{ 0,1,2,3 \right\}$	$1101
对称差	$A\triangle B$	$a \oplus b$	$\left\{ 0,2,3 \right\} \triangle \left\{ 0,1,2 \right\} = \left\{ 1,3 \right\}$	$1101\oplus0111 = 1010$
差	$A \backslash B$	$a\& \sim b$	$\left\{ 0,2,3 \right\} \backslash \left\{ 1,2 \right\} = \left\{ 0,3 \right\}$	$1101 \& 1001 = 1001$
差（子集）	$A \backslash B(B \subseteq A)$	$a \oplus b$	$\left\{ 0,2,3 \right\} \backslash \left\{ 0,2 \right\} = \left\{ 3 \right\}$	$1101 \oplus 0101 = 1000$
包含于	$A \subseteq B$	$a \& b = a$ $a | b = a$	$\left\{ 0,2 \right\} \subseteq \left\{ 0,2,3 \right\}$	$0101 \&1101=0101$ $0101 | 1101 = 1101$

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

注2：包含于的两周运算写法是等价的，再编程时只需要判断其中任意一种。

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

二、集合与元素

通常会用到位移计算

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

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

术语	集合	位运算	举例	二进制
空集	$\emptyset$	0
单元素合集	$\left\{ i \right\}$	$1 << i$	$\left\{ 2 \right\}$	$1<<2$
全集	$U=\left\{ 0,1,2,...n-1 \right\}$	$(1 << n)-1$	$\left\{ 0,1,2,3 \right\}$	$(1<<4)-1$
补集	$\complement_U S = U \backslash S$	$\sim S$ 或者 $((1 << n) - 1) \oplus s$
属于	$i \in S$	$(s >> i)\& 1 =1$	$2 \in \left\{ 0,2,3 \right\}$	$(1101 >> 2) \& 1 = 1$
不属于	$i \notin S$	$(s >> i) \& 1 = 0$	$1 \notin \left\{ 0,2,3 \right\}$	$(1101 >> 2) \& 1 = 0$
添加元素	$S \cup \left\{ i \right\}$	$s	(1 << i)$	$\left{ 0,3 \right} \cup \left{2 \right} $
删除元素	$S \backslash \left\{ i \right\}$	$s\&\sim(1 << i)$	$\left{ 0,2,3 \right} \backslash \left{2 \right} $	$1101 \& \sim (1<<2)$
删除元素（一定在集合中）	$S\backslash\left\{i\right\}(i \in S)$	$s\oplus(1 << i)$	$\left{ 0,2,3 \right} \backslash \left{2 \right} $	$1101 \oplus(1 << 2)$
删除最小元素		$s\&(s-1)$		见下

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

此外，某些数字可以借助标准库的函数算出：

术语	Python	Java	C++	Go
集合大小（元素个数）	s.bit_count()	Integer.bitcount(s)	__builtin_popount(s)	bits.OnesCount(s)
二进制长度（减一得到集合中的最大元素）	s.bit_length()	32-Integer.numberOfLeadingZeros(s)	32-__builtin_clz(s)	bits.Len(s)
集合中的最小元素	(s&-s).bit_length()-1	Integer.numberOfTrailingZeros(s)	__builtin_ctz(s)	bits.TrailingZeros(s)

特别地，只包含最小元素的子集，即二进制最低 1 及其后面的 0，也叫 lowbit，可以用 s & -s 算出。举例说明：

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

三、遍历集合

设元素范围从 $0$ 到 $n-1$，挨个判断元素是否在集合 $s$ 中：

PythonJavaC++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 的逻辑
    }
}

四、枚举集合

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

PythonJavaC++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 的逻辑
}

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

PythonJavaC++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 \rightarrow 10100 \rightarrow 10001 \rightarrow 10000 \rightarrow 00101 \rightarrow ...$$

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

$$111 \rightarrow 110 \rightarrow 101 \rightarrow 100 \rightarrow 011 \rightarrow ...$$

如何快速找到下一个子集呢？以 $10100 \rightarrow 10001$ 为例说明，普通的二进制减法会把最低位的 $1$ 变成 $0$，同时 $1$ 右边的 $0$ 全部变成 $1$，即 $10100 \rightarrow 10011$。「压缩版」的二进制减法也是类似的，把最低位的 $1$ 变成 $0$，但同时对于 $1$ 右边的 $0$，只保留在 $s = 10101$ 中的 $1$，所以是 $10100 \rightarrow 10001$。怎么保留？ $\& 10101$ 就行

但同时对于 $1$ 右边的 $0$，只保留在 $s = 10101$ 中的 $1$

意思是，把 $10100$ 的最低位 $1$ 变 $0$，它的后面有两位 $00$，都是 $0$，这时候按照普通二进制，会把这两个 $00$ 变成 $11$，如果按照压缩版，就是把原来集合中有的 $1$ 变成 $1$（因为求的是子集），其余的还是 $0$，原有的集合是$10101$，最后两位是 $01$，所以只保留 $01$。综合起来就是 $10100$ 先变成 $10000$，然后保留 $01$，变成 $10001$（按照作者的说法，应该是对于 $10101$，只有最后一位存在值，所以最后一位取反，$0 \rightarrow 1$，所以 $10100$ 先变成 $10000$，然后最后一位取反）。

这样做的效果是从 $10100$ 直接跳到了 $10001$，把中间的 $10011$ 和 $10010$ 忽略掉了（普通减法的顺序是：$10100 \rightarrow 10011 \rightarrow 10010 \rightarrow 10001$），因为 $10011$ 和 $10010$ 不是有效子集

作者：roylx
链接：https://leetcode.cn/circle/discuss/CaOJ45/view/gj5DL2/

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

PythonJavaC++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$ 时说明最后一次循环式空集，退出循环。

注：还可以枚举全集 $U$ 的所有大小恰好为 $k$ 的子集，这一技巧叫做 Gosper’s Hack，具体见作者B站的讲解【力扣双周赛 86】Gosper’s Hack | 单调队列 | LeetCode 算法刷题

练习

用位运算完成如下题目：

• 78.子集

• 77.组合

• 46.全排列
  然后是一些状态压缩 DP。这类题目通常和排列/子集有关，可以先从暴力回溯开始思考，再过渡到记忆化搜索和递推。

• 2172.数组的最大与和，题解

• 1125.最小的必要团队，题解

• 2305.公平分发饼干，题解

• 1494.并行课程 II，题解

• LCP 53.守护太空城，题解

• 1879.两个数组最小的异或值之和

• 1986.完成任务的最少工作时间段

更多题目，可以在题库中同时选上「动态规划」和「位运算」这两个标签：链接。