跳转至

# 二进制集合操作

前置知识：位运算、整数与位序列．

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

操作 | 集合表示 | 位运算表示
--- | --- | ---
交集 | 𝑎 ∩𝑏 a∩b | 𝑎 A N D⁡𝑏 a AND⁡b
并集 | 𝑎 ∪𝑏 a∪b | 𝑎 O R⁡𝑏 a OR⁡b
补集 | ¯𝑎 a¯ | N O T⁡𝑎 NOT⁡a（全集为二进制都是 1）
差集 | 𝑎 ∖𝑏 a∖b | 𝑎 A N D⁡N O T⁡𝑏 a AND⁡NOT⁡b
对称差 | 𝑎△𝑏 a△b | 𝑎 X O R⁡𝑏 a XOR⁡b

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

### 模 2 的幂

一个数对 2 2 的非负整数次幂取模，等价于取二进制下一个数的后若干位，等价于和 𝑚 𝑜 𝑑 −1 m o d−1 进行与操作．

C++Python

    1
    int modPowerOfTwo(int x, int mod) { return x & (mod - 1); }

    1
    2
    def modPowerOfTwo(x, mod):
        return x & (mod - 1)

于是可以知道，2 2 的非负整数次幂对它本身取模，结果为 0 0，即如果 𝑛 n 是 2 2 的非负整数次幂，𝑛 n 和 𝑛 −1 n−1 的与操作结果为 0 0．

事实上，对于一个正整数 𝑛 n，𝑛 −1 n−1 会将 𝑛 n 的最低 1 1 位置零，并将后续位数全部置 1 1．因此，𝑛 n 和 𝑛 −1 n−1 的与操作等价于删掉 𝑛 n 的最低 1 1 位．

借此可以判断一个数是不是 2 2 的非负整数次幂．当且仅当 𝑛 n 的二进制表示只有一个 1 1 时，𝑛 n 为 2 2 的非负整数次幂．

C++Python

    1
    bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }

    1
    2
    def isPowerOfTwo(n):
        return n > 0 and (n & (n - 1)) == 0

### 子集遍历

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

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

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

给定一个掩码 𝑚 m，希望有效迭代 𝑚 m 的所有子掩码 𝑠 s，可以考虑基于位运算技巧的实现．

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

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

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

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

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

接下来证明，上面的代码访问了所有 𝑚 m 的子掩码，没有重复，并且按降序排列．

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

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

这两步操作等价于切割掩码 𝑠 −1 s−1，以确定算术上可以取到的最大值，即按降序排列的 𝑠 s 之后的下一个子掩码．

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

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

使用 p o p c o u n t(𝑚)popcount(m) 表示 𝑚 m 二进制中 1 1 的个数，用这种方法可以在 𝑂(2 p o p c o u n t(𝑚))O(2 popcount(m)) 的时间复杂度内遍历集合 𝑚 m 的子集．

### 遍历所有掩码的子掩码

在使用状压 DP 的问题中，有时会希望对于每个掩码，遍历掩码的所有子掩码：

    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 的集合的每个子集的子集．

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

考虑第 𝑖 i 位，即集合中第 𝑖 i 个元素，有三种情况：

- 在掩码 𝑚 m 中为 0 0，因此在子掩码 𝑠 s 中为 0 0，即元素不在大小子集中．
- 在 𝑚 m 中为 1 1，但在 𝑠 s 中为 0 0，即元素只在大子集中，不在小子集中．
- 在 𝑚 m 和 𝑠 s 中均为 1 1，即元素同时在大小子集中．

总共有 𝑛 n 位，因此有 3 𝑛 3 n 个不同的组合．

还有一种证明方法是：

如果掩码 𝑚 m 具有 𝑘 k 个 1 1，那么它有 2 𝑘 2 k 个子掩码．对于给定的 𝑘 k，对应有 (𝑛 𝑘)(n k) 个掩码 𝑚 m，那么所有掩码的总数为：

𝑛∑𝑘=0(𝑛 𝑘)2 𝑘∑k=0 n(n k)2 k

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

### 参考资料

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

### 习题

- Atcoder - Close Group
- Codeforces - Nuclear Fusion
- Codeforces - Sandy and Nuts
- UVa 1439 - Exclusive Access 2
- UVa 11825 - Hackers' Crackdown

> 本页面最近更新：2026/1/27 12:26:08，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Tiphereth-A, aofall, arielherself, c-forrest, gavinliu266, Great-designer, hhc0001, jol888, Menci, shawlleyw, TOMWT-qwq, ZnPdCo
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用