# 课前零食：把 64 个开关装进一个格子

> 今天的主角不是某个玄学优化，而是一句很朴素的话：既然一排判断都只回答“是/否”，能不能让 CPU 一次搬 64 个？答案是能，但账本仍要老老实实地算。

## 本节目标

学完后，你能：

- 把一个布尔数组看成集合，把第 $i$ 位为 1 看成“元素 $i$ 在集合中”；
- 用 AND、OR、XOR、移位分别表达交、并、奇偶出现和整体平移；
- 解释 `bitset` 的一次整集合操作为何是 $O(N/w)$ 而不是魔法 $O(1)$；
- 看懂为什么这类优化适合“大量同形布尔判断”，却不适合每一位都走不同分支的任务。

## 前置知识与课前自测

前置：二进制、位运算 `& | ^ << >>`、数组下标。

1. 若位串 `00101000` 的最右位是编号 0，哪些编号在集合中？
2. 两个集合交集中的元素，应在两个位串的哪种运算后留下 1？
3. 长度 $10^5$ 的位集合做一次 `&`，CPU 真只做一条机器指令吗？

<details><summary>答案</summary>

1. 编号 3 和 5。2. AND。3. 不会；它通常要处理约 $\lceil10^5/64\rceil$ 个机器字，只是每一字同时处理了 64 个布尔值。

</details>

## 互动规则：把 0 和 1 当成一排真的开关

这节不从 `std::bitset` 开始。请先在纸上画编号 `0..7` 的八个格；约定**最右格是编号 0**。每一轮都写四栏：`第 i 格代表什么对象`、`这一轮逐格做了什么`、`能否把很多格做成同一种动作`、`越界格去哪了`。

程序里显示的字符串从左到右是高位到低位；纸上编号却从右往左。这个小别扭故意保留：你要亲手翻译一次，之后才能真正控制位运算，而不是靠眼熟。

## 从零搭框架：从八次 if 到一次整字操作

### 第 0 步：先让布尔数组说人话

令 `like_A[i]` 表示编号 `i` 的人是否在 A 的名单，`like_B[i]` 同理。把下面两行翻译成集合成员：

```text
A = 10110110
B = 01101100
```

> 停顿 0：请从右往左编号，分别列出 A、B 中为 1 的下标；再圈出两边同时为 1 的下标。不要先算二进制整数。

<details><summary>展开：位串只是压缩后的布尔数组</summary>

A 的成员为 `{1,2,4,5,7}`，B 的成员为 `{2,3,5,6}`，共同成员为 `{2,5}`。第 $i$ 位就是一句 `bool`；它不是一个神秘的“位技巧对象”。

</details>

### 第 1 步：先写出最朴素循环和它的账本

要找共同成员，人脑会写：

```text
for i in 0..N-1:
    if A[i] and B[i]:
        keep i
```

请在 $N=8$ 的例子中逐列写下两盏灯的状态与结果。然后把 $N$ 改成 64、$10^5$，只估算“要做多少次彼此独立的同形判断”，不必猜具体秒数。

> 停顿 1：这 8 次 `and` 之间有前后依赖吗？第 7 格的答案会影响第 0 格吗？

<details><summary>展开：发现可并行的真正条件</summary>

没有依赖：每一列只看自己的两个布尔值，并采用同一规则。于是我们不必改变答案定义，只需改变处理单位——把连续 64 个布尔值装成一个 64 位机器字。若每格下一步都要访问不同位置或依赖前一格结果，就不能直接这样打包。

</details>

### 第 2 步：先为一位写真值表，再允许它批量工作

不要背 `& | ^`。给单个位置填表：

| A 的这一位 | B 的这一位 | “都在名单中” | “至少一边在” | “恰好一边在” |
|---:|---:|---:|---:|---:|
| 0 | 0 |  |  |  |
| 0 | 1 |  |  |  |
| 1 | 0 |  |  |  |
| 1 | 1 |  |  |  |

> 停顿 2：分别给三列取运算符名字；为什么“出现奇数次”要用 XOR 而不是 OR？

<details><summary>展开：集合语言与机器语言一一对应</summary>

“都在”是 AND， “至少一边”是 OR，“恰好一边/出现次数奇偶”是 XOR。两次出现的元素在 XOR 中变回 0，正好符合模 2 计数；OR 会把两次出现仍错误地保留成 1。

