# J.2 整数算术的基本技术 学过计算机算术的读者会发现，本节的大部分内容属于复习。 ## 行波进位加法 加法器通常由多个简单部件组合而成。半加器和全加器就是构造加法器的基本部件。半加器接收两个位 \(a\)、\(b\)，输出和位 \(s\) 与进位 \(c_{\mathrm{out}}\)。从数学上说， $$ s=(a+b)\bmod 2,\qquad c_{\mathrm{out}}=\left\lfloor\frac{a+b}{2}\right\rfloor, $$ 其中 \(\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\)，对应的逻辑方程为： $$ s=a\bar b\bar c+\bar a b\bar c+\bar a\bar b c+abc.\tag{J.2.1} $$ $$ c_{\mathrm{out}}=ab+ac+bc.\tag{J.2.2} $$ 用小部件构造 \(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)\)，常数因子却很小。因此，短的行波进位加法器常被用作较大加法器的基本模块。 ![由多个全加器构成的行波进位加法器](/figures/app-j/fig-j-1.png) {#fig-J.1 .wide .expand num="J.1" caption="行波进位加法器，由 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 保存低半部分。 ![无符号整数乘法器与除法器的框图](/figures/app-j/fig-j-2.png) {#fig-J.2 .wide .expand num="J.2" caption="n 位无符号整数的 (a) 乘法器和 (b) 除法器框图。每一步乘法根据 A 的最低位，把 P 与 B 或 0 相加，和写回 P，再把 P 和 A 右移一位。每一步除法先把 P 和 A 左移一位，再从 P 中减去 B；若差非负，将差写入 P，并把 A 的最低位置为 1。"} 图中 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\)。** | P | A | 操作 | |---|---|---| | `00000` | `1110` | 初始值 | | `00001` | `110` | 第 1 步 (i)：移位 | | `−00010` | `1100` | 第 1 步 (ii)：减 `00011`；(iii)：结果为负，商位置 0 | | `00001` | `1100` | 第 1 步 (iv)：恢复 | | `00011` | `100` | 第 2 步 (i)：移位 | | `00000` | `1001` | 第 2 步 (ii)：减 `00011`；(iii)：结果非负，商位置 1 | | `00001` | `001` | 第 3 步 (i)：移位 | | `−00010` | `0010` | 第 3 步 (ii)：减 `00011`；(iii)：结果为负，商位置 0 | | `00001` | `0010` | 第 3 步 (iv)：恢复 | | `00010` | `010` | 第 4 步 (i)：移位 | | `−00001` | `0100` | 第 4 步 (ii)：减 `00011`；(iii)：结果为负，商位置 0 | | `00010` | `0100` | 第 4 步 (iv)：恢复；商为 \(0100_2\)，余数为 \(00010_2\) | **(b) 不恢复余数除法：同样计算 \(14/3\)，B 始终为 \(0011_2\)。** | P | A | 操作 | |---|---|---| | `00000` | `1110` | 初始值 | | `00001` | `110` | 第 1 步 (i-b)：移位 | | `11110` | `1100` | 第 1 步 (ii-b)：减 \(b\)，即加其补码 `11101`；(iii)：P 为负，商位置 0 | | `11101` | `100` | 第 2 步 (i-a)：移位 | | `00000` | `1001` | 第 2 步 (ii-a)：加 \(b\)，即 `00011`；(iii)：P 非负，商位置 1 | | `00001` | `001` | 第 3 步 (i-b)：移位 | | `11110` | `0010` | 第 3 步 (ii-b)：减 \(b\)，即加 `11101`；(iii)：P 为负，商位置 0 | | `11100` | `010` | 第 4 步 (i-a)：移位 | | `11111` | `0100` | 第 4 步 (ii-a)：加 \(b\)，即 `00011`；(iii)：P 为负，商位置 0 | | `00010` | `0100` | 余数为负，再加 `00011`，作最后一次恢复；商为 \(0100_2\)，余数为 \(00010_2\) | 图 J.3　(a) 恢复余数除法与 (b) 不恢复余数除法的数值例子。 {#fig-J.3 .wide .expand num="J.3"} 为什么不恢复余数法有效？令 \(r_k\) 表示第 \(k\) 步之后 (P,A) 的内容，暂不计放入 A 空闲低位中的商位。以上例为例，初始 \(r_0=14\)，第一次移位后得到 28。恢复余数法首先把 \(r_k\) 变成 \(2r_k\)，再从高半部分减去 \(b\)，相当于计算 \(2r_k-2^n b\)。若结果非负，两种算法没有区别。若结果为负，恢复余数法将它恢复为 \(2r_k\)，下一步得到 $$ r_{\mathrm{res}}=2(2r_k)-2^n b. $$ 不恢复余数法则保留负的结果，下一步先移位，再加上 \(b\)，得到 $$ r_{\mathrm{nonres}}=2(2r_k-2^n b)+2^n b=4r_k-2^n b=r_{\mathrm{res}}. $$ 因此，在上述比较中，两种算法得到的 (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\) 的数值可写为 $$ -a_{n-1}2^{n-1}+a_{n-2}2^{n-2}+\cdots+a_1 2^1+a_0.\tag{J.2.3} $$ 例如，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\)。于是，所有加法累积得到 $$ \sum_{i=0}^{n-1}b(a_{i-1}-a_i)2^i =b\left(-a_{n-1}2^{n-1}+a_{n-2}2^{n-2}+\cdots+a_1 2+a_0\right)+ba_{-1}. $$ 结合式 J.2.3 与 \(a_{-1}=0\)，右边正是补码意义下的 \(b\times a\)。 | P | A | 操作 | |---|---|---| | `0000` | `1010` | 将 \(-6=1010_2\) 装入 A，\(-5=1011_2\) 装入 B | | `0000` | `1010` | 第 1 步 (i)：\(a_0=a_{-1}=0\)，按规则 I 加 0 | | `0000` | `0101` | 第 1 步 (ii)：移位 | | `0101` | `0101` | 第 2 步 (i)：\(a_1=1,a_0=0\)，按规则 III 减 \(b\)，即加 \(-b=0101_2\) | | `0010` | `1010` | 第 2 步 (ii)：移位 | | `1101` | `1010` | 第 3 步 (i)：\(a_2=0,a_1=1\)，按规则 II 加 \(b=1011_2\) | | `1110` | `1101` | 第 3 步 (ii)：算术移位，最左位移入 1 | | `0011` | `1101` | 第 4 步 (i)：\(a_3=1,a_2=0\)，按规则 III 减 \(b\)，即加 `0101` | | `0001` | `1110` | 第 4 步 (ii)：移位；最终结果 \(00011110_2=30\) | 图 J.4　Booth 重编码的数值例子。\(a=-6\) 与 \(b=-5\) 相乘，得到 30。 {#fig-J.4 .wide .expand num="J.4"} 实现 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 总结了几种常见机器的处理方式。 | 机器 | 有符号溢出触发陷阱？ | 无符号溢出触发陷阱？ | 有符号溢出置标志位？ | 无符号溢出置标志位？ | |---|---|---|---|---| | VAX | 使能时触发 | 否 | 是；Add 设置 V 位 | 是；Add 设置 C 位 | | IBM 370 | 使能时触发 | 否 | 是；Add 设置条件码 | 是；Logical add 设置条件码 | | Intel 8086 | 否 | 否 | 是；Add 设置 V 位 | 是；Add 设置 C 位 | | MIPS R3000 | 两种 add 指令，一种总触发，另一种从不触发 | 否 | 否；软件必须根据操作数和结果的符号判断 | 否；软件必须根据操作数和结果的符号判断 | | SPARC | 否 | 否 | Addcc 设置 V 位，Add 不设置 | Addcc 设置 C 位，Add 不设置 | 图 J.5　各种机器处理整数溢出的方式。8086 与 SPARC 都有在 V 位置位时触发陷阱的指令，因此在溢出时触发陷阱需要额外一条指令。 {#fig-J.5 .wide .expand num="J.5"} > 译注：表中的 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。 | 语言 | 整数除法 | 余数 | |---|---|---| | FORTRAN | \(-5/3=-1\) | \(\operatorname{MOD}(-5,3)=-2\) | | Pascal | \(-5\operatorname{DIV}3=-1\) | \(-5\operatorname{MOD}3=1\) | | Ada | \(-5/3=-1\) | \(-5\operatorname{MOD}3=1\)；\(-5\operatorname{REM}3=-2\) | | C | \(-5/3\) 未定义 | `−5 % 3` 未定义 | | Modula-3 | \(-5\operatorname{DIV}3=-2\) | \(-5\operatorname{MOD}3=1\) | 图 J.6　各种程序设计语言中的整数除法与整数余数示例。 {#fig-J.6 .wide .expand num="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\) 位数和一个单比特的第三操作数，第三操作数就是上一次加法产生的进位。多精度数通常存储在数组中，因此必须能够递增数组指针，而不破坏进位位。