守株阁

第 01 篇得到了一块全零磁盘。QEMU 能运行固件，GDB 能控制 CPU，但 BIOS 最终只显示 No bootable device.。磁盘里没有可执行的引导入口，工具链生成的 ELF 文件也没有被加载。 本篇把一段 16 位机器码写进磁盘第一个扇区。BIOS 读取它，程序准备自己的段寄存器和栈，输出固定标识，再停在可检查的循环中。改坏末尾签名后，同一份机器码将不再得到执行机会。 从第一个扇区交出执行权 在本系列固定的 QEMU PC 和 SeaBIOS 环境里，固件尝试从 IDE 硬盘启动时，会读取第一个逻辑扇区，把内容放到物理地址 0x7c00。通过有效性检查后，执行流转移到这块内存。 磁盘上的扇区编号、文件偏移和内存地址是三个不同的量： 123456789镜像文件偏移 0 … 511：第一个 512 字节扇区 │ BIOS 读取 ▼客体内存0x7c00 … 0x7dff：刚读入的同一组字节 │ CPU 取指 ▼设置段与栈 → 输出标识 → 停止 0x7c00 不是 NASM 决定的磁盘位置。固件先决定加载位置，汇编代...

在普通应用项目里，编译成功后通常可以直接运行可执行文件。自制操作系统还缺少一段工作：谁把文件里的指令放进内存，谁准备栈，CPU 又从哪里开始执行？ 本篇先把这些问题拆开验证。第一条实验生成 ELF32/i386 文件，检查源代码、符号、链接地址和机器指令的对应关系。第二条实验把一块全零磁盘接到 QEMU，观察固件启动失败，再用 GDB 停住并单步执行 CPU。 两条实验还没有连接起来。sample.elf 不会被写进空磁盘，也不会由 BIOS 加载。本篇完成后得到的是可用的编译与调试环境；第 02 篇才开始写 BIOS 能执行的启动扇区。 宿主、目标与固件 本次实验的宿主链路是 ARM macOS 上的 Podman Linux 虚拟机，容器内运行 Debian 12 aarch64。交叉编译器本身是一段 ARM Linux 程序，它生成的指令却属于 32 位 x86。QEMU 再通过 TCG 动态翻译运行这个 x86 客体，不要求宿主 CPU 支持直接执行 x86 指令，机制见 QEMU TCG 文档。 12345678ARM macOS └─ Podman Linux V...

这个系列准备从一个 512 字节启动扇区开始，逐步做出一个能运行用户程序、读取文件、响应键盘鼠标、显示窗口终端的教学操作系统。 路线故意选得朴素：x86 32 位、BIOS、C11、少量 NASM 汇编、QEMU 模拟 PC。它不是现代操作系统的完整复刻，也不追求真实机器兼容。它的目标是把“操作系统到底接管了什么”拆成一组可以运行、可以坏掉、可以诊断的实验。 最终目标是一条连续演示：从自制磁盘镜像启动，进入自制内核；打开一个终端窗口；运行 cat README.TXT；再运行 cat README.TXT | wc；最后运行一个 DEMO.EXE，它并发启动两个计数程序和一个故意越界访问的程序。越界程序应该被终止，两个计数程序继续前进，Shell 还能继续接收下一条命令。 这篇导读只给路线、边界和先修自测。首批配套项目提供工具链样例；自制内核尚未出现。后续每篇会在同一份代码上增加一个可观察能力，并给出构建命令、运行日志和故障实验。 最终系统长什么样 先用一张目标图定住边界。图里的“目标”表示后续实现完成后的结构，不是当前已经跑通的截图。 12345678910111213141...

