# 习题 ### 习题 J.1 {#exercise-j-1} **[12]〈J.2〉** 用 n 位补码能够表示的最大、最小整数分别是什么？ ### 习题 J.2 {#exercise-j-2} **[20/25]〈J.2〉** J.2 节“有符号数”指出：最高位的输入进位与输出进位不同时，补码加法溢出。 a. **[20]〈J.2〉** 对输入、输出进位的四种组合，各给出一对整数实例，验证上述规则。 b. **[25]〈J.2〉** 解释为什么该规则总成立。 ### 习题 J.3 {#exercise-j-3} **[12]〈J.2〉** 用 4 位二进制数和 Booth 重编码计算 \((-8)\times(-8)\)。 ### 习题 J.4 {#exercise-j-4} **[15]〈J.2〉** 式 J.2.1、J.2.2 用于两个 n 位数的加法。推导减法的类似方程，此时以借位代替进位。 ### 习题 J.5 {#exercise-j-5} **[25]〈J.2〉** 若机器硬件不检测整数溢出，说明如何在软件中检测有符号加法的溢出。 ### 习题 J.6 {#exercise-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 {#exercise-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 {#exercise-j-8} **[15]〈J.3〉** 把非规格化数也考虑在内时，非负浮点数的编码顺序仍与整数顺序相同吗？ ### 习题 J.9 {#exercise-j-9} **[20]〈J.3〉** 编写程序，打印你所用计算机上表示浮点数的位模式。NaN 使用什么位模式？ ### 习题 J.10 {#exercise-j-10} **[15]〈J.4〉** 取 \(p=4\)，展示二进制浮点乘法算法如何计算 \(1.875\times1.875\)。 ### 习题 J.11 {#exercise-j-11} **[12/10]〈J.4〉** 考虑浮点乘法中的指数相加。 a. **[12]〈J.4〉** 实现指数加法的硬件是什么样的？ b. **[10]〈J.4〉** 若单精度偏置为 129 而非 127，实现指数加法会更容易还是更困难？ ### 习题 J.12 {#exercise-j-12} **[15/12]〈J.4〉** 浮点乘法的上溢检测讨论指出，单精度可在 9 位加法器中相加指数，以检测指数溢出。 a. **[15]〈J.4〉** 给出检测上溢的精确规则。 b. **[12]〈J.4〉** 改用 10 位加法器，检测是否会更容易？ ### 习题 J.13 {#exercise-j-13} **[15/10]〈J.4〉** 关于浮点乘法： a. **[15]〈J.4〉** 构造两个单精度浮点数，使其乘积直到最终舍入时才发生上溢。 b. **[10]〈J.4〉** 是否有某种舍入模式，使这种现象不可能发生？ ### 习题 J.14 {#exercise-j-14} **[15]〈J.4〉** 给出一个操作数为非规格化数、结果却为规格化数的乘法例子。最后需要移多少位？若输入均为双精度，最大可能移多少位？ ### 习题 J.15 {#exercise-j-15} **[15]〈J.5〉** 用 J.5 节的浮点加法算法，以 4 位精度计算 \(1.010_2-.1001_2\)。 ### 习题 J.16 {#exercise-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 {#exercise-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 {#exercise-j-18} **[12]〈J.4、J.5〉** 如何用两个并行加法器，避免浮点乘法最后单独进行舍入进一的加法？ ### 习题 J.19 {#exercise-j-19} **[30/10]〈J.5〉** 本题给出只用一个加法器、把浮点加法所需加法次数从三次减至两次的方法。 a. **[30]〈J.5〉** 令 A、B 为异号整数，a、b 为其绝对值。证明，对无符号数 a、b 执行以下步骤可得到 A+B。 1. 对其中一个操作数逐位取反。 2. 用循环进位（end-around carry）将取反后的操作数与另一个未取反的操作数相加。 3. 若产生进位输出，结果采用未取反操作数的符号。 4. 否则，对结果逐位取反，并采用被取反操作数的符号。 b. **[10]〈J.5〉** 利用上述结果，说明 J.5 节浮点加法算法的第 2、4 步如何只需一次加法完成。 ### 习题 J.20 {#exercise-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 {#exercise-j-21} **[10/20/15/15/15]〈J.6〉** 正确舍入的迭代除法。a、b 为 p 位有效数浮点数，双精度时 p=53。令精确商 \(q=a/b\)，且 \(1\le q<2\)。迭代结果 \(\bar q\) 多保留几位，满足 \(0 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 {#exercise-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 {#exercise-j-23} **[15]〈J.7〉** 两次舍入与一次舍入可能不同的例子使用了中点取偶规则。如果中点总向上舍入，两次舍入仍有危险吗？ ### 习题 J.24 {#exercise-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 {#exercise-j-25} **[讨论]〈J.7〉** MIPS 的异常处理方法需要快速检测两个浮点操作数是否可能导致异常，并尽量避免误报。你能提出实用的检测方法吗？其性能成本取决于浮点数的分布，这在 Knuth [1981] 和 Swartzlander [1990] 收录的 Hamming 论文中有讨论。 ### 习题 J.26 {#exercise-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 {#exercise-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 {#exercise-j-28} **[15]〈J.9〉** 普通 Booth 重编码第 i 步采用的 b 的倍数为 \(a_{i-1}-a_i\)。你能为基 4 Booth，即重叠三位组，找到类似公式吗？ ### 习题 J.29 {#exercise-j-29} **[20]〈J.9〉** 按图 J.27 的方式展开图 J.29，画出各个加法器。 ### 习题 J.30 {#exercise-j-30} **[25]〈J.9〉** 为基 8 Booth 重编码写出类似图 J.25 的表格。 ### 习题 J.31 {#exercise-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 {#exercise-j-32} **[15]〈J.9〉** 正文讨论了商数字为 −2、−1、0、1、2 的基 4 SRT 除法。如果还允许 ±3，应以什么关系代替 \(|r_i|\le2b/3\)？ ### 习题 J.33 {#exercise-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 {#exercise-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 {#exercise-j-35} **[12]〈J.6、J.9〉** remainder-step 的讨论假定采用逐位除法。若改用高基数除法，需要作哪些变化？ ### 习题 J.36 {#exercise-j-36} **[25]〈J.9〉** 图 J.28 没有利用阵列可流水化的能力。能否设计一种把最底 CSA 的输出反馈到下部 CSA、而非最顶 CSA 的方案，使它比图 J.28 更快？