J.2 整数算术的基本技术

学过计算机算术的读者会发现，本节的大部分内容属于复习。

行波进位加法

加法器通常由多个简单部件组合而成。半加器和全加器就是构造加法器的基本部件。半加器接收两个位 $a$、$b$，输出和位 $s$ 与进位 $c_{\mathrm{out}}$。从数学上说，

其中 $\lfloor\ \rfloor$ 表示向下取整。写成逻辑方程，则为 $s=a\bar b+\bar a b$、$c_{\mathrm{out}}=ab$，其中 $ab$ 表示 $a\land b$，$a+b$ 表示 $a\lor b$。半加器也称为 (2,2) 加法器，因为它有两个输入、两个输出。

全加器是 (3,2) 加法器，定义为 $s=(a+b+c)\bmod2$、$c_{\mathrm{out}}=\lfloor(a+b+c)/2\rfloor$，对应的逻辑方程为：

用小部件构造 $n$ 位加法器时，主要问题是如何将进位从一个部件传到下一个部件。最直接的办法是采用行波进位加法器（ripple-carry adder）：把 $n$ 个全加器连接起来，如图 J.1 所示。本附录图中的最低有效位一律位于右侧。加法器的输入为 $a_{n-1}a_{n-2}\cdots a_0$ 和 $b_{n-1}b_{n-2}\cdots b_0$；前者表示数值 $a_{n-1}2^{n-1}+a_{n-2}2^{n-2}+\cdots+a_0$。第 $i$ 个加法器的输出 $c_{i+1}$ 接入下一个、即第 $i+1$ 个加法器的进位输入，最低位的进位输入 $c_0$ 置为 0。既然最低位进位接 0，最低位加法器本可采用半加器。不过，后面会看到，把这个进位置为 1 对减法很有用。

电路产生输出所需的时间，通常与信号经过的最大逻辑级数成正比。不过，逻辑级数与实际延迟的准确关系高度依赖工艺，所以比较加法器时，我们只比较逻辑级数。行波进位加法器有多少级？由 $a_0$、$b_0$ 算出 $c_1$ 需要两级，再由 $c_1,a_1,b_1$ 算出 $c_2$ 又需要两级，依此类推直到 $c_n$，共需 $2n$ 级。整数运算的典型 $n$ 值是 32，双精度浮点运算则是 53。行波进位加法器最慢，但也最便宜：只需 $n$ 个简单单元，以简单而规则的方式连接。

与 J.8 节讨论的设计相比，行波进位加法器相当慢，为什么还要使用它？在 CMOS 等工艺中，虽然它的时间复杂度为 $O(n)$，常数因子却很小。因此，短的行波进位加法器常被用作较大加法器的基本模块。

图中 Full adder 表示全加器；$a_i,b_i$ 为输入位，$s_i$ 为和位，$c_i$ 为进位。

基 2 乘法与除法

最简单的乘法器逐位计算两个无符号数的乘积，如图 J.2(a) 所示。待相乘的数 $a_{n-1}\cdots a_0$ 与 $b_{n-1}\cdots b_0$ 分别置于寄存器 A、B，寄存器 P 初值为 0。每一步乘法分为两部分。

乘法步骤

1. 若 A 的最低有效位为 1，就把含有 $b_{n-1}\cdots b_0$ 的寄存器 B 加到 P；否则向 P 加上全 0。和写回 P。
2. 将 P、A 组成的寄存器对右移一位。第 1 步的进位移入 P 的最高位，P 的最低位移入 A 的最高位，A 的最低位移出后弃去。

重复 $n$ 次之后，乘积位于 (P,A) 中，A 保存低半部分。

图中 Carry-out 为进位输出，Shift 为移位；乘法器的 P 和 A 各为 $n$ 位，另有一位进位；除法器的 P 为 $n+1$ 位，A 为 $n$ 位，B 在最高端补 0。

除法器与乘法器很相似，也逐位产生商。要计算 $a/b$，仍把 $a$ 放入 A、$b$ 放入 B，P 置 0。下面的算法称为恢复余数除法（restoring division），每一步包含：

1. 将寄存器对 (P,A) 左移一位。
2. 从 P 中减去 B。
3. 如果结果为负，把 A 的最低位置 0；否则置 1。
4. 如果结果为负，向 P 加回 B，以恢复原值。

重复 $n$ 次后，A 中是商，P 中是余数。这正是纸笔长除法的二进制形式；图 J.3(a) 给出了一个例子。图 J.2(b) 是相应硬件框图。乘除法器可以共用同一套硬件，主要变化是移位必须能够向两个方向进行。

恢复操作也可以省去：当一次减法产生负数时，保留它，在下一步作相应补偿。这称为不恢复余数除法（nonrestoring division）。每一步如下：

