二进制与集合

1 一位二进制，记录一个元素

假设我们只关心 $n$ 个元素，给它们编号 $0,1,\ldots,n-1$，组成全集 $U$。对于 $U$ 的任意子集 $A$，用一个二进制整数 a 表示它：

• 第 $i$ 位是 $1$：元素 $i$ 在集合 $A$ 中。
• 第 $i$ 位是 $0$：元素 $i$ 不在集合 $A$ 中。

位的编号从右往左，从 $0$ 开始。 例如，全集 $U=\{0,1,2,3,4\}$，集合 $A=\{0,2,3\}$ 可以表示成：

1
2
3

元素编号    4 3 2 1 0
是否存在    0 1 1 0 1
二进制      0b01101

对应的整数是 $2^0+2^2+2^3=13$。这种表示集合的整数通常叫作位掩码，也常用于状态压缩。

空集对应 0；只含元素 $i$ 的集合对应 1ULL << i；全集对应低 $n$ 位全为 $1$ 的整数。

这里存储的是元素是否存在，无法直接记录重复次数。若元素原本是字母、物品或顶点，先给它们分配统一的编号；不同集合必须使用同一套编号，才能进行位运算。

前置知识：[ Rbook: 二进制]

2 集合运算为什么能变成位运算

判断一个元素是否属于运算结果，只需要看它在两个集合中是否存在。对应到二进制，就是只看这一位的两个值。

这正好分别是按位或、按位与、按位与取反、按位异或的规则。因此，对整个整数做一次位运算，就同时完成了所有元素的判断。

其中 full 表示全集，本文始终假定 a、b 的全集范围外各位均为 $0$。

2.1 用同一个例子算一遍

取 $A=\{0,2,3\}$，$B=\{1,2,3\}$：

1
2
3
4
5
6
7
8

a          01101    {0, 2, 3}
b          01110    {1, 2, 3}

a | b      01111    {0, 1, 2, 3}    并集
a & b      01100    {2, 3}          交集
a & ~b     00001    {0}             A 去掉 B
b & ~a     00010    {1}             B 去掉 A
a ^ b      00011    {0, 1}          对称差

差集有方向，a & ~b 与 b & ~a 通常不同。

3 子集判断：三种等价写法

$A\subseteq B$ 的意思是：$A$ 中的每一个元素都在 $B$ 中。 注意方向，是判断 a 是否被 b 包含。

3.1 并进去没有增加元素

如果 $A$ 的元素本来就在 $B$ 中，把 $A$ 并入 $B$ 后，$B$ 不会改变：

1

(a | b) == b

例如 $A=\{0,2\}$、$B=\{0,1,2\}$：

1
2
3

a          00101
b          00111
a | b      00111    与 b 相等，说明 a 没有带来新元素

3.2 交集保留了全部元素

如果 $A$ 的元素全部在 $B$ 中，取交集时就不会丢掉 $A$ 中的任何元素：

1

(a & b) == a

3.3 找不到“在 A 中、不在 B 中”的元素

要否定 $A\subseteq B$，只需找到一个在 $A$ 中却不在 $B$ 中的元素。这些元素组成的集合就是差集 $A\setminus B$。

因此，差集为空，就说明没有这样的反例：

1

(a & ~b) == 0

例如 $A=\{0,3\}$、$B=\{0,1,2\}$：

1
2
3

a          01001
b          00111
a & ~b     01000    找到了元素 3，所以 A 不是 B 的子集

这三种判断完全等价：

1
2
3

bool subset1 = ((a | b) == b);
bool subset2 = ((a & b) == a);
bool subset3 = ((a & ~b) == 0);

选择哪一种，取决于你想表达什么：“没有新增”“全部保留”或“没有缺失”。

3.4 子集与真子集

本文用 $\subseteq$ 表示允许相等的子集关系，用 $\subsetneq$ 表示真子集关系。

$A$ 是 $B$ 的真子集，还需要 $A\ne B$：

1

((a & b) == a) && (a != b)

空集是任何集合的子集；一个集合也是自身的子集。所以上面的三种子集判断，在 a == 0 或 a == b 时都应当成立。

4 常用集合判断速查

“有公共元素”与“包含全部元素”是不同的要求。例如 $A=\{0\}$、$B=\{0,1\}$，(a & b) != 0 成立，但 $A$ 并没有包含 $B$。

5 单个元素的查询、加入与删除

元素 $i$ 对应只有第 $i$ 位为 $1$ 的掩码：

1

auto bit = 1ULL << i;

