J.5 浮点加法

浮点运算通常接收两个 $p$ 位精度的输入，返回 $p$ 位结果。理想算法先精确执行运算，再按当前舍入模式舍入到 $p$ 位。上一节的乘法正是如此。实现 IEEE 算术的硬件必须给出与理想算法相同的结果，却不一定真的执行理想算法；加法就有更好的方法。

先看 6 位二进制数 $1.10011_2$ 与 $1.10001_2\times2^{-5}$ 相加。对阶后为

  1.10011
+  .0000110001

用 6 位加法器、暂时丢弃第二加数的低位，得到

  1.10011
+  .00001
----------
  1.10100

第一个被丢弃的位为 1，但仅凭它无法判断是否进一，还需检查余下的 0001。其实只要像乘法那样用 sticky 位记录其中是否有非零位即可。因此，两个 $p$ 位数相加，用 $p$ 位加法器已足够，只需另存第一个丢弃位（舍入位），以及其余丢弃位的 OR（sticky 位），再按图 J.11 判断。本例 sticky 为 1，需要进一，最终为 $1.10101_2$。

再看：

  1.11011
+  .0101001

6 位加法器得到：

  1.11011
+  .01010
----------
 10.00101

由于左侧产生进位，舍入位不再是第一个被丢弃的位，而变成和的最低位 1。丢弃的 01 作 OR 得 sticky=1。两者均为 1，所以和的高 6 位 $10.0010_2$ 应进一，结果为 $10.0011_2$。

再看减法：

  1.00000
−  .00000101111

最简单的计算方式是把 $-.00000101111_2$ 转成补码，使差变成和：

  1.00000
+ 1.11111010001

6 位加法器得到：

  1.00000
+ 1.11111
----------
  0.11111

最高位抵消后，必须把第一个丢弃位，即保护位，补到结果的最低端，得到 $0.111110_2$；第二个丢弃位则成为舍入位。这与乘法算法的情况 (1) 相似。舍入位为 1 还不足以作决定，剩余 0001 的 OR 给出 sticky=1，所以最终进一为 $0.111111_2$。可见，减法抵消最高位时，需要一个保护位。若最高两位都抵消，是否就需要两个保护位？不需要。如果 $x,y$ 足够接近，以至于差的最高两位抵消，那么 $x-y$ 会是精确的，根本不需要保护位。

加法比乘法复杂，是因为它可能因操作数符号而实际变成减法。加法可能在左侧产生进位；减法可能发生抵消；两者都会改变舍入位的位置。不过，无需先求精确和再舍入，只要用最高 $p$ 位的和，以及舍入位、sticky 位，就能确定结果。

下面详细给出浮点加法算法。令两个加数为 $a_1,a_2$，指数和有效数分别为 $e_i,s_i$。输入已经解包，因此 $s_i$ 含显式首位。算法分八步：

1. 若 $e_1<e_2$，交换操作数，使 $d=e_1-e_2\ge0$。暂定结果指数为 $e_1$。
2. 若 $a_1,a_2$ 异号，把 $s_2$ 替换成其补码。
3. 把 $s_2$ 放入 $p$ 位寄存器，右移 $d$ 位；若上一步取过补码，高位移入 1。移出的位中，最高一位置入 $g$，次高位置入 $r$，其余位的 OR 置入 sticky。
4. 把 $s_1$ 与保存 $s_2$ 的 $p$ 位寄存器相加，得到初步有效数 $S=s_1+s_2$。若两加数异号、S 最高位为 1、且没有进位输出，则 S 为负，需用其补码替换。这只可能发生在 $d=0$ 时。
5. 若两加数同号，且第 4 步有进位输出，则 S 右移一位，高位移入进位 1。否则，左移直到规格化；第一次左移时把 $g$ 移入低位，之后移入 0。相应调整结果指数。
6. 调整 $r,s$。若第 5 步右移，令 $r$ 为移位前 S 的最低位，$s:=g\lor r\lor s$；若不移位，令 $r:=g$、$s:=r\lor s$；若左移一次，$r,s$ 不变；若左移至少两次，令 $r=s=0$。原书解释，最后一种情况仅发生于两加数异号且指数相同，此时第 4 步计算精确。
7. 按图 J.11 舍入 S：对应条件成立时，在最低位加 1。若产生进位，则右移 S 并调整指数。这样得到最终有效数。
8. 确定符号。若两加数同号，结果同号；若异号，结果取决于原来哪个为负、第 1 步是否交换，以及第 4 步是否对 S 取补码，见图 J.12。