• 若 P 为负：(i-a) 将 (P,A) 左移一位；(ii-a) 把 B 加到 P。
• 若 P 非负：(i-b) 将 (P,A) 左移一位；(ii-b) 从 P 中减去 B。
• (iii) 若 P 为负，将 A 的最低位置 0；否则置 1。

重复 $n$ 次之后，A 保存商。若 P 非负，它就是余数；否则，还需要恢复一次，即加上 $b$，才得到余数。图 J.3(b) 给出了数值例子。步骤 (i-a) 与 (i-b) 相同，因此很容易想到先统一移位，再判断 P 的符号。但这样不行，因为移位可能使符号位丢失。

(a) 恢复余数除法：$14=1110_2$ 除以 $3=11_2$，B 始终为 $0011_2$。

(b) 不恢复余数除法：同样计算 $14/3$，B 始终为 $0011_2$。

图 J.3　(a) 恢复余数除法与 (b) 不恢复余数除法的数值例子。

为什么不恢复余数法有效？令 $r_k$ 表示第 $k$ 步之后 (P,A) 的内容，暂不计放入 A 空闲低位中的商位。以上例为例，初始 $r_0=14$，第一次移位后得到 28。恢复余数法首先把 $r_k$ 变成 $2r_k$，再从高半部分减去 $b$，相当于计算 $2r_k-2^n b$。若结果非负，两种算法没有区别。若结果为负，恢复余数法将它恢复为 $2r_k$，下一步得到

不恢复余数法则保留负的结果，下一步先移位，再加上 $b$，得到

因此，在上述比较中，两种算法得到的 (P,A) 位模式相同。

我们一直假定 $a,b$ 为无符号数，即 $0\le a,b\le2^n-1$。乘法中 P 用 $n$ 位就足够；除法中，P 需要 $n+1$ 位来表示符号，加法器也要有 $n+1$ 位。

恢复余数除法似乎要多做一次加法，为什么仍有人采用它？常见实现并不真的执行第 (iv) 步的加法，而是检查减法结果的符号，仅当结果非负时才把结果装入 P。还有一点：开始除法前，必须检查除数是否为 0。

有符号数

有符号数有四种常见表示：原码（sign magnitude）、补码（two’s complement）、反码（one’s complement）和移码（biased）。原码以最高位表示符号，其余 $n-1$ 位表示绝对值。补码中，一个数与其相反数的编码之和为 $2^n$。反码通过逐位取反得到负数，一个数与其相反数的编码之和为 $2^n-1$。在这三种表示中，非负数都采用通常的二进制表示。移码则把每个数 $k$ 编码为无符号数 $k+\text{bias}$；只要 $k+\text{bias}\ge0$，$k$ 就可以为负。典型偏置值为 $2^{n-1}$。

例如，用 4 位表示 $k=3=0011_2$：其相反数的原码为 $1011_2$；补码为 $1101_2$，因为 $3+13=16$。

反码将 $0011_2$ 逐位取反，因此 $-k$ 为 $1100_2$。若移码的偏置为 $2^{n-1}=8$，则 $k$ 表示为 $k+\text{bias}=1011_2$，$-k$ 表示为 $-k+\text{bias}=0101_2$。

补码是最广泛采用的整数表示，本节也采用它。它的一大优点是有符号加法非常简单：只需丢弃最高位的进位输出。例如，计算 $5+(-2)$，将 $0101_2$ 与 $1110_2$ 相加得 $0011_2$，恰为正确结果 3。补码数 $a_{n-1}\cdots a_1a_0$ 的数值可写为

例如，4 位补码 $1101_2$ 表示 $-1\cdot2^3+1\cdot2^2+0\cdot2^1+1\cdot2^0=-8+4+1=-3$，与上例一致。

当运算结果超出所用表示能够容纳的范围时，就发生溢出（overflow）。例如，4 位无符号数 $6=0110_2$ 与 $11=1011_2$ 相加得 17，其二进制表示 $10001_2$ 无法容纳于 4 位。无符号溢出很容易检测：最高有效位产生进位输出，当且仅当发生溢出。补码稍复杂：进入最高位的进位与从最高位产生、随后被丢弃的进位不同，当且仅当发生溢出。上面的 $5+(-2)$ 中，进入和离开最左位的进位都为 1，所以没有溢出。

对补码数求负，先逐位取反，再加 1。例如，$0011_2$ 取反得 $1100_2$，加 1 得 $1101_2$。所以，用加法器计算 $a-b$，只需输入 $a$ 与 $\bar b$（$b$ 的逐位反码），并把最低位进位置 1。这也解释了为什么图 J.1 最右侧使用全加器。