</details>

### 第 3 步：移位不是搬数字，是让集合成员改编号

在纸上写 `reach={0,2,5}`。若一个统一动作把每个位置编号加 3，请先把集合手算成新集合；再把它写成一个 8 位串，做左移 3 位，最后裁掉超过 7 的成员。

> 停顿 3：若不同位置分别加 `a[i]`，还能用一次 `<<` 吗？为什么？

<details><summary>展开：一条移位代表许多相同转移</summary>

`{0,2,5}` 变为 `{3,5,8}`，在长度 8 的集合里只留下 `{3,5}`。`reach << 3` 正是在所有置位位置同时加同一个数；若每个位置的步长不同，就没有一条统一移位可代替逐点转移。

</details>

### 第 4 步：速度账本要算“字”，不是假装一切 O(1)

把长度 $N$ 的布尔数组切成 $\lceil N/64\rceil$ 个字。请填写：

| 长度 N | 一次整集合 AND 至少处理几字 | 外层枚举 $N$ 次时总字操作约多少 |
|---:|---:|---:|
| 64 |  |  |
| 1024 |  |  |
| $10^5$ |  |  |

这一步是 Bitset 的复杂度框架：先识别“每位同形”，再按机器字估算；不是看到 `bitset` 就把复杂度涂成 $O(1)$。

## 问题动机：逐个打勾并不总是必要

假设有两张很长的“喜欢这部电影的人”名单。要找共同喜欢的人，最直白的循环会逐个人比较：`if likes_a[i] and likes_b[i]`。比较本身没有错，但 64 次彼此独立的小判断可以装进一个 64 位整数，一次 AND 就交给硬件并行完成。

![把多个布尔值装入一个机器字](../插图/03-Bitset/00-Bitset-01-打包.svg)

注意这个词：**并行的是同形操作，不是任意算法。**若每个位置都要访问不同的邻居、走不同分支，装进同一个格子也救不了数据依赖。

## 步步式引导

### 1. 从集合语言翻译到位运算

令第 $i$ 位表示元素 $i$ 是否在集合里。两集合 $A,B$ 的每一位独立决定：

| 集合问题 | 位运算 | 这一位为什么正确 |
|---|---|---|
| $A\cap B$ | `A & B` | 两边都选中才留下 |
| $A\cup B$ | `A | B` | 至少一边选中就留下 |
| 恰好一边选中 | `A ^ B` | 两个 1 合成 0，符合奇偶 |
| 全体中不在 $A$ | `~A` | 0 与 1 互换；要记得裁掉越界位 |
| 编号整体加 $k$ | `A << k` | 每个置位位置向高位平移 |

![同一位上的集合运算](../插图/03-Bitset/00-Bitset-02-集合运算.svg)

### 2. 速度从哪里来，又没有从哪里来

把长度 $N$ 的集合分成 $\lceil N/w\rceil$ 个机器字，常见机器字宽 $w=64$。整集合 AND/OR/XOR 的工作量是：

$$
O\left(\frac{N}{w}\right).
$$

这不是把 $N$ 个信息凭空删掉，而是改变处理单位。外层若仍枚举 $N^2$ 对点，总复杂度仍约为 $O(N^3/w)$；先估算总机器字操作次数，才知道优化有没有把题从“过不了”带到“能过”。

### 3. 一次移位为什么能表示很多状态转移

若 `reach[i]=1` 表示“能到位置 $i$”，而一个动作让位置编号都加 3，则新集合可写成 `reach << 3`。再与其他来源 OR 起来，就是许多状态同时转移。它要求每个状态的转移规则相同；若第 $i$ 个位置要加 `a[i]`，就不能直接用一条统一移位。

```text
# bits 是一个长度 N 的布尔集合，mask 只保留 0..N-1 位
common = group_a AND group_b
next_reach = ((reach << step_1) OR (reach << step_2)) AND mask
how_many = popcount(common)
```

## 纸上模拟：把一行位串完整翻译三次

仍用 `A=10110110`、`B=01101100`。先不使用程序，依次完成：

1. 每列做 AND，写出 8 位结果；把结果译回集合。
2. 每列做 XOR，说明下标 2、5 为什么消失或保留。
3. 把 A 左移 2 位后与 `11111111` 相与；哪些原成员因越界消失？
4. 若长度不是 8 而是 6，`~A` 后为什么还必须与 `00111111` 相与？