译注：第 6 步的赋值应按调整前的 $g,r,s$ 同时计算，不能先覆盖 $r$ 再计算 $s$。原书“左移至少两次只会发生于指数相同”过于严格：指数相差 1 也可能严重抵消，例如 $1.000_2\times2^0-1.111_2\times2^{-1}=0.0001_2$；该差同样精确，故置 $r=s=0$ 的处理仍适用。

图 J.12　两加数异号时的结果符号规则。swap 指第 1 步交换操作数，compl 指第 4 步取补码；“任意”对应原表的空白项，即无关条件。

例题　用上述算法计算 $(-1.001_2\times2^{-2})+(-1.111_2\times2^0)$。

解答　初始 $s_1=1.001,e_1=-2,s_2=1.111,e_2=0$。

1. $e_1<e_2$，交换；$d=2$，暂定指数为 0。
2. 两操作数都为负，不对 $s_2$ 取负。
3. 交换后的 $s_2=1.001$ 右移两位，得 $s_2=.010,g=0,r=1,s=0$。
4. $1.111+.010=(1)0.001$，因此 S=.001，并有进位。
5. 右移并补入进位，S=1.000，指数增为 1。
6. 舍入位是原和的最低位，即 1；sticky 为 $0\lor1\lor0=1$。
7. $r\land s$ 为真，按图 J.11 进一，得 S=1.001。
8. 两加数均为负，结果为负。原页末式写作 $-S\times2^{\mathrm{exp}}=1.001_2\times2^1$。

译注：原页末式右侧漏了负号；与题目及本步文字一致的结果应为 $-1.001_2\times2^1$。

例题　计算 $(-1.010_2)+1.100_2$。

解答　$s_1=1.010,e_1=0,s_2=1.100,e_2=0$。

1. 不交换，$d=0$，暂定指数为 0。
2. 异号，把 $s_2$ 替换成补码 0.100。
3. $d=0$，不移位，$r=g=s=0$。
4. $1.010+0.100=1.110$。异号、最高位为 1、无进位，因此对和取补码，得 S=0.010。
5. 左移两位，S=1.000，指数减为 −2。
6. 左移两次，$r=g=s=0$。
7. 舍入不需要加 1。
8. 结果为 $\text{sign}\times1.000\times2^{-2}$。查图 J.12：取过补码、未交换、原 $a_1$ 为负，所以结果为正，即 $1.000_2\times2^{-2}$。

加速加法

估算上述算法的时间：第 2 步可能需要一次加法，第 4 步需要一到两次，第 7 步可能再需一次。若 $p$ 位加法耗时 T，单精度 $p=24$、双精度 $p=53$，看起来至少需要 4T。但这过于悲观：第 4 步若需两次加法，两输入必然同指数、异号，差是精确的，第 7 步无需进一，所以最多三次加法。

同样，第 3、5 步似乎各需一次可变移位，但若 $|e_1-e_2|\le1$，第 3 步最多右移一位，只有第 5 步需要可变移位；若 $|e_1-e_2|>1$，第 3 步需要可变移位，第 5 步却最多左移一位。因此最多只执行一次可变移位。即便如此，三次串行加法对 53 位双精度有效数来说仍很耗时。

加速方法之一是流水线，J.10 节会介绍商业芯片实例。另一种是并行进行两次加法，Intel 860 就采用了它 [Kohn and Fu 1989]；下面说明它如何把延迟从 3T 降为 T。