补码乘法不如加法简单。直观方法是先把两个操作数都变成非负数，执行无符号乘法，若原操作数异号，再把结果取负。这个方法容易理解，却需要额外时间和硬件。更好的方法是沿用图 J.2(a)：把 $a$ 装入 A、$b$ 装入 B。由于 B 始终保存 $b$，下文交替使用 B 和 $b$。如果 B 可以为负而 A 非负，只需保证 P 右移时采用算术移位，即向最高位移入 P 的符号位，而不是加法进位，就能将无符号乘法改成补码乘法。此时，$n$ 位加法器相加的是范围为 $-2^{n-1}$ 到 $2^{n-1}-1$ 的补码数。

再考虑 $a$ 为负的情况。处理它的方法称为 Booth 重编码。这是计算机算术中的基本技术，J.9 节还会用到。前面的乘法算法从最低位到最高位检查 $a$。若 $a=7=0111_2$，步骤 (i) 依次加 B、加 B、加 B、加 0。Booth 重编码把 7 改写为 $8-1=1000_2-0001_2=100\bar1$，其中 $\bar1$ 表示 $-1$。于是可依次减 B、加 0、加 0、加 B。这个过程同时使用加减法，比无符号算法复杂，但在 $a$ 为负时体现出优势。

例如，令 $a=-4=1100_2$。先把 $1100_2$ 视为无符号数 12，再重编码为 $12=16-4=10000_2-0100_2=10\bar100$。乘法仅迭代 $n=4$ 次，最高位被忽略，最终减去 $0100_2=4$ 倍的乘数，恰得正确结果。因此，对 $a$ 重编码后，无论正负都能使用相同算法。具体说，只要允许某些步骤从 P 减去 $b$，而不是仅加 $b$ 或 0 即可。若 A 的初值为 $a_{n-1}\cdots a_0$，第 $i$ 步 A 的最低位为 $a_i$，乘法步骤 (i) 改为：

1. 若 $a_i=0,a_{i-1}=0$，向 P 加 0。
2. 若 $a_i=0,a_{i-1}=1$，向 P 加 B。
3. 若 $a_i=1,a_{i-1}=0$，从 P 减 B。
4. 若 $a_i=1,a_{i-1}=1$，向 P 加 0。

第一步 $i=0$ 时，规定 $a_{-1}=0$。

例题　计算 $-6$ 乘以 $-5$ 时，寄存器对 (P,A) 的值依次是什么？

解答　见图 J.4。

以上四种情况可以统一表述为：第 $i$ 步向 P 加 $(a_{i-1}-a_i)\mathrm B$。于是，所有加法累积得到

结合式 J.2.3 与 $a_{-1}=0$，右边正是补码意义下的 $b\times a$。

图 J.4　Booth 重编码的数值例子。$a=-6$ 与 $b=-5$ 相乘，得到 30。

实现 Booth 重编码规则最简单的方法，是把 A 向右扩展一位，用新的一位保存 $a_{i-1}$。与先把所有负操作数取正的朴素方法相比，这种方法不需要额外步骤，也不必对负数单独处理，只略微增加控制逻辑。若乘法器与除法器共用，硬件本来就具备减 $b$ 的能力。因此，补码乘法的一种简单实现就是：右移 P 时保留符号，保存 A 最近移出的一位，并据此决定向 P 加还是减 $b$。

Booth 重编码通常是设计有符号乘法硬件的最佳方法。但若硬件未直接支持，在软件或微码中实现它常因条件判断和分支而过慢。如果硬件支持算术移位，能正确处理负的 $b$，则可以把 $a$ 当作无符号数，用前面的算法执行前 $n-1$ 步；若 $a<0$，此时 A 的最低位为 1，就从 P 减 $b$，否则不加也不减；最后再移位一次，总共移位 $n$ 次。它实际上计算 $b(-a_{n-1}2^{n-1}+\cdots+a_1 2+a_0)$，依式 J.2.3 正是所求补码乘积。若不支持算术移位，先把操作数转为非负数可能更合适。

最后补充两点。测试有符号乘法例程时，一个很好的测试用例是 $(-2^{n-1})\times(-2^{n-1})$，因为只有这种情况会产生 $2n-1$ 位的结果。与乘法不同，硬件除法通常先把操作数转为非负数，再执行无符号除法。

由于除法比乘法慢得多，而且出现频率更低，处理符号的额外时间对除法的影响相对较小。

系统层面的问题

设计指令集时，需要解决若干整数算术问题，这里讨论其中几项。

