考研笔记

定点数的乘除运算

乘除法在硬件上没有加减法那样的”一步到位”办法。加法可以靠先行进位压成常数级延迟，乘除法则本质上是一串加减与移位的迭代， 位就要 轮。这是乘除法指令的 CPI 远高于加减法的根本原因，也是第 5 章讲流水线时乘法器要单独开一条通路的原因。

本节的两条主线：乘法怎样把”逐位相加”变成硬件能做的形式，除法怎样在”不能试错”的电路里做试商。

机制

乘法的位宽：

两个 位数相乘，乘积最多 位。这不是保险起见，而是紧的： 确实需要 位，加符号位正好 。

由此得到一个在 C 里天天踩的坑：

int a = 100000, b = 100000;
long long c = a * b;        /* 溢出：乘法在 int 域完成，结果 1410065408 */
long long d = (long long)a * b;  /* 正确：10000000000 */

乘法的结果类型由操作数决定，与赋值目标无关。 a * b 两个都是 int，乘法就在 32 位里做，高 32 位直接丢弃，之后再扩展已经晚了。硬件层面 x86 的 imul 其实同时产生了高低两半（放在 EDX:EAX），是 C 的类型规则丢掉了高半部。

手工乘法到机器乘法：三点改造

竖式乘法是”逐位判断 → 移位 → 全部加起来”。直接照搬到硬件有两个麻烦：需要 位宽的加法器，且要同时存 个部分积。

机器的做法是三点改造：

  1. 被乘数不左移，改为部分积右移。 这样加法器只需 位宽——每次都是”当前部分积的高半部 + 被乘数”。
  2. 每次只做一次加法，加完立刻右移，不积攒。
  3. 移出的低位直接进入乘积的低半部，乘数寄存器腾出的位置正好装它，乘数寄存器和乘积低半部共用一组触发器。

于是硬件只需要：一个 位加法器、三个 位寄存器，做 轮”判断—加—移位”。

原码一位乘法：符号单独算

原码乘法把问题拆成两半，因为原码的符号位与数值位本来就是分离的：

符号数值

数值部分按绝对值做 轮：看乘数最低位，是 1 就加 ，是 0 就加 0，然后部分积连同乘数一起逻辑右移一位。

注意这里是逻辑右移（补 0），因为参与运算的是绝对值，全程为正，没有符号可保。

原码乘法的缺点很明显：符号要单独处理，需要额外的判断和最后的拼接，控制逻辑不统一。

补码一位乘法（Booth 算法）

Booth 的目标是让符号位也参与运算，一套流程走到底。

做法：在乘数最低位之后附加一位 ，然后每轮看相邻两位 ：

动作
00部分积不变
01部分积 补
10部分积 补（即减 ）
11部分积不变

然后算术右移一位（补符号位，不是补 0——这是与原码乘法的关键差别）。共做 轮， 是含符号位的字长。

为什么是相邻两位，为什么能处理负数，答案在一个恒等式里：一段连续的 1，等价于”在它上方加一次、在它下方减一次”。 而 这一对，正好在扫描到 1 段的下沿时看到 10（触发减）、扫描到 1 段的上沿时看到 01（触发加），段内部一律 11（什么都不做）。Booth 算法就是这个恒等式的逐位实现。

负数能被自动处理，是因为补码的最高位权是 ：把符号位也纳入扫描后，最高位那次 10 恰好贡献一个减法，正是那个负权。

验证一遍：（），附加 ，扫描序列 0 1 0 1 0：

完整手算：补，补，，。部分积 初值 0000。

轮动作
初000001010
110 → 算术右移000110101
201 → 算术右移111101010
310 → 算术右移000100101
401 → 算术右移111100010

结果 1111 0001 ，即 。符号自动正确，没有任何单独的符号处理。

关联对照：Booth 的"一加一减"与移位优化是同一个恒等式

编译器把 优化成 ，用的正是 ，即 。这与 Booth 算法处理连续 1 段的原理完全相同，只是一个发生在编译期、一个发生在运行时的硬件里。参见 2.2.2。

阵列乘法器：用面积换时间

一位乘法要 轮，太慢。阵列乘法器把 个”与门 + 全加器”排成方阵，一次性把所有部分积同时算出来再并行归约，延迟降到 甚至 ，代价是门数从 涨到 。

这是本章第三次出现”面积换时间”——先行进位加法器、桶形移位器、阵列乘法器，三者是同一个设计哲学的三次应用。