第30篇的集合覆盖要求覆盖全部目标，尽量降低成本。本篇改变约束：最多选择k个集合，尽量覆盖更多元素。两个问题都可能每轮挑选新增覆盖多的集合，但目标函数、停止条件和近似比不同，不能直接互换证明。 最大覆盖是单调次模最大化的一个实例。它适合完整展示贪心保证：每一步至少消除剩余最优差距的1/k，而这个结论同时依赖预算、单调性与边际递减。 元素宇宙与候选集合 元素宇宙为整数0到U−1，U≥0。输入有n个候选集合C_0到C_{n−1}，每个元素必须在宇宙内；不同ID可以具有相同集合内容。预算k是非负整数，输出至多k个不同候选ID以及它们的并集。 令S为选中的候选ID集合，目标函数f(S)是其覆盖元素数。候选ID与被覆盖元素属于两种对象，不能把“选了三个集合”和“覆盖了三个元素”混用。 空候选族或k=0返回空选择与空覆盖。U=0时所有合法候选均为空，最优值也是0。预算超过候选数量不需要重复选择同一ID；最多考虑全部n个候选。 从新增覆盖看次模性 函数归一化意味着f(空集)=0。单调性意味着S包含于T时f(S)≤f(T)。加入更多候选不会删除已覆盖元素，所以最大覆盖满足两者。 把新增候选x的边...

两段有序数组归并成一段，顺序算法每次比较两端最小值，耗线性时间。要让多个处理器同时工作，不能简单地把两段输入各切成相同长度：某一段的全部元素可能都应排在另一段之前，输入位置并不对应输出位置。 本篇用co-ranking把输出区间映射成输入区间，再并行归并。证明使用共享数组模型；Python实验使用独立进程，父进程的切片、传输和结果拼接另行计入实际时间。 输入顺序与相等键 输入A、B是两个非递减整数数组，长度分别为m、n，总长N=m+n。输出包含所有元素且非递减，不修改输入。相等键约定A中的元素先于B，同一数组内部保持原顺序。 空数组与重复值合法。serial_merge与parallel_merge检查元素为整数且已排序；parallel_merge还拒绝整数分区数P≤0。co_rank只检查前缀长度r范围，它以两输入已排序为前提，不单独扫描验证排序。接口不提供任意比较器、浮点NaN或外部文本解析。 按输出位置把[0,N)分成P段，边界r_j=⌊jN/P⌋。每段长度相差至多1；P>N时会出现空段，不能假设每个任务都有工作。 一个输出前缀来自多少输入 对前r个输出元素，设其中...

近邻索引可以减少需要比较的候选点，但没有进入候选集的真近邻，无法靠最后一次精确距离计算补回来。评价索引因此需要同时回答三个问题：漏了哪些近邻、保存了多少索引、每次查询花多少时间。 本篇只实现二进制Hamming空间中的位抽样LSH。精确扫描使用同一批数据、同一批查询和同一种并列顺序；HNSW作为另一类方法的延伸，不把LSH碰撞公式当作它的保证。 先固定距离和答案顺序 输入有n条D位二进制向量，D>0，每条用[0,2^D)中的整数表示，ID为输入位置。允许不同ID拥有相同向量。距离为异或结果的1位数，范围0到D；它不是实数向量的欧氏距离或余弦距离。 精确答案按“距离、ID”升序取前k项，k>0。n<k时返回全部n项，空数据返回空。查询整数必须位于同一D位范围，越界拒绝。并列距离也按ID排序，避免索引与参照只因选择不同的同距点而难以解释recall。 近似接口采用相同排序，但只对候选集排序，候选不足k时返回不足。没有候选时返回空，不自动回退到全扫描。否则一些配置会用完整扫描掩盖索引漏检，速度和质量的含义都会改变。 多张位抽样表 每张表独立抽取b个位位置，每次在0到D...

第29篇讨论输入长度与伪多项式，第30篇用近似比约束点覆盖的解质量。参数化算法采用另一条路线：仍求精确可行解，把指数成本限制在某个结构参数上。参数是否足够小，必须从问题输入中说明，不能只给变量改名。 本篇实现简单无向图的k顶点覆盖判定与解恢复。返回一个大小不超过k的覆盖，或明确表示不存在；不要求返回最小覆盖，也不以近似解替代预算判定。 n、k与编码长度 设图有n个顶点、m条边，预算k为非负整数，N是图和预算的输入编码长度。一个参数化问题属于FPT，要求存在f(k)N^c时间算法，其中常数c不依赖k，f只依赖k。参数可以影响前面的函数，却不能悄悄进入N的指数。 枚举至多k个顶点的所有子集，可以给出n^{O(k)}一类成本。固定k时它是多项式，但多项式次数随k变化，这是XP型上界。仅凭这个上界不能证明该算法是FPT，也不能证明问题不存在更好的FPT算法。 例如n从一千增至一万，n^k项增加10^k倍；2^k乘一个线性图扫描项，在同样稀疏度与固定k下只随图规模线性增长。这里只比较公式，不是本机跑分或任何规模下的实际速度承诺。 一条未覆盖边给出两个分支 沿用第30篇覆盖定义：每条边至少有...

