习题

习题 J.1

[12]〈J.2〉 用 n 位补码能够表示的最大、最小整数分别是什么？

习题 J.2

[20/25]〈J.2〉 J.2 节“有符号数”指出：最高位的输入进位与输出进位不同时，补码加法溢出。

a. [20]〈J.2〉 对输入、输出进位的四种组合，各给出一对整数实例，验证上述规则。

b. [25]〈J.2〉 解释为什么该规则总成立。

习题 J.3

[12]〈J.2〉 用 4 位二进制数和 Booth 重编码计算 $(-8)\times(-8)$ 。

习题 J.4

[15]〈J.2〉 式 J.2.1、J.2.2 用于两个 n 位数的加法。推导减法的类似方程，此时以借位代替进位。

习题 J.5

[25]〈J.2〉 若机器硬件不检测整数溢出，说明如何在软件中检测有符号加法的溢出。

习题 J.6

[15/15/20]〈J.3〉 将以下数分别表示成 IEEE 单精度与双精度浮点数。

a. [15]〈J.3〉 10。

b. [15]〈J.3〉 10.5。

c. [20]〈J.3〉 0.1。

习题 J.7

[12/12/12/12/12]〈J.3〉 对下列单精度浮点数，写出其二进制值、十进制值，以及 IEEE 编码。

a. [12]〈J.3〉 小于 1 的最大数。

b. [12]〈J.3〉 最大数。

c. [12]〈J.3〉 最小的正数（限规格化数）。

d. [12]〈J.3〉 最大非规格化数。

e. [12]〈J.3〉 最小正数。

习题 J.8

[15]〈J.3〉 把非规格化数也考虑在内时，非负浮点数的编码顺序仍与整数顺序相同吗？

习题 J.9

[20]〈J.3〉 编写程序，打印你所用计算机上表示浮点数的位模式。NaN 使用什么位模式？

习题 J.10

[15]〈J.4〉 取 $p=4$ ，展示二进制浮点乘法算法如何计算 $1.875\times1.875$ 。

习题 J.11

[12/10]〈J.4〉 考虑浮点乘法中的指数相加。

a. [12]〈J.4〉 实现指数加法的硬件是什么样的？

b. [10]〈J.4〉 若单精度偏置为 129 而非 127，实现指数加法会更容易还是更困难？

习题 J.12

[15/12]〈J.4〉 浮点乘法的上溢检测讨论指出，单精度可在 9 位加法器中相加指数，以检测指数溢出。

a. [15]〈J.4〉 给出检测上溢的精确规则。

b. [12]〈J.4〉 改用 10 位加法器，检测是否会更容易？

习题 J.13

[15/10]〈J.4〉 关于浮点乘法：

a. [15]〈J.4〉 构造两个单精度浮点数，使其乘积直到最终舍入时才发生上溢。

b. [10]〈J.4〉 是否有某种舍入模式，使这种现象不可能发生？

习题 J.14

[15]〈J.4〉 给出一个操作数为非规格化数、结果却为规格化数的乘法例子。最后需要移多少位？若输入均为双精度，最大可能移多少位？

习题 J.15

[15]〈J.5〉 用 J.5 节的浮点加法算法，以 4 位精度计算 $1.010_2-.1001_2$ 。

习题 J.16

[10/15/20/20/20]〈J.5〉 某些情况下可以确定 a+b 能被浮点数精确表示，不需要舍入。

a. [10]〈J.5〉 若 a、b 同指数、异号，解释为什么 a+b 精确。J.5 节“加速加法”使用过这个性质。

b. [15]〈J.5〉 给出指数相差 1、符号相反、但 a+b 不精确的例子。

c. [20]〈J.5〉 若 $a\ge b\ge0$ ，计算 a−b 时 a 的最高两位抵消，解释为什么差精确。正文介绍抵消时提到过这个性质。

d. [20]〈J.5〉 若 $a\ge b\ge0$ ，且指数相差 1，证明除非 a−b 的最高位与 a 的最高位处于同一位置，否则差精确。这一点在“加速加法”中提到过。

e. [20]〈J.5〉 若 a−b 或 a+b 的结果是非规格化数，证明它精确。J.7 节“下溢”提到过这个性质。

习题 J.17

[15/20]〈J.5〉 使用并行加法器的快速浮点加法，取 $p=5$ 。

a. [15]〈J.5〉 对 $a=1.0111_2,b=.11011_2$ ，逐步执行快速加法算法。

b. [20]〈J.5〉 若舍入模式为向 $+\infty$ ，上述例子中，假定会产生进位的加法器会遇到什么额外问题？提出解决办法。