分三种情况。首先，两操作数同号，需要合并第 4、7 步。第 4 步是否产生进位尚不确定，因此和的最高位位置未知；用两个加法器分别覆盖两种可能。第一个假定无进位，因而可事先算出 $r,s$。若应进一，计算 $S=s_1+s_2+1$，其中加 1 的位置是 $s_1$ 的最低位，可通过把普通加法器的最低进位输入置 1 实现；否则照常计算 $S=s_1+s_2$。若 $r=1,s=0$，还需知道和的最低位，它也能很快预先算出。第二个加法器假定会进位，此时 $r,s$ 和加 1 的位置不同，但也能事先算出。究竟是否有进位，要到加法完成后才知道；两个加法器并行运行，必有一个产生正确答案。

其次，两输入异号、同指数。此时和精确，无需舍入，但结果符号要等加法结束才知道。不要在第 2 步先取补码，因为那要一次加法；改为并行计算 $\bar s_1+s_2+1$ 与 $s_1+\bar s_2+1$。前者把对 $s_1$ 取补码与求和合并，得到 $s_2-s_1$；后者得到 $s_1-s_2$。

其中一个非负，就是最终结果的绝对值。这样，所有加法仍由两个并行加法器在一步完成。

最后，两输入异号、指数不同，情况更复杂。若 $|e_1-e_2|>1$，差的首位仅可能在两个位置之一，类似普通加法。若 $|e_1-e_2|=1$，可能发生抵消，首位几乎可以出现在任何位置；不过，只有差的首位与 $s_1$ 首位同位置时才可能需要进一。因此，一个加法器假定需要进一，另一个假定不需要，即可合并第 4、7 步。但第 2 步的加法怎么办？

考虑第 4 步中两个操作数的对齐关系：

       ←── p 位 ──→
s₁      1.xxxxxxx
s₂ −            1yyzzzzz

若标为 z 的位全为 0，$S=s_1-s_2$ 的高 $p$ 位可用 $s_1+\bar s_2+1$ 算出；若至少一个 z 为 1，则用 $s_1+\bar s_2$。因此一次加法就能得到差，但仍需取得 $s_2$ 补码对应的 $g,r$，供第 7 步舍入。

为此，将第 2、4 步合并：第 2 步不对 $s_2$ 取补码；把加法器向右扩展两位，扩展的和记为 $S'$。在 $s_1$ 右侧补两个 0 得 $s_1'$，在 $s_2$ 后附上初步的 $g,r$ 得 $s_2'$。若第 3 步得到的初步 sticky 为 1，计算 $S'=s_1'+\overline{s_2'}$；若 sticky 为 0，则计算 $s_1'+\overline{s_2'}+1$。现在，$S'$ 的最低两位就是正确的 $g,r$，sticky 已在第 3 步正确算出。再与第 4、7 步的合并方法结合，就能在一次加法时间 T 内得到结果。

还有一些细节，见 Santoro、Bewick 与 Horowitz [1989] 及习题 J.17。该论文虽针对乘法，但很多讨论同样适用于加法。习题 J.19 还给出了另一种符号—数值形式的加法方法。

非规格化数

与乘法不同，即使一个输入为非规格化数，以上加法算法也几乎不变。只需检测指数域是否为 0；若为 0，解包有效数时不补首位 1，并把内部偏置指数置为 1，算法其余部分照常运行。

处理非规格化输出时，第 5 步略作修改：左移 S，直到规格化，或指数达到 $E_{\min}$，即偏置指数为 1。若指数为 $E_{\min}$，且舍入后 S 的最高位为 1，结果仍是规格化数，按通常方式打包，省去首位 1。

若最高位为 0，则结果是非规格化数，存回格式时指数域应置 0。J.7 节将讨论检测下溢的精确规则。

译注：原文此处写“结果解包时”（unpacked），但语境是把内部结果编码回浮点格式，即打包；译文据此表述，并保留此说明。

上溢很容易检测：只有第 5 步右移时，偏置指数被增至单精度的 255、双精度的 2047，或者舍入后发生同样情况，才会出现上溢。