1.13 绕不开的加法器
沿输入位、半加器、全加器、进位链和多位输出追踪整数加法，用布尔门、溢出和故障实验验证。
学习目标
- 能用 XOR、AND、OR 解释半加器、全加器和逐位进位链的输入输出
- 能区分每一位的和、生成进位、传入进位、多位结果和有符号溢出
- 能在缺少进位、位宽边界和门逻辑错误场景中定位首个错误并重放真值轨迹
1.13 绕不开的加法器
本页依据刘欣《码农翻身》（2018 年第 1 版）及出版社公开书目信息，独立重构 1.13 绕不开的加法器。正文、代码、图示、实验和练习都是本课程重新设计的教学材料，不复制原书正文、插图、练习答案或代码。
整数加法不是一个不可拆的黑盒。半加器处理两个输入位，XOR 产生和、AND 产生进位；全加器再把低位传入进位合并，多个全加器串成多位加法器。每一位都要保存输入、和、生成进位、传入进位和传出进位，最终还要按位宽解释结果与溢出。
三个会让加法器模型失真的陷阱
加法器合同
↡本页把故事重构为由布尔门构成半加器与全加器，并由进位链产生固定位宽整数和的组合逻辑模型。不是把加法拟人化，而是要求每一位的布尔输入、输出和进位关系可计算、可观察、可复位。
全加器的关系可以写成：
多位加法器从最低位到最高位传递 carry_out。固定位宽的结果只保留位宽内的位；无符号进位、有符号溢出和结果截断要分别报告。
五个节点到机制证据
输入位
↡当前位的两个操作数位以及从低一位传入的进位位，决定该位全加器的输入状态。先固定 a、b 和 carry_in，再逐位计算；不能把整型输入直接跳过门级关系。
半加和
↡半加器对两个输入位执行 XOR 得到的和位，不包含来自更低位的传入进位。是 a XOR b，同时还要产生 a AND b
的生成进位。它是理解全加器的局部构件，不是多位结果。
生成进位
↡由当前位两个输入同时为 1 产生的进位，通常由 AND 门表达并等待与传入进位合并。表示 a AND b；即使当前位没有直接生成，也可能由传入进位继续传播。
合并进位
↡把半加器产生的局部结果与传入进位组合，形成当前位和与传出进位的全加器阶段。决定进位链能否跨越连续位；任何一位漏接都会在更高位形成可定位的首差。
输出多位
↡按位宽收集各位 sum 和传出最高位进位，并分别解释固定宽度结果、无符号进位和有符号溢出的结果。不是把无限精度整数直接打印出来。记录位宽、每位和、最高位进位、截断结果和溢出判定。
最小可重放实现
carry = 0
for bit in least_significant_to_most_significant:
sum_bit = a[bit] xor b[bit] xor carry
carry = (a[bit] and b[bit]) or (carry and (a[bit] xor b[bit]))
assert fixed_width_result == reference_result
assert reset() == baseline_trace这段草图只表达逐位进位合同，不复制书中叙事或代码。实际复核应保存位宽、输入位、半加结果、生成/传入/传出进位、门输出、最终结果和复位结果。
五步复核一条多位加法
1. 固定位宽和输入位
记录无符号或有符号解释、位宽、每个操作数的二进制表示和初始 carry_in。先预测最低位的和与进位。
Lab
真值表与进位链实验
只改变一个输入或进位连接，观察首个错误位、位宽结果和溢出判定。
4 位输入 0011 + 0100，进位链按序归零
bit0..3 → sum=0111; carry_out=0; signed overflow=false
判定
通过：每位真值与多位输出一致
当前场景：基线加法；记录位宽、输入位、XOR/AND、carry_in、carry_out、截断与溢出。
正常、边界与故障证据
| 样本 | 只改变的变量 | 预期判定 | 必存证据 |
|---|---|---|---|
| 正常 | 真值表输入和进位连接完整 | 每位和、进位与参考结果一致 | 输入位、门输出、进位链、结果 |
| 边界 | 位宽、连续进位、最高位符号或全 1 输入 | 截断、无符号进位和溢出分别报告 | 位宽、最高位、carry out、符号判定 |
| 故障 | 一次门逻辑错误或进位线断开 | 首个错误位可定位，修复后重放 | 首差、输入、门输出、进位、复位 |
故障诊断：从最低位向最高位找首差
- 核对位宽与解释：确认二进制位序、补码/无符号模式和期望输出位宽，排除显示层误读。
- 核对半加门：比较每一位 XOR、AND 真值，找第一个不符合门合同的输出。
- 核对进位链：检查
carry_in是否等于低一位carry_out，找断线、反接或漏合并。 - 核对最高位判定：分别保存截断结果、无符号进位和有符号溢出，再从清零进位的基线重放。
术语表
名词解释
本章出现的专业名词，用大白话再讲一遍。
- 1.13 绕不开的加法器
由布尔门构成半加器与全加器，并由进位链产生固定位宽整数和的组合逻辑模型。
- 输入位
当前位的两个操作数位以及从低一位传入的进位位。
- 半加和
半加器对两个输入位执行 XOR 得到的和位，不包含传入进位。
- 生成进位
由当前位两个输入同时为 1 产生的 AND 进位。
- 合并进位
把局部结果和传入进位组合成全加器和与传出进位的阶段。
- 输出多位
按位宽收集各位和并分别解释截断、无符号进位与有符号溢出。
练习
练习
问题 1： 为什么 1 + 1 不能只用 XOR 得出最终结果？
问题 2： 最高位产生进位，是否一定表示有符号溢出？
问题 3： 多位加法结果只在某一个输入上错误，应该先检查哪里？
本页小结
1.13 绕不开的加法器的关键不是把加法看成一个神秘黑盒，而是能从输入位、半加和、生成进位、合并进位追踪到固定宽度输出。完成标准是区分无符号进位、截断和有符号溢出，在首个门逻辑或进位断点修复后，用真值表和干净复位证明结果一致。