习题 J.18

[12]〈J.4、J.5〉 如何用两个并行加法器，避免浮点乘法最后单独进行舍入进一的加法？

习题 J.19

[30/10]〈J.5〉 本题给出只用一个加法器、把浮点加法所需加法次数从三次减至两次的方法。

a. [30]〈J.5〉 令 A、B 为异号整数，a、b 为其绝对值。证明，对无符号数 a、b 执行以下步骤可得到 A+B。

对其中一个操作数逐位取反。

用循环进位（end-around carry）将取反后的操作数与另一个未取反的操作数相加。
若产生进位输出，结果采用未取反操作数的符号。
否则，对结果逐位取反，并采用被取反操作数的符号。

b. [10]〈J.5〉 利用上述结果，说明 J.5 节浮点加法算法的第 2、4 步如何只需一次加法完成。

习题 J.20

[20/15/20/15/20/15]〈J.6〉 迭代求平方根。

a. [20]〈J.6〉 用 Newton 方法推导平方根迭代算法，公式中会出现一次除法。

b. [15]〈J.6〉 你能想到的浮点数除以 2 的最快方法是什么？

c. [20]〈J.6〉 若除法慢，平方根迭代也会慢。对 $f(x)=1/x^2-a$ 应用 Newton 方法，推导不使用除法的算法。

d. [15]〈J.6〉 假定“除以 2：浮点加法：浮点乘法”的耗时比为 1:2:4。乘法与除法的耗时比满足什么条件时，(c) 的每次迭代比 (a) 更快？

e. [20]〈J.6〉 采用 (a) 的方法，要在三次迭代后达到双精度，初始估计需要多少个正确位？可忽略舍入误差。

f. [15]〈J.6〉 假定 spice 在 TI 8847 上运行时，16.7% 时间花在平方根例程中；这一比例曾在其他机器测得。利用图 J.36，假设迭代三次，如果改为用 (a) 的软件算法实现平方根，spice 会慢多少？

习题 J.21

[10/20/15/15/15]〈J.6〉 正确舍入的迭代除法。a、b 为 p 位有效数浮点数，双精度时 p=53。令精确商 $q=a/b$ ，且 $1\le q<2$ 。迭代结果 $\bar q$ 多保留几位，满足 $0<q-\bar q<2^{-p}$ 。以下要求 $\bar q<q$ ，即使 q 可以精确表示为浮点数，也必须严格小于。

a. [10]〈J.6〉 若 x 为浮点数， $1\le x<2$ ，紧随 x 的下一个可表示数是什么？

b. [20]〈J.6〉 说明如何由 $\bar q$ 计算具有 p+1 位精度、且满足 $|q-q'|<2^{-p}$ 的 $q'$ 。

c. [15]〈J.6〉 假定舍入到最近值，证明正确舍入的商必为 $q'$ 、 $q'-2^{-p}$ 、 $q'+2^{-p}$ 之一。

d. [15]〈J.6〉 根据 $q'$ 的最低位与 $a-bq'$ 的符号，给出从 $q'$ 得到正确舍入商的规则。

e. [15]〈J.6〉 对另外三种舍入模式回答 (c)。

习题 J.22

[15]〈J.6〉 验证 J.6 节展开 Newton 迭代所得的公式。提示：若

x_n=x_0(2-x_0b)\prod_{i=1}^{n}\left[1+(1-x_0b)^{2^i}\right],

则

\begin{aligned} 2-x_nb &=2-x_0b(2-x_0b)\prod\left[1+(1-x_0b)^{2^i}\right]\\ &=2-\left[1-(1-x_0b)^2\right]\prod\left[1+(1-x_0b)^{2^i}\right]. \end{aligned}

译注：提示中的乘积上限 n 与左侧 $x_n$ ，和正文以 $x_{i+1}$ 编号的展开式存在一位索引偏移。若沿用正文迭代编号， $x_n$ 的乘积上限应为 n−1。

习题 J.23

[15]〈J.7〉 两次舍入与一次舍入可能不同的例子使用了中点取偶规则。如果中点总向上舍入，两次舍入仍有危险吗？

习题 J.24

[10/10/20/20]〈J.7〉 J.7 节“精度”中斜体命题的某些情况不难证明。

a. [10]〈J.7〉 若先舍入到 q 位、再到 p 位，与直接舍入到 p 位不同，原二进制数必须具有什么形式？

b. [10]〈J.7〉 证明：p 位数相乘，若 $q\ge2p$ ，先舍入到 q 位再到 p 位，等于直接舍入到 p 位。