除法：位宽与前提

位被除数除以 位除数，得到 位商和 位余数。它有一个加法乘法都没有的前提：商必须装得下。

  • 定点小数：要求 ，否则商 ，超出定点小数范围。
  • 定点整数：要求商在 位范围内。

不满足前提就是除法溢出，见下。

恢复余数法

模仿竖式除法：“试着减一下，减不动就还回去”。

每一轮：余数左移一位，减去除数。

  • 结果 ：够减，商上 1，余数保留。
  • 结果 ：不够减，商上 0，再把除数加回去（恢复余数），然后进入下一轮。

“加回去”这一步是纯粹的浪费：它不产生任何信息，只是撤销上一次操作。最坏情况下 轮里做了 次加减。

加减交替法（不恢复余数法）

核心观察：如果这一轮减完是负数 ，恢复余数法会做 ，然后下一轮做 。

而 可以直接由 一步算出：左移后加除数，根本不需要先恢复。

于是规则简化成：

上一轮余数商上本轮动作
1左移后减除数
0左移后加除数

“够减就减、不够减就加”，加减交替，故得名。 每轮固定一次加减，共 次，比恢复余数法省掉最多 次操作。

收尾要校正：最后一轮结束后，若余数为负，需再加一次除数才是真正的余数。这一步容易漏。

C 的整数除法与取整方向

C99 起明确规定：整数除法向零截断，取模的符号跟随被除数。恒等式 (a/b)*b + a%b == a 在所有情况下成立。

这与算术右移的向负无穷取整不一致，是 2.2.2 已经点过的裂缝：，而 。

边界

除法溢出

除法是唯一会让机器真的停下来的定点运算。

加减乘溢出时机器只置 OF 然后继续（见 2.2.3），除法溢出则在 x86 上直接触发 #DE 除法错误异常，程序被内核终止或转入异常处理。

两种情形：

  • 除数为 0。
  • 商超出目标位宽。最典型的是 ：数学结果 超出 int 范围，触发异常。这正是补码非对称性的又一个后果。

“除以零在 C 里是未定义行为”和”机器上触发除法异常”是两个层面的说法，前者是语言不作承诺，后者是这台机器实际发生的事。

逻辑右移 vs 算术右移在乘法中的分工

这一条最容易记混：

算法部分积右移方式原因
原码一位乘逻辑右移（补 0）运算的是绝对值，全程非负
补码一位乘（Booth）算术右移（补符号位）部分积是补码，可能为负

判据是”部分积有没有符号”，不是”被乘数有没有符号”。

乘法的高半部不是”溢出”

得到 位是正常结果，不是溢出。只有当程序只保留低 位时，丢弃高半部才可能造成信息丢失。

x86 提供两套指令：mul/imul 的单操作数形式产生完整的 位（EDX:EAX），双操作数形式只保留低 位并按有符号溢出置 OF。C 的 * 对应后者。

408 的考法与实际硬件的差距

真实 CPU 早已不用一位乘法：乘法用 Wallace 树 + 阵列，除法用 SRT 算法（一次出多位商）。教材讲一位乘除法，目的是把”加减 + 移位”这条主线讲清楚，不是描述现代实现。

考试实际会问的是：位宽关系、Booth 的判断表与步数、加减交替法的规则与校正、除法溢出条件、取整方向。完整手算全过程出现在真题里的频率不高，但判断表必须能背。

对照速查

原码一位乘补码一位乘（Booth）
符号单独异或自动处理
判断依据乘数最低 1 位相邻 2 位
部分积右移逻辑算术
轮数（数值位）（含符号位）
恢复余数法加减交替法
不够减时加回除数再继续不加回，下轮改为加
每轮加减次数1~2 次固定 1 次
收尾无余数为负时加一次除数

考点

  • 的积是 位；C 中 int * int 仍是 int，需先转宽类型
  • 原码乘：符号异或 + 绝对值相乘 + 逻辑右移
  • Booth：附加位 ，看相邻两位，01 加 / 10 减 / 00、11 不动，算术右移
  • Booth 的原理是 ，一段连续 1 换成一加一减
  • 加减交替法每轮固定一次加减，最后余数为负要加一次除数校正
  • 除法溢出会触发异常，是唯一会中断程序的定点运算
  • 溢出
  • C 的整数除法向零截断，与算术右移的向负无穷不同

链接

反向链接