第26篇用残量网络判断还能不能增加流量。给每条边增加单位费用后，同样大小的流可能有不同总费用；只找到一条增广路，已经不足以决定该走哪条路。最小费用流需要同时维护容量可行性与费用最优性。 本篇采用Bellman–Ford逐次最短增广路。费用可以为负，但初始正容量边组成的全图不得有负费用环；容量、费用和请求流量均为整数。这个条件允许从零流开始证明，不把有限容量的负环误称为无解。 固定流值与最大流值 输入是n个顶点、m条有向边、源s、汇t和请求F。要求n≥2、s≠t、F≥0，容量非负；每条边有独立标识，所以平行边和原生反向边都可以分别计费。教学接口拒绝自环，顶点编号必须落在[0,n)。 输出包括实际流量f、总费用及各原始边流量。先在所有f≤F中最大化f，再在这个流值下最小化费用。若网络能承载F，结果就是所请求流值的最小费用流；若不能，则返回小于F的最小费用最大流。这里没有把“少运一点更便宜”当成可替代目标。 每条边的流量应在0与容量之间。源汇之外的顶点流入等于流出；源的净流出为f，汇的净流入为f。总费用是原始边单位费用乘流量后求和。负边合法，零容量边不能参与当前残量路径或负环。 反向边...

第14篇用版本根保留旧状态。对旧版本发起查询，得到的答案不会因为新版本产生而改变。追溯数据结构允许编辑过去的操作序列，之后的历史查询则按照编辑后的序列重新解释。两个接口都出现时间参数，但承诺保留的东西不同。 本篇只实现整数增量事件：在指定时间插入一个加法，或删掉已有事件，再查询某时刻之前的累计和。这个有界操作集可以用排序数组与前缀和实现，足以验证语义，不需要先实现一个通用追溯框架。 两种时间不能混用 把一次编辑请求的提交次序记为版本编号v，把事件在被建模历史中的位置记为时间t。提交顺序可以是先录入t=10，再录入t=2。版本编号仍向前增长，逻辑时间却不要求按输入顺序排列。 持久化保留v所指的旧状态；完全持久化允许从旧版本分支产生新版本，原分支仍存在。追溯编辑把t=2处的事件放入当前解释的历史，此后查询t=3就必须计入这个事件。若还要求查看“编辑之前看到的历史”，需要额外保存编辑版本，本实现没有这个接口。 需求 被查询的对象 新编辑对旧查询的影响 持久化查询版本v 固定版本状态 相同v的答案不变 追溯查询逻辑时间t 当前事件序列在t前的状态 编辑早于t的事件可能改...

把0和1放进整数数组，可以做前缀计数，但“数组长度是n”不等于“占n位空间”。简洁数据结构要求先确定信息下界，再计算索引冗余；指针、绝对计数和查找表都不能从空间账本中消失。 本篇实现静态位向量的rank/select接口，用Python参照和C++固定字长实现核对查询。教学实现采用简单分块索引，明确不把它称为已经实现n+o(n)位的succinct结构。 一种查询数个数，另一种查询找位置 输入为长度n的二进制序列B，元素只能为整数0或1，构造后不再修改。rank1(i)返回半开前缀B[0:i]中1的数量，0≤i≤n；select1(k)返回第k个1的零基位置，k从1开始，沿用00与06篇的顺序统计约定。 空序列可以构造，rank1(0)=0，但任何select都越界。全零序列也没有合法select。非法位值拒绝，rank端点或select序号越界拒绝，不用某个特殊位置冒充答案。 例如B=[0,1,0,1,1]，rank1(3)=1，select1(2)=3。这里rank参数是位置端点，select参数是出现序号；若p=select1(k)，则rank1(p)=k−1、rank1(...