<details><summary>展开：结果与边界账</summary>

AND 为 `00100100`，集合 `{2,5}`；XOR 为 `11011010`，集合 `{1,3,4,6,7}`。A 左移 2 后（保留 8 位）为 `11011000`，原编号 7 越界消失。长度为 6 时，整数的 `~` 会连同“第 6 位以上不存在的成员”也翻成 1，必须用掩码裁回合法宇宙。

</details>

## 核心知识：边界位也是集合成员

`~A` 在整数上会把无限高位也翻成 1；固定长度 `std::bitset<N>` 会自动限制范围，自己用 Python/整数模拟时必须 `& mask`。左移溢出的成员应离开集合，右移低位补 0。最常见错误不是 `&` 写成 `|`，而是“位编号从左还是从右数”在两段代码里悄悄换了口音。

空间为 $O(N/w)$ 个机器字。若大小在编译时固定，C++ 的 `std::bitset<N>` 很方便；若大小运行时才知道，正式课会讨论 `vector<uint64_t>` 的分块处理。

### 一点点 SIMD：它是表亲，不是同义词

Bitset 的 AND 是把一个机器字里的**每一位**当成一个布尔对象；SIMD（Single Instruction, Multiple Data）则让一条指令同时处理多个固定宽度的“通道”，例如 8 个 `int32` 或多组 64 位字。两者都在利用硬件并行，但研究对象不同：

| 工具 | 一次并行的对象 | 适合的表达 |
|---|---|---|
| Bitset | 一个字中的许多布尔位 | 集合交并、可达状态、掩码 |
| SIMD | 寄存器中的多条数值通道 | 批量加减、比较、向量/矩阵小块计算 |

在非常长的动态 bitset 中，底层循环有时能让编译器把多个 64 位字再用 SIMD 一批处理；但 C++ 标准不保证 `std::bitset` 一定自动向量化。先选对算法、估算 $N/w$、再用 profiler 证明确有瓶颈，最后才考虑编译器优化选项或 intrinsics。SIMD 是一把好电动螺丝刀，不是见到螺丝就必须掏出来。

## 实现指南

- 先在纸上约定：最低位是否对应下标 0；之后打印、移位和取位都用同一约定。
- 需要 `count()` 时，确认它统计的是置位数，不是集合中元素值之和。
- `~`、左移后记得和长度掩码相与；否则调试输出会长得像一只没有尽头的毛毛虫。
- 估算 `N/w` 时别遗漏外层循环，也别把缓存、常数当成无限小。

## 互动小实验室

运行 [把64个开关装进一个格子.py](../../互动程序/03-Bitset/00-把64个开关装进一个格子.py)。它先用 8 位版本展示位号，再让你选择 `&`、`|`、`^` 或移位；最后把结果重新翻译成集合。

先预测 `10110110 & 01101100` 的集合交集，再按回车看答案。8 位只是显微镜，真正的机器字会一次装下 64 位。

## 扩展与联系

Bitset 常出现在邻接集合交、可达集合传播、背包布尔可达性和字符串位置匹配中。它不能替代需要最小值、路径恢复或每个位置异构转移的 DP；这时“能否并行”要先经过数据依赖的同意。若数据不是布尔集合而是一排相同宽度的数值，再回头考虑 SIMD 会更自然。

## 总结与自检

1. 为什么 XOR 对应“出现次数的奇偶”，而不对应普通并集？
2. 哪个条件使 `reach << k` 成为合法的一批转移？
3. 长度固定为 $N$ 时，`~bits` 后为什么要裁边？

<details><summary>自检答案</summary>

两个 1 XOR 后变 0；所有置位的位置必须采用同一平移规则；整数补码没有“只到第 N 位”的天然边界。

</details>

## 一周预热安排

- 第 1 天：把 8 个位置写成一串二进制，互相翻译集合与位串。
- 第 2 天：手算四种基本位运算和一次移位。
- 第 3 天：用 $N/w$ 估算三种不同规模的整集合操作。
- 第 4 天：运行互动程序，故意测试 `~` 与越界移位。
- 第 5 天：带着“同形布尔转移”的识别信号进入[正式课](01-字级并行集合模型与动态匹配.md)。