首先，如何处理整数溢出？有符号与无符号运算的溢出检测不同，使问题更复杂。对有符号运算，可以在溢出时置标志位、触发陷阱，或者不作处理；最后一种情况下，必须由软件检查溢出。对程序员最方便的方法，是设置一个使能位：使能时溢出触发陷阱，不使能时只置标志位；或者提供两种不同的加法指令。这样，无论是否需要陷阱，都只需一条指令。J.7 节还会看到，这与 IEEE 浮点标准处理浮点溢出的方式相似。图 J.5 总结了几种常见机器的处理方式。

图 J.5　各种机器处理整数溢出的方式。8086 与 SPARC 都有在 V 位置位时触发陷阱的指令，因此在溢出时触发陷阱需要额外一条指令。

译注：表中的 8086“V 位”为原书记法，保留其原有术语。

再看无符号加法。图 J.5 的体系结构都不在无符号溢出时触发陷阱，因为无符号算术主要用于地址运算。用加法实现无符号地址的减法很方便。例如，$n=4$ 时，可以向无符号地址 $10=1010_2$ 加 $14=1110_2$，以减去 2。这会产生溢出，但我们不希望因此触发陷阱。

第二个问题涉及乘法。两个 $n$ 位数相乘，应该返回 $2n$ 位结果，还是只返回低 $n$ 位，并在完整结果容纳不下时报告溢出？支持 $n$ 位结果的理由是，几乎所有高级语言都把乘法定义为同类型整数变量之间的运算，结果仍是该类型的整数变量。

因此，编译器不会生成利用双倍精度结果的代码。支持 $2n$ 位结果的理由则是，汇编语言例程可以利用它显著加速多精度整数乘法，约可快 3 倍。

第三个问题出现在希望每周期执行一条指令的机器中。通常难以让乘法或除法像加法、寄存器间移动一样快。可能的办法有三种：第一，提供单周期的 multiply-step 指令，例如执行 Booth 算法的一步；第二，在浮点单元中执行整数乘法，并将其纳入浮点指令集，DLX 就采用此法；第三，在 CPU 中设置自主运行的乘法单元，或者保证固定周期数后给出结果，由编译器安排等待，或者提供互锁。这些考虑也适用于除法。最初的 SPARC 提供 multiply-step，却没有 divide-step；MIPS R3000 则由自主单元执行乘除法。较新的 SPARC 体系结构加入了整数乘法指令。HP Precision Architecture 的设计者尤其深入地分析了乘除操作数的出现频率，并据此设计乘法和除法步骤，详见 Magenheimer 等 [1988]。

最后一个问题是负数的整数除法与余数。例如，$-5\operatorname{DIV}3$ 与 $-5\operatorname{MOD}3$ 应是多少？计算 $x\operatorname{DIV}y$ 和 $x\operatorname{MOD}y$ 时，负的 $x$ 足够常见，值得认真考虑；负的 $y$ 则很少见。如果硬件提供相应指令，其语义应与高级语言一致。遗憾的是，各语言并不一致，见图 J.6。

图 J.6　各种程序设计语言中的整数除法与整数余数示例。

译注：本表按原书所述历史语境保留，不能据此判断现行语言标准的语义；特别是 C 栏的“未定义”是原书措辞。

在这些定义中，有一种明显更优，即 $x\operatorname{DIV}y=\lfloor x/y\rfloor$。于是 $5\operatorname{DIV}3=1$，$-5\operatorname{DIV}3=-2$。MOD 应满足 $x=(x\operatorname{DIV}y)y+x\operatorname{MOD}y$，使 $x\operatorname{MOD}y\ge0$。所以 $5\operatorname{MOD}3=2$，$-5\operatorname{MOD}3=1$。这种定义有很多优点，其中包括：

1. 对大小为 $N$ 的散列表计算索引时，可以用 MOD N，并保证结果处于合法的 $0$ 到 $N-1$ 范围。
2. 图形处理中，在不同坐标系之间转换时，0 附近不会出现“异常”。例如，将每英寸 100 点系统中的坐标 $x$ 转为每英寸 70 点位图显示器上的坐标 $y$，公式 $y=(70x)\operatorname{DIV}100$ 会把一到两个 $x$ 坐标映射到每个 $y$ 坐标。但若像 Pascal 那样把 DIV 定义为 $x/y$ 向 0 舍入，$-1,0,1$ 三个点都会映射到 0。
3. $x\operatorname{MOD}2^k$ 等价于与低 $k$ 位为 1 的掩码作按位 AND；$x\operatorname{DIV}2^k$ 等价于算术右移 $k$ 位。

译注：这里“余数非负”的结论沿用本段正除数的情境；若除数为负，不能由上述恒等式推出余数非负。

还需提醒一个多精度加法陷阱。许多指令集提供一种加法变体，接收两个 $n$ 位数和一个单比特的第三操作数，第三操作数就是上一次加法产生的进位。多精度数通常存储在数组中，因此必须能够递增数组指针，而不破坏进位位。