c. [20]〈J.7〉 若 a、b 是同号 p 位数，证明当 $q\ge2p+1$ 时，a+b 先舍入到 q 位再到 p 位，等于直接舍入到 p 位。

d. [20]〈J.7〉 对异号的 a、b 证明 (c)。

习题 J.25

[讨论]〈J.7〉 MIPS 的异常处理方法需要快速检测两个浮点操作数是否可能导致异常，并尽量避免误报。你能提出实用的检测方法吗？其性能成本取决于浮点数的分布，这在 Knuth [1981] 和 Swartzlander [1990] 收录的 Hamming 论文中有讨论。

习题 J.26

[12/12/10]〈J.8〉 跳跃进位加法器。

a. [12]〈J.8〉 假定时间与逻辑级数成正比，n 位加法器分成固定 k 位块，一次加法需要多久？

b. [12]〈J.8〉 k 取什么值最快？

c. [10]〈J.8〉 解释为什么时间复杂度为 $O(\sqrt n)$ 。

习题 J.27

[10/15/20]〈J.8〉 补全以下加法器框图的细节。

a. [10]〈J.8〉 用 AND、OR 门实现图 J.15 的“1”“2”方框。

b. [15]〈J.8〉 图 J.19 中，顶行加法单元需要向 C 单元传递哪些信号？写出 C 单元的逻辑方程。

c. [20]〈J.8〉 扩展图 J.17，使其产生最终进位 $c_8$ 。

习题 J.28

[15]〈J.9〉 普通 Booth 重编码第 i 步采用的 b 的倍数为 $a_{i-1}-a_i$ 。你能为基 4 Booth，即重叠三位组，找到类似公式吗？

习题 J.29

[20]〈J.9〉 按图 J.27 的方式展开图 J.29，画出各个加法器。

习题 J.30

[25]〈J.9〉 为基 8 Booth 重编码写出类似图 J.25 的表格。

习题 J.31

[18]〈J.9〉 假设带符号数字数值 $a_{n-1}\cdots a_1a_0$ 、 $b_{n-1}\cdots b_1b_0$ 按 J.9 节例题相加。用 $a_i,a_{i-1},a_{i-2},b_i,b_{i-1},b_{i-2}$ 写出和的第 i 位 $s_i$ 的公式。

习题 J.32

[15]〈J.9〉 正文讨论了商数字为 −2、−1、0、1、2 的基 4 SRT 除法。如果还允许 ±3，应以什么关系代替 $|r_i|\le2b/3$ ？

习题 J.33

[25/20/30]〈J.9〉 关于图 J.34 的 SRT 商选择表：

a. [25]〈J.9〉 编写程序生成该表。

b. [20]〈J.9〉 该表关于 P 的正负具有一定对称性。能否利用它，只存正 P 的表项？

c. [30]〈J.9〉 若用 CSA 代替 CPA，商表输入由除数的 k 位和余数的 l 位组成；余数高位通过把和寄存器、进位寄存器的高 l 位相加得到。k、l 应是多少？编程生成相应商表。

习题 J.34

[12/12/12]〈J.9、J.12〉 最初生产的数百万片 Pentium 有时会给出错误除法结果。它使用与 J.9 节示例相似的基 4 SRT，但余数以保留进位形式存储，见 J.33(c)。Intel 表示缺陷来自商表的五个错误表项。

a. [12]〈J.9、J.12〉 错误表项本应给出 ±2，却给出 0。冗余表示似乎可能使算法在后续迭代中从错误商位“恢复”。证明 Pentium 缺陷无法如此恢复。

b. [12]〈J.9、J.12〉 浮点除法需对前面的整数 SRT 作两处修改：除数已规格化，不再需要步骤 1；初始余数可能不满足正确边界，Pentium 为 $|r|\le2b/3$ 。证明省去步骤 2(a) 的第一次左移可以解决这个问题。

c. [12]〈J.9、J.12〉 若错误表项对应的余数可能出现在第一次除法步骤，随机测试很快就会发现缺陷。原文括注此时“余数就是除数”（divisor）。实际并未很快发现，这说明索引到错误表项的余数值有什么特征？

译注：括注使用了 divisor（除数），但本附录前面将被除数有效数装入初始 P，因而这里“除数”与初始化叙述不一致，可能是 dividend（被除数）的笔误。

习题 J.35

[12]〈J.6、J.9〉 remainder-step 的讨论假定采用逐位除法。若改用高基数除法，需要作哪些变化？

习题 J.36

[25]〈J.9〉 图 J.28 没有利用阵列可流水化的能力。能否设计一种把最底 CSA 的输出反馈到下部 CSA、而非最顶 CSA 的方案，使它比图 J.28 更快？