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

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

本节目标

学完后，你能：

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

前置知识与课前自测

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

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

答案

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

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

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

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

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

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

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

A = 10110110
B = 01101100

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

展开：位串只是压缩后的布尔数组

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

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

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

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 格吗？

展开：发现可并行的真正条件

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

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

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

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

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

展开：集合语言与机器语言一一对应

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

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

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

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

展开：一条移位代表许多相同转移

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

第 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 就交给硬件并行完成。

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

步步式引导

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`	每个置位位置向高位平移

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]，就不能直接用一条统一移位。

# 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。先不使用程序，依次完成：

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

展开：结果与边界账

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

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

~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。它先用 8 位版本展示位号，再让你选择 &、|、^ 或移位；最后把结果重新翻译成集合。

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

扩展与联系

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

总结与自检

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

自检答案

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

一周预热安排

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

00-课前零食-把64个开关装进一个格子.md 12 KB Historique Raw