跳转至

二进制集合操作

二进制集合操作

一个数的二进制表示可以看作是一个集合(\(0\) 表示不在集合中,\(1\) 表示在集合中)。比如集合 \(\{1,3,4,8\}\),可以表示成 \((100011010)_2\)。而对应的位运算也就可以看作是对集合进行的操作。

操作 集合表示 位运算语句
交集 \(a \cap b\) a & b
并集 \(a \cup b\) a | b
补集 \(\bar{a}\) ~a (全集为二进制都是 1)
差集 \(a \setminus b\) a & (~b)
对称差 \(a\triangle b\) a ^ b

在进一步介绍集合的子集遍历操作之前,先看位运算的有关应用例子。

模 2 的幂

一个数对 \(2\) 的非负整数次幂取模,等价于取二进制下一个数的后若干位,等价于和 \(mod-1\) 进行与操作。

C++
1
int modPowerOfTwo(int x, int mod) { return x & (mod - 1); }
Python
1
2
def modPowerOfTwo(x, mod):
    return x & (mod - 1)

于是可以知道,\(2\) 的非负整数次幂对它本身取模,结果为 \(0\),即如果 \(n\)\(2\) 的非负整数次幂,\(n\)\(n-1\) 的与操作结果为 \(0\)

事实上,对于一个正整数 \(n\)\(n-1\) 会将 \(n\) 的最低 \(1\) 位置零,并将后续位数全部置 \(1\)。因此,\(n\)\(n-1\) 的与操作等价于删掉 \(n\) 的最低 \(1\) 位。

借此可以判断一个数是不是 \(2\) 的非负整数次幂。当且仅当 \(n\) 的二进制表示只有一个 \(1\) 时,\(n\)\(2\) 的非负整数次幂。

C++
1
bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
Python
1
2
def isPowerOfTwo(n):
    return n > 0 and (n & (n - 1)) == 0

子集遍历

遍历一个二进制数表示的集合的全部子集,等价于枚举二进制数对应掩码的所有子掩码。

掩码是一串二进制码,用于和源码进行与运算,得到屏蔽源码的若干输入位后的新操作数。

掩码对于源码可以起到遮罩的作用,掩码中的 \(1\) 位意味着源码的相应位得到保留,掩码中的 \(0\) 位意味着源码的相应位进行置 \(0\) 操作。将掩码的若干 \(1\) 位改为 \(0\) 位可以得到掩码的子掩码,掩码本身也是自己的子掩码。

给定一个掩码 \(m\),希望有效迭代 \(m\) 的所有子掩码 \(s\),可以考虑基于位运算技巧的实现。

C++
1
2
3
4
5
6
// 降序遍历 m 的非空子集
int s = m;
while (s > 0) {
  // s 是 m 的一个非空子集
  s = (s - 1) & m;
}

或者使用更紧凑的 for 语句:

C++
1
2
3
// 降序遍历 m 的非空子集
for (int s = m; s; s = (s - 1) & m)
// s 是 m 的一个非空子集

这两段代码都不会处理等于 \(0\) 的子掩码,要想处理等于 \(0\) 的子掩码可以使用其他办法,例如:

C++
1
2
3
4
5
// 降序遍历 m 的子集
for (int s = m;; s = (s - 1) & m) {
  // s 是 m 的一个子集
  if (s == 0) break;
}

接下来证明,上面的代码访问了所有 \(m\) 的子掩码,没有重复,并且按降序排列。

假设有一个当前位掩码 \(s\),并且想继续访问下一个位掩码。在掩码 \(s\) 中减去 \(1\),等价于删除掩码 \(s\) 中最右边的设置位,并将其右边的所有位变为 \(1\)

为了使 \(s-1\) 变为新的子掩码,需要删除掩码 \(m\) 中未包含的所有额外的 \(1\) 位,可以使用位运算 \((s-1)\&m\) 来进行此移除。

这两步操作等价于切割掩码 \(s-1\),以确定算术上可以取到的最大值,即按降序排列的 \(s\) 之后的下一个子掩码。

因此,该算法按降序生成该掩码的所有子掩码,每次迭代仅执行两个操作。

特殊情况是 \(s=0\)。在执行 \(s-1\) 之后得到 \(-1\),其中所有位都为 \(1\)。在 \((s-1)\&m\) 操作之后将得到新的 \(s\) 等于 \(m\)。因此,如果循环不以 \(s=0\) 结束,算法的循环将无法终止。

使用 \(\text{popcount}(m)\) 表示 \(m\) 二进制中 \(1\) 的个数,用这种方法可以在 \(O(2^{\text{popcount}(m)})\) 的时间复杂度内遍历集合 \(m\) 的子集。

遍历所有掩码的子掩码

在使用掩码动态编程的问题中,有时会希望对于每个掩码,遍历掩码的所有子掩码:

C++
1
2
3
4
for (int m = 0; m < (1 << n); ++m)
  // 降序遍历 m 的非空子集
  for (int s = m; s; s = (s - 1) & m)
// s 是 m 的一个非空子集

这样做可以遍历大小为 \(n\) 的集合的每个子集的子集。

接下来证明,该操作的时间复杂度为 \(O(3^n)\)\(n\) 为掩码总共的位数,即集合中元素的总数。

考虑第 \(i\) 位,即集合中第 \(i\) 个元素,有三种情况:

  • 在掩码 \(m\) 中为 \(0\),因此在子掩码 \(s\) 中为 \(0\),即元素不在大小子集中。
  • \(m\) 中为 \(1\),但在 \(s\) 中为 \(0\),即元素只在大子集中,不在小子集中。
  • \(m\)\(s\) 中均为 \(1\),即元素同时在大小子集中。

总共有 \(n\) 位,因此有 \(3^n\) 个不同的组合。

还有一种证明方法是:

如果掩码 \(m\) 具有 \(k\)\(1\),那么它有 \(2^k\) 个子掩码。对于给定的 \(k\),对应有 \(C_n^k\) 个掩码 \(m\),那么所有掩码的总数为:

\[ \sum_{k=0}^n C_n^k 2^n \]

上面的和等于使用二项式定理对 \((1+2)^n\) 的展开,因此有 \(3^n\) 个不同的组合。

参考资料

本页面主要译自博文 Перебор всех подмасок данной маски 与其英文翻译版 Submask Enumeration。其中俄文版版权协议为 Public Domain + Leave a Link;英文版版权协议为 CC-BY-SA 4.0。

习题