位运算与集合-当前滚动

2023-06-16 16:24:58
来源：博客园

前言在刷LeetCode的时候，我们常常碰到需要枚举同时选择几个元素，或者

前言

在刷 LeetCode 的时候，我们常常碰到需要枚举同时选择几个元素，或者说枚举选择一个集合的情况，即同时选择 $\lbrace0, 1, 2\rbrace$ 或者 $\lbrace0, 1,3\rbrace$ 等，这里集合中的数字表示要选择的元素的索引。

通常情况下，我们往往会使用哈希表来表示集合，好处在于可以方便的在 $O(1)$ 时间内确定元素是否处于集合中，坏处则是当我们需要做集合之间的运算，例如求交集或者并集，那么就需要 $O(n)$ 时间才能实现；另一个缺陷就是，当递归函数的可变实参中存在哈希表（或者对哈希表的引用）时，无法通过添加 $cach$ 数组实现记忆化搜索。

(相关资料图)

于是，我们需要想一个新的办法来表示集合，由于集合可以由全集（包含所有元素的集合）中每个元素的选或者不选来表示，因此，很容易联想到二进制上每一位的 $0$ 和 $1$，例如 $101 = 5$ 表示集合中只有第 $0$ 个元素和第 $2$ 个元素。

使用数学化一点的语言，即集合可以以如下方式压缩成二进制下的一个数字：

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

其中 $i$ 表示集合中的元素在原数组中的索引。$\lbrace a[0], a[1], a[3]\rbrace$ 即可由 $2^0+2^1+2^3 = 13$ 即二进制数 $1101$ 表示。

集合与元素

根据上面提到的二进制表示集合的方法，我们可以在 $O(1)$ 的时间内实现集合与元素之间的运算。

具体运算表格参见灵神的从集合论到位运算，常见位运算技巧分类总结！。无需记忆，自己做题的时候很容易就能推导出来。

集合与集合

集合与集合之间的运算也可以在用二进制数表示集合的情况下，在 $O(1)$ 时间内完成计算。

具体运算表格同样参见灵神的从集合论到位运算，常见位运算技巧分类总结！。

同样无需记忆，自己做题的时候很容易就能推导出来。

遍历集合

在集合用二进制数 $mask$ 表示的情况下，集合中的元素个数可以由 C++ 库函数 __builtin_popcount(mask)计算出来。

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

for (int i = 0; i < n; ++i) {    if ((s >> i) & 1) { // i 在 s 中，注意 == 运算优先级高于 &        //     }}

枚举集合

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

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

暴力的枚举集合的办法是从 $s$ 出发，不断减一直到 $0$，但是这样中途会有很多并不是 $s$ 的子集的情况。

假设集合 $s = 10101$，那么它的子集从大到小依次为：

$$\lbrace 10101, 10100, 10001, 10000, 00101, 00100, 00001\rbrace$$

如果忽略掉 $10101$ 中间的两个 $0$，即忽略第一位和第三位的 $0$（位索引从 $0$ 开始），那么它的子集的数字变化与普通的二进制减法是一样的，即：

$$\lbrace 111, 110, 101, 100, 011, 010, 001\rbrace$$

因此，当我们执行 $(mask - 1)$ & $s$ 时，以 $10100$ 为例，相当于强制跳过了 $10100$ 到 $10001$ 中间那些第一位和第三位数字不为 $0$ 的数。

套用灵神的说法，以 $10100$ 为例，普通的二进制减法会把最低位的 $1$ 变成 $0$，把这个最低位的 $1$ 右边的 $0$ 都变成 $1$，即 $10100\rightarrow 10011$，我们这个压缩版的二进制减法，也是把最低位的 $1$ 变成 $0$，但对这个最低位的 $1$ 右边的 $0$，并不会全都变成 $1$，而是只保留 $s = 10101$ 中存在的 $1$，其他的会依旧是 $0$。

Gosper"s Hack

Gosper"s Hack 算法是生成 $n$ 元集合中所有包含 $k$ 个元素的子集的算法。

这里先给出 Gosper"s Hack 算法的代码

while (x < uplimit) {    int lowbit = x & (-x);    int left = x + lowbit;    int right = ((x ^ (x + lowbit)) / lowbit) >> 2;    x = left | right;}

接下来讲一下 Gopser"s Hack 算法的思想：

对一个二进制数，例如 $110110$，我们需要找到它从左往右的最后一个 $01$，然后把这个 $01$ 变成 $10$，再把它右边的 $1$ 全部集中到最右边（这里右边的 $1$ 显然都是连续的，否则与最后一个 $01$ 矛盾），即 $110110\rightarrow 111001$。

在举了例子之后，Gosper"s Hack 算法的思想其实很好理解。

我们利用 $x + lowbit(x)$ 得到的结果，就是将 $x$ 的第一个 $01$ 变成 $0$，同时右边的数全都变成 $0$，即 $110110\rightarrow 111000$，如果我们使用 $x \oplus (x + lowbit(x))$，即可得到 $x$ 从最后一个 $01$ 起的右边的数，即 $110110\rightarrow 001110$，我们再除以 $lowbit$，即可去掉 $x \oplus (x + lowbit(x))$ 的最右边的连续的 $0$，又因为 $x + lowbit(x)$ 会将这个最后一个的 $01$ 变成 $10$，$01 \oplus 10 = 11$，因此 $(x \oplus(x + low)) / lowbit(x)$ 的 $1$ 的个数比 $x$ 的最后一个 $01$ 的右边的 $1$ 的个数还多了 $2$ 个，于是我们再右移两位，即得到了我们需要 $right$。