《计算机组成原理》第三章在很多学校里是劝退章节——前面还在讲数制和进制转换突然就冒出来一堆门电路、寄存器、进位链。我当年学ALU这一章最崩溃的不是听不懂而是每一页PPT似乎都在默认你应该懂硬件可我只想知道一台只会认高低电平的机器到底是怎么把加减乘除算出来的。这篇笔记不打算把教材复述一遍就围绕ALU和整数的四则运算把“为什么硬件要这样设计”“每一步电路到底在忙什么”“考试怎么考”这三件事讲明白适合正在学组成原理的本科生也适合准备技术面试时临时补硬件基础的开发者。1. 学ALU之前先回答一个问题硬件拿什么算数1.1 三种机器数为什么最后只留下补码几乎所有教材在讲ALU之前都会先花一整节讲原码、反码、补码。很多同学觉得这是纯理论跟硬件没关系其实这恰恰是理解ALU的前提。原码最接近人的直觉正负号单独用一位表示但问题在于原码做加减法非常麻烦两个正数相加直接加绝对值就行一正一负要看谁大谁小符号还得单独判断。硬件最怕“分支判断”因为每一个分支都意味着额外的电路和控制逻辑。反码的出现解决了符号位参与运算的问题但反码有一个著名的尴尬它有两个零正零和负零的编码不一样。计算机里零只有一个这会导致运算结果需要额外修正。补码通过“模运算”把减法统一成了加法负数不再是单独处理的对象而是某个正数在模意义下的等价表示。比如四位补码里-1 和 15 在模 16 的意义下是同一个数所以一个本来要“减一”的操作硬件上只要“加15”再丢掉最高位的进位就行了。你可能觉得这很绕但正是这个“绕”让硬件变得极其简单加法器只需要处理无符号二进制加法减法和负数都在编码层面被消化掉了。所以ALU的核心不是“会算四种运算”而是“只需要会做加法其余运算通过编码和移位来还原”。1.2 ALU到底是一个什么样的盒子ALU的全称是算术逻辑单元它不是一个能“思考”的部件而是一个组合逻辑电路构成的盒子。你给它输入两个操作数 A 和 B再给它一个操作控制信号比如 000 表示加、001 表示减、010 表示与、011 表示或它通过内部的逻辑门直接算出结果并输出。这里有个关键点组合逻辑没有时钟、没有状态信号进去输出几乎立刻稳定下来中间不需要任何寄存器的参与。所以ALU的输入输出是非常直的输入端通常有两组数据总线各接一个寄存器输出端接一个结果寄存器另外还有标志位输出比如零标志 ZF、符号标志 SF、进位标志 CF、溢出标志 OF。这些标志位看似只是“顺便”输出的信号实际上对后续的条件跳转、循环控制极其重要也是第五章指令系统的基础。初学的时候我建议你从“行为级”理解ALU把它当成一个能换挡的加法器。挡位由控制信号决定有的挡位把 B 直接送进去做加法有的挡位把 B 取反再做加法有的挡位把 A 和 B 做位运算。你先把这些行为弄清楚再去抠内部电路就不会在门电路里迷失方向。1.3 从真值表到门电路算术运算的底层语言ALU内部的电路本质上就是用门电路实现布尔函数。任何一个算术运算都可以先写成真值表再化简成逻辑表达式最后用与或非门搭出来。这个流程看着机械却是理解全加器、比较器、移位器的最快路径。举例来说一位二进制加法其实只有四种情况0000111011110。前三种没有进位第四种要产生一个进位。这就是一位半加器的全部逻辑。但实际加法器要处理来自低位的进位所以需要三位输入A、B、Cin低位进位输出本位和 S 以及向高位的进位 Cout。理解了真值表再看逻辑表达式就完全不会慌。硬件设计者和课本上反复强调“一位全加器”是因为它是所有加法器的基础。你后面看到的超前进位加法器、阵列乘法器本质上都是在优化“如何更快地处理位与位之间的进位传播”而不是发明新的加法。先把一位全加器嚼碎了后面所有内容都是它的排列组合。2. 加法器整数四则运算的真正地基2.1 一位全加器三个输入两个输出一位全加器我们手动推一下。输入是 A、B、Cin输出是 S 和 Cout。真值表写出来之后S 的规律就是“三个输入里 1 的个数是奇数时输出 1”所以 S 可以直接用三个异或门串起来S A⊕B⊕Cin。Cout 的规律是“A 和 B 都为 1或 A/B 任意一个为 1 且 Cin 为 1”表达式是 Cout AB (A⊕B)Cin。很多人看到表达式就过去了但我建议你真正动手画一下电路图。画完之后你会发现门电路实现加法并不神秘两个输入先过一个异或门得到初步和再和进位输入过一个异或门得到最终和进位产生分两条路一条是 A 和 B 都等于 1 时的“直接进位”另一条是 A、B 中有一个为 1 时进位输入“穿透过来”的进位。理解“进位产生”和“进位传递”这两个概念特别重要。后面的超前进位加法器核心就是分别定义Ggenerate进位产生和Ppropagate进位传递G_i A_i B_iP_i A_i⊕B_i。如果 G_i 为 1说明这一位必然产生进位不管低位有没有进位过来如果 P_i 为 1说明这一位会把低位的进位原样传给高位。你可以把 P 想象成一段通畅的水管把 G 想象成水管中间自己冒出来的水源。2.2 进位链为什么加法快慢取决于进位把 n 个一位全加器串联起来就得到了最朴素的串行进位加法器。每一位的 Cout 接到下一位的 Cin看起来天经地义但它的致命问题在于延迟第 0 位的进位要等第 0 位计算完第 1 位要等第 0 位的进位到达才能稳定第 2 位又要等第 1 位……进位像多米诺骨牌一样一路倒过去。举个例子你就明白了。计算 0111 0001最低位 11 产生进位这个进位传到第 1 位第 1 位的 10进位又产生进位一路传到最高位。中间每一级全加器都需要一定的门延迟如果每一位进位延迟是 2t那么 32 位加法器的进位总延迟就是 64t 左右。t 通常是纳秒级看起来不多但 CPU 一个时钟周期才几纳秒进位链直接决定了你加法器不能跑多快。所以优化加法器的核心目标只有一个缩短进位传播路径。最极端的做法是参考 CLA超前进位加法器一次性把所有位需要的进位全部提前算出来不让进位一位一位往上爬。2.3 超前进位与组间并行4位CLA是怎么算的超前进位加法器的思想是递归地展开进位公式。以 4 位为例C1 G0 P0C0C2 G1 P1G0 P1P0C0C3 G2 P2G1 P2P1G0 P2P1P0C0C4 G3 P3G2 P3P2G1 P3P2P1G0 P3P2P1P0C0你仔细看C2 不用等 C1 先算出来它直接由 G、P 和 C0 组合逻辑生成。整个 4 位加法器的进位只需要经过门电路一次“决策”不再是一家一家排队传递。代价也很明显每一项的与门输入越来越多C4 的表达式里甚至有一个 4 输入与门再往上扩展到 8 位、16 位门电路的扇入一个门有多少个输入端会大到物理上无法实现。所以实际工程里不会做 32 位全超前进位而是分层处理4 位一组用 CLA组之间再用串行或组间先行进位来连接。这就像公司管理每个人只管几个直接下属再通过层级协同不会让一个 CEO 直接管理一万个人。考试里常见的设计题基本都会落在“4 位 CLA 组成的 16 位加法器”这个层次你只要能把 4 位的进位公式写出来再说明组间串行或组间并行的思路就够用了。3. 减法没有新电路补码让减法“消失”了3.1 一个控制信号把加法器改成减法器理解了补码之后减法就变得非常“无趣”了因为 A - B 可以写成 A (-B)而 (-B) 的补码就是 B 的补码按位取反再加 1。硬件上只需要做三件事把 B 的每一位取反把 Cin 置 1然后丢进加法器。具体电路里通常用一个信号 Sub 来控制Sub 为 0 时直通 B 的原值Cin 为 0电路做加法Sub 为 1 时所有 B 的线接一个异或门相当于取反Cin 为 1电路做减法。所以你看到的所有 ALU 电路里加法和减法共用同一个加法器只是前面加了一层“可控取反器”后面多了一个进位输入的控制。这就是为什么教材反复强调补码因为补码不仅统一了符号位参与运算的问题还直接让硬件省掉了一整套减法器。实际的 ALU 电路里你会看到 A 和 B 都先经过一组异或门再到全加器阵列那个异或门就是“取反开关”。我当年第一次看懂这个电路的时候真的拍了大腿——所谓减法不过是在加法器门口加了一个“把 B 翻个面”的装置。3.2 溢出不是算错了是放不下整数的加减法最容易被忽视的问题是溢出。请注意溢出和进位是两码事。进位指最高位向更高位产生了进位它可能只是说明结果需要的位数变多了溢出则是结果超出了当前字长能表示的“范围”导致结果本身变成了另一个数。以 4 位补码为例能表示的范围是 -8 到 7。如果你计算 5 4结果是 9超过了 7那么硬件算出来的 0101 0100 1001即 -7。数学上完全错了这就是溢出。再比如 -6 (-4) -10小于 -8结果 1010 1100 10110截断成 0110 即 6也是错的。判断溢出有一个直觉方法两个正数相加得到负数或两个负数相加得到正数必然溢出。但这句“口诀”只适用于“同号相加”一正一负相加永远不可能溢出因为结果绝对值不会超过任意一个操作数。硬件上不能靠直觉判断必须用可计算的逻辑。3.3 单符号位与双符号位两种判断溢出的办法教材里最经典的判断方法有两个考试必考。第一种是单符号位法。设最高数据位向符号位的进位为 C1符号位向更高位的进位为 C2也就是最终的 Cout那么溢出标志 V C1 ⊕ C2。C1 和 C2 不同就说明结果符号被进位改变了必然溢出。你拿 54 验证0101 0100 中第三位的进位是 0000等等我重新算4 位 0101 0100从第 0 位开始101 无进位第 1 位 000第 2 位 110 进位 1第 3 位符号位0011无进位。所以 C1第 2 位产生的进位给符号位是 1C2符号位产生的进位是 0异或得 1溢出。用 -6 (-4) 验证也能得到溢出这个方法非常可靠。第二种是双符号位法也叫变形补码。把补码的符号位扩展成两位00 表示正数11 表示负数。运算时符号位两位同时参与如果结果的两个符号位相同00 或 11说明没溢出如果是 01说明正溢出如果是 10说明负溢出。这个方法的原理是正确的符号只能被两位完全相同的状态表示一旦最高位和次高位不一致说明进位冲进了符号区域。我个人更喜欢双符号位因为它不仅告诉你“有没有溢出”还告诉你是正方向溢出了还是负方向溢出了做题时不容易混淆。但考试书写通常更常考单符号位公式所以你两个都要会并且要能说清 C1、C2 各是哪一段的进位。4. 乘法用“移位加法”把竖式写进寄存器4.1 原码一位乘法最朴素也是最可靠的流程整数乘法在硬件上绝对不是用一个“乘法器芯片”直接算而是把小学竖式搬进了寄存器。回想一下十进制竖式乘法把乘数每一位逐位取出来乘以被乘数然后错位相加。二进制更简单因为每一位只能是 0 或 1所以“乘以这一位”的结果要么是 0要么就是被乘数本身根本不需要乘法表。原码一位乘法的做法是符号位单独处理将两个操作数的绝对值做“无符号乘法”。硬件上通常有三个寄存器A 寄存器存部分积的高位初始为 0Q 寄存器存乘数M 寄存器存被乘数。每一步检查 Q 的最低位也就是乘数当前被处理的那一位如果 Q0 是 1就在 A 上加一个 M如果 Q0 是 0A 保持不变。然后 A 和 Q 联合右移一位把 A 的最低位移进 Q 的最高位乘数最低位丢弃同时 A 的最高位补 0。这个过程重复 n 次n 是操作数的位数结束后乘积就在 A 和 Q 拼接而成的 2n 位寄存器里。你需要注意的是这里的右移是逻辑右移最高位永远补 0因为做的是无符号绝对值乘法不存在符号扩展的问题。4.2 手推一遍5×3寄存器到底是怎么转的我们拿 4 位原码一位乘法算 5 × 3。X 0101Y 0011M 0101Q 0011A 初始为 0000。第 1 轮Q0 1所以 A A M 0000 0101 0101。然后 A 和 Q 联合右移。A 变成 0010A 的最低位移入 Q 的最高位Q 从 0011 变为 1001。此时 A:Q 0010 1001。第 2 轮Q0 1A A M 0010 0101 0111。联合右移A 变成 0011Q 变成 1100。此时 A:Q 0011 1100。第 3 轮Q0 0A 保持不变仍是 0011。联合右移A 变成 0001Q 变成 1110。此时 A:Q 0001 1110。第 4 轮Q0 0A 不变仍是 0001。联合右移A 变成 0000Q 变成 1111。最终 A:Q 0000 1111也就是 15。注意乘数和被乘数都是正数符号位异或为 0所以结果正。如果其中一个是负数绝对值乘法做完后把符号位异或的结果挂在最高位前面就行。你仔细品一下这个过程每一轮只做一次加法再做一次右移循环 n 次——这完全就是硬件喜欢重复执行的节奏。4.3 补码乘法Booth算法为什么非要看相邻两位原码一位乘法有一个天然缺陷它不能直接处理负数。虽然可以符号位单独处理但“绝对值相乘”等于先要把负数转成绝对值乘完再补符号这意味着一套额外的转换电路。在追求统一和简洁的硬件里人们希望直接用补码相乘符号位自然参与运算于是就有了 Booth 算法。Booth 算法的核心不是逐位检查乘数“是 0 还是 1”而是检查乘数相邻两位的跳变。规则我直接列出来设 Q0 是当前位Q-1 是比当前位更低一位的附加位初始时 Q-1 0。每次看 Q0 和 Q-1 的组合00 或 11部分积不变01部分积加被乘数 X 的补码10部分积减被乘数 X 的补码即加 -X 的补码。然后 A、Q、Q-1 联合执行算术右移保持 A 的符号位不变。整个过程需要 n1 次判断有的教材写 n 次体现在最后一次移位是否执行的细节差异上不同教材约定不同考试以你课堂版本为准。为什么这样能行因为二进制数可以看成一系列“连续相同位段”的差分表示。比如 00111100 这样的乘数直接一位一位判断要做很多次加法但用 Booth 的视角它等价于“在 01 处加一次在 10 处减一次”其余位置全部跳过。部分积加的次数少了乘法速度就上去了。同时因为做的是补码算术右移符号位被保留参与运算负数不需要额外转换。初学时你可能不习惯但 Booths 算法是真正体现了“聪明设计”的一个部件值得把规则表抄在笔记里反复对照。5. 除法比乘法更麻烦的“试商”过程5.1 恢复余数法不够减就把余数加回来除法是整个整数四则运算里最“折腾”的。乘法的基本单元只有加法和移位除法则要求你反复“试商”每移一位都要判断当前的余数够不够减去除数够的话商上 1不够的话商上 0。这个“判断”落在电路上就是一个减法操作之后看结果是不是负数。恢复余数法的流程是先把余数寄存器 R 清零把被除数 X 放在 Q 寄存器里。每一轮先把 R 和 Q 联合左移一位从 Q 的最高位移出一个比特进到 R 的低位然后用 R 减去除数 Y也就是 R R - Y。如果新 R 不小于 0说明够减Q 的最低位写入 1如果新 R 小于 0说明不够减就把 R 加回 Y恢复成左移之前的值同时 Q 的最低位写入 0。你看这个流程里最“笨”的地方就是“恢复”那一步减错了还要加回来。如果除数与被除数某一位试商经常不够减恢复操作会频繁发生整个除法周期被拉长。但它的思想非常朴素适合作为理解除法硬件的第一站几乎所有教材都会先讲它。5.2 追踪一遍8 ÷ 3 的完整试商过程我们拿 4 位二进制算 8 ÷ 3X 1000Y 0011R 0000Q 1000。第 1 轮R 和 Q 联合左移R 变成 0001Q 变成 0000。然后 R 减 Y0001 - 0011结果为负不够减Q0 写 0R 恢复成 0001。第 2 轮联合左移R 变成 0010Q 保持 0000。R 减 Y0010 - 0011结果为负Q0 写 0R 恢复成 0010。第 3 轮联合左移R 变成 0100Q 仍是 0000。R 减 Y0100 - 0011 0001结果非负够减Q0 写 1Q 变成 0001R 保持 0001。第 4 轮联合左移R 变成 0010Q 变成 0010。R 减 Y0010 - 0011结果为负Q0 写 0R 恢复成 0010。最终 Q 0010 2R 0010 2。8 2 × 3 2商和余数都正确。我把中间过程标出来是希望你看到两个容易混的点一是每轮开头都会把 Q 的最高位“喂”给 R所以被除数的比特是逐渐进入余数的二是 Q 里被除数腾空的位置正好用来从低位逐位“长”出商。整个过程就是余数寄存器和商寄存器一起“滚动”的节奏。5.3 加减交替法的改进思路不恢复余数恢复余数法虽然正确但“恢复”这个动作是额外的时间开销而且你还需要额外电路来区分“当前要不要恢复”。于是有了加减交替法也叫不恢复余数法国内教材里常写成“原码加减交替法”。它的思路其实很直接既然上一轮不够减我们已经知道当前的余数是负的那就不要费劲把它加回去下一轮直接“将错就错”——如果上一轮余数为负下一轮就左移后加上除数如果上一轮余数为正下一轮就左移后减去除数。换句话说每次加还是减由“上一次余数的符号”决定而不是上一轮减完再恢复再重新减。用数学来表达余数为正 Ri-1 时下一步做 Ri 2Ri-1 - Y余数为负时下一步做 Ri 2Ri-1 Y。这比恢复余数法省掉了“加回 Y”的完整步骤。唯一要注意的是最后一轮如果余数是负的结束后还要补一次加法修正余数使余数恢复为正。考试里这两种方法都要求会手算但理解上我是这样记的恢复余数法是“错了就回头”加减交替法是“错着往前走最后再纠正”。前者每一步都清晰后者更快也很能体现硬件的“物理思维方式”。6. 把知识变成分数题型、进位延迟与常见失分点6.1 这一章的常见题型基本绕不开这五类第一类是数制转换和补码范围题看似送分但每年都有人丢分比如问 8 位补码能表示多少个数答案不是 128 而是 256范围是 -128 到 127。第二类是画电路或补逻辑表达式最常见的是让你补全一位全加器、画出 4 位超前进位加法器的进位生成电路这种题考的就是 G 和 P 的表达式你把 C 的递推式写清楚画门电路其实只是翻译。第三类是手算乘法原码一位乘法、补码一位乘法各来一道考察你流程和右移方向是否记混。第四类是除法手算恢复余数法几乎是必考加减交替法也常作为进阶题出现。第五类是溢出判断给你一个加法结果让你说明是否溢出并要求列出 V C1 ⊕ C2 的推导过程。这五类题看着多但共同点只有一个它们在考你“过程”而不是考你“结果”。所以平时练习时一定要把每轮寄存器状态、每一次移位的方向、符号位的处理原原本本写出来。我见过太多同学心算能力很强直接写出最终答案结果中间过程分全没了。6.2 进位延迟的计算背结论不如会推导加法器延迟是最容易被突击复习的一部分因为每本教材给的参数记号不太一样。但核心逻辑是一致的延迟来自“进位路径经过了多少个门”。串行进位加法器每一位的进位要经过一个“与门或门”的复合延迟所以 n 位加法器的进位延迟差不多按 n 线性增长。而超前进位加法器只要把进位表达式用门电路展开每一位的进位最多经过固定的几级门延迟几乎和位宽无关。题目里如果给出了每个门的延迟 t一般套路是先判断进位是串行还是并行然后数最高位的进位从最低位开始要穿几级门。比如串行 8 位加法器最低位进位要经过 8 个进位单元每个单元约 2 个门延迟总延迟就是 16t再叠加最后一级求和的异或门延迟 t最终大概 17t 左右。不同教材对“门延迟”的假设不同但你只要会数“几级门”分数就跑不掉了。我建议你把这部分当应用题做而不是背公式。因为只要题目把延迟参数改一改背公式就会出错而“数门”的方法是永远通用的。6.3 我自己复习时踩过的三个坑第一个坑原码乘法和补码乘法的移位方向记混。原码一位乘法对 A 和 Q 做的是逻辑右移最高位补 0补码乘法做的是算术右移A 的最高位保持符号。我当时图省事拿一种思路套所有题结果补码乘法算出个完全离谱的数。解决办法很简单在草稿纸开头就写明“这一步是逻辑右移还是算术右移”每题都写写十道题之后就再也忘不掉了。第二个坑Booth 算法里“减被乘数”的实现。很多人投机取巧把被乘数先变负再求补但正确顺序是先把被乘数转成补码再对整个补码取负也就是按位取反再加 1。因为减一个补码数等价于加上这个补码数的相反数而补码的相反数就是“取反加一”。这个顺序反了符号位和数值位都会崩。第三个坑手算除法忘了“最后修正”。加减交替法最后如果余数为负需要加一次除数修正恢复余数法如果出现不够减后的“恢复”恢复后余数也不能直接当最终余数用要看清楚你写的是修正前还是修正后的值。考试阅卷时中间每步的 R 都是有步骣分的别在最后一步功亏一篑。如果说这一章能有什么“必杀技”我觉得就是自己动手把 5×3、8÷3、71 这三个例子从头到尾算三遍。第一遍照着书看第二遍合上书自己推第三遍把寄存器状态画成表格当作别人向你请教时的讲稿。算完这三遍后续学补码乘法除法、甚至浮点加减法时很多硬骨头都会软下来——因为当你摸清了硬件“只做加法、其余靠移位和循环”的老底再复杂的运算也不过是这些基础操作的套路组合。