重复加入不会增加元素个数；删除一个不存在的元素也不会改变集合。这与普通集合的行为一致。

^ 表示切换，不能无条件用来删除元素。只有已知 $i\in A$ 时，a ^= bit 才与删除等价。

6 补集必须先确定全集

设 $U=\{0,1,2,3,4\}$，full = 0b11111，a = 0b01101。那么补集是 $\{1,4\}$：

1
2
3

full             11111
a                01101
full & ~a        10010    只保留全集范围内、不属于 A 的元素

直接写 ~a 会把整数存储范围内的高位也翻成 $1$。那些高位没有对应本题的元素，所以不能直接把 ~a 当作全集内的补集。

在 a 确实是 full 的子集时，也可以写：

1

auto complement = full ^ a;

而差集 a & ~b 不必再与 full 相与：因为 a 在全集外的位已经全是 $0$，这些高位自然会被清掉。

7 集合大小与子集枚举

7.1 集合大小就是 1 的个数

每一个 $1$ 对应一个元素，因此 $|A|$ 就是 a 的二进制中 $1$ 的数量。

使用 GCC / Clang 时，可以写：

1

int size = __builtin_popcountll(a);  // a 使用 unsigned long long

也可以每次清除最低位的 $1$，直到集合为空：

1
2
3
4
5
6
7
8

int count_elements(unsigned long long a) {
    int count = 0;
    while (a != 0) {
        a &= a - 1;
        ++count;
    }
    return count;
}

这一写法的循环次数恰好是 $|A|$。

7.2 枚举 A 的所有子集

从 a 开始，不断计算 (s - 1) & a，可以按掩码数值从大到小枚举所有子集：

1
2
3
4

for (auto s = a; ; s = (s - 1) & a) {
    // 处理子集 s，包括空集和 A 自身
    if (s == 0) break;
}

例如 a = 0b101，得到：

1
2
3
4

101    {0, 2}
100    {2}
001    {0}
000    空集

减一会把最低位的 $1$ 变成 $0$，并把其右边的位变成 $1$；再与 a 相与，就只留下允许出现的元素。这相当于只在 a 为 $1$ 的位置上做二进制倒数。

处理完 s == 0 必须停止，否则无符号数的 0 - 1 会回绕，再与 a 相与又得到 a，形成循环。上述写法也适用于 a == 0，此时只处理一次空集。

若 $A$ 有 $k$ 个元素，它有 $2^k$ 个子集，所以枚举仍然需要 $2^k$ 次处理。位运算压缩了表示，并没有减少子集的数量。

8 应用：检查能力是否满足需求

假设每一位表示一种能力：第 $0$ 位是读权限，第 $1$ 位是写权限，第 $2$ 位是执行权限。

某个用户的能力集合为 have，操作要求的能力集合为 need：

1
2
3
4
5
6
7
8

using Mask = unsigned long long;

Mask have = 0b101;  // 有读、执行权限
Mask need = 0b011;  // 需要读、写权限

bool enough = ((have & need) == need);  // false：没有满足全部要求
Mask missing = need & ~have;           // 0b010：缺少写权限
bool any = ((have & need) != 0);        // true：至少满足了一项

这里要判断的是 $need\subseteq have$，因此交集应该与 need 比较。把题目中的“需要全部”“至少一个”“一个也不能有”翻译成包含关系、交集非空、交集为空，就能直接写出判断式。

9 C++ 中的类型与范围

本文代码统一使用 unsigned long long，并把元素编号限制在 $0$ 到 $63$。对这个范围，1ULL << i 可以表示单个元素；不要写成默认使用 int 的 1 << i。

如果全集有 $n$ 个元素，且 $0\le n\le63$，可以写：

1
2

using Mask = unsigned long long;
Mask full = (1ULL << n) - 1;

它在 n == 0 时得到空集。若要覆盖编号 $0$ 到 $63$ 的全部 $64$ 个元素，可以使用：

1
2
3

#include <limits>
using Mask = unsigned long long;
Mask full = std::numeric_limits<Mask>::max();  // 在 64 位 Mask 上

不能在 64 位类型上计算 1ULL << 64：移位次数必须小于类型的位宽。若元素更多，可使用 std::bitset<N> 或多字位集；此时一次集合运算的成本也会随使用的机器字数量增加。

当整个集合装在一个机器字中时，本文的交、并、差和包含判断都只需常数次位运算。理解这些式子的关键，是把每一位始终看成同一个问题：这个元素在不在集合中？

10 相关题解

暂无相关题解