【分析解答】
第 3 版 · OCR 辅助 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
# 【分析解答】
根据无符号数乘法运算和补码乘法运算算法，填写表3.4。
表 3.4 题 8 中填入结果后的表
[tbl-16.md](tbl-16.md)
对表3.4中结果分析如下。
（1）对于两个相同的机器数，作为无符号数进行乘法运算和作为带符号整数进行乘法运算，因为其所用的乘法算法不同，所以，乘积的机器数可能不同。但是，从表中看出，截断后的乘积是一样的，即不同的仅是乘积中的高 $n$ 位，而低 $u$ 位完全一样。
（2）对于 $n$ 位乘法运算，无论是无符号数乘法还是带符号整数乘法，若截取 $2n$ 位乘积的低 $n$ 位作为最终的乘积，则都有可能结果溢出，即 $n$ 位数字无法表示正确的乘积。虽然表中给出的带符号整数乘积截断后都没有发生溢出，但实际上还是存在溢出的情况，例如， $011 \times 011 = 001001$ ，截断后 $011 \times 011 = 001$ ，显然截断后的结果发生了溢出。
（3）表3.4中加粗的地方是截断后发生溢出的情况。可以看出，对于无符号整数乘法，若乘积中高 $n$ 位为全0，则截断后的低 $n$ 位乘积不发生溢出，否则溢出；对于带符号整数乘法，若高 $n$ 位中的每一位都等于低 $n$ 位中的第一位，则截断后的低 $n$ 位乘积不发生溢出，否则溢出。
9. 考虑以下C语言程序代码：
```c
int func1(unsigned short si)
{
return(si * 256);
}
int func2(unsigned short si)
{
return(si/256);
}
int func3(unsigned short si)
{
return(((short) si * 256)/256);
}
int func4(unsigned short si)
{
return(short)((si * 256)/256);
}
<!-- page: 70 -->
请回答下列问题：
（1）假设计算机硬件不提供乘除运算功能，能否用移位运算实现上述函数功能？函数 func1、func2、func3 和 func4 得到的结果各有什么特征？
（2）填写表 3.5（要求机器数用十六进制表示），并对表中的“异常”数据进行分析。
表 3.5 题 9 用表
[tbl-17.md](tbl-17.md)
（3）对于函数 func1 来说，用一位乘运算所花的时间开销大约是用移位运算的多少倍？对于函数 func2 来说，用不恢复余数除法所花的开销大约是用移位运算的多少倍？
## 【分析解答】
（1）编译器在处理变量与常数相乘时，往往以移位、加法和减法的组合运算来代替乘法运算。例如，对于表达式 $x * 20$，编译器可以利用 $20 = 16 + 4 = 2^4 + 2^2$，将 $x * 20$ 转换为 $(x < 4) + (x < 2)$，这样，一次乘法转换成了两次移位和一次加法。不管是无符号整数还是带符号整数的乘法，即使乘积溢出时，利用移位和加减运算组合的方式得到的结果都是和采用直接相乘的结果是一样的。
为了缩短除法运算的时间，编译器在处理一个变量与一个 2 的幂次形式的整数相除时，常采用右移运算来实现。无符号整数除法采用逻辑右移方式，带符号整数除法采用算术右移方式。两个整数相除，结果也一定是整数，在不能整除时，其商采用朝零方向舍入的方式，也就是截断方式，即将小数点后的数直接去掉，例如，$7/3 = 2, -7/3 = -2$。
对于无符号整数来说，采用逻辑右移时，高位补 0，低位移出，因此，移位后得到的商的值只可能变小而不会变大，即商朝零方向舍入。因此，不管是否能够整除，采用移位方式和直接相除得到的商完全一样。但是，对于带符号整数 $x$ 来说，如题 3 的分析解答中所说的那样，当计算 $x/2^k$ 时，若 $x < 0$，则不能直接将 $x$ 算术右移 $k$ 位，而应该先将 $x$ 加上偏移量 $(2^k - 1)$，然后再算术右移 $k$ 位。
因为 $256 = 2^{8}$，所以题目给出的函数中的乘、除运算可以分别用左、右移运算来实现。可用“左移 8 位”代替“乘 256”的操作，用“右移 8 位”代替“除以 256”的操作。func1(si)相当于将 si 逻辑左移 8 位，结果的最后 8 位都为 0；func2(si)相当于将 si 逻辑右移 8 位，结果的范围是 $0 \sim 255$；func3(si)相当于将 si 先算术左移 8 位，再算术右移 8 位，所以结果的范围是 $-128 \sim 127$；func4(si)相当于将 si 先逻辑左移 8 位，再逻辑右移 8 位，最后以带符号整数类型返回。因为最后是逻辑右移，高位补 0，所以，返回的总是正数，结果的范围是 $0 \sim 255$。
（2）函数 func1、func2、func3 和 func4 的执行结果填表如表 3.6 所示。
<!-- page: 71 -->
表 3.6 题 9 中填入结果后的表
[tbl-18.md](tbl-18.md)
在表3.6中，加粗数据是一些“异常”结果。当 si=256时，由于 256×si=65536，因此用16位无符号数无法表示实际结果，导致 func1(si)、func3(si)和 func4(si)都为0；当 si=65535时，由于 256×si溢出，导致 func1、func3和 func4的函数值出现了“异常”结果；当 si=128时，因为 256×128=32768，超过了short型数据的最大表示范围，发生溢出，其结果与 128<<8的操作结果一样，机器数都是8000H，其真正的值为-32768，再除以256，结果为-128，与对8000H算术右移8位得到的结果FF80H(值为-128)完全一样；当 si=255时，因为 256×255=65280，超过了short型数据的最大表示范围，发生溢出。因此，左移16位后得到乘积FF00H(真值为-256)，其第一位(符号位)为1，即乘积变成了负数，反映出乘积是一个溢出值。因此再除以256，结果应该是-1，显然，通过算术右移8位得到的结果FFFFH，其值也是-1。
（3）用移位操作代替乘、除运算，其程序执行时间会大大减少。采用桶型移位器进行移位时，移动任何位数都只要一次移位操作。假定一次移位操作所用时间和一次加/减运算时间一样，都是一个时钟周期T，那么，对于函数func1，采用一位乘法器时，两个16位数相乘的运算所需循环次数为16，每个循环内进行“判断-加法-右移”操作，其中判断操作是控制器在送出控制信号之前进行的，无须一个专门的时钟周期来实现，因此16位乘法运算所用时间大约为32T，由此可知，采用一位乘法运算，函数func1的执行时间大约是采用移位运算的32倍左右。对于函数func2，采用不恢复余数法时，两个16位数相除时所需循环次数为16，循环内有“判断-左移（上商）-加/减”操作，所用时间大约为32T，因此是采用移位运算的32倍左右。
10. 若一次加法需要 1ns, 一次移位需要 0.5ns。请分别估算用一位乘法、两位乘法、基于 CRA 的阵列乘法、基于 CSA 的阵列乘法 4 种方式计算两个 8 位无符号二进制数乘积时所需要的时间。
## 【分析解答】
对于8位无符号二进制数相乘，一位乘法需8次右移，8次加法，共计12ns；二位乘法需4次右移，4次加法，共计6ns；对于基于CRA的阵列乘法，每一级部分积不仅依赖于上一级部分积，还依赖于上一级最终的进位，而每一级进位又是串行进行的，所以最长的路径总共经过了 8+2×(8-1)=22 个单元节点（细胞模块），假定经过每个单元节点所花时间平均为0.5ns，则共计大约11ns；对于基于CSA的阵列乘法，本级进位与本级和能同时传送到下一级，且同级部分积之间互不依赖，因此只需进行 O(N)次简单加法（即半加或全加）运算，假定简单加法时间为8位加法器时间的一半，则一共大约为4ns。
<!-- page: 72 -->
11. 已知 $x = 10, y = -6$，采用 6 位机器数表示。请按如下要求计算，并把结果还原成真值。
(1) 求 $[x + y]_{\mathrm{H}}, [x - y]_{\mathrm{H}}$。
(2) 用原码一位乘法计算 $[x \times y]_{\mathrm{H}}$。
(3) 用补码一位乘法（布斯算法）计算 $[x \times y]_{\mathrm{H}}$。
(4) 用 MBA（基 4 布斯）乘法计算 $[x \times y]_{\mathrm{H}}$。
(5) 用不恢复余数法计算 $[x / y]_{\mathrm{H}}$ 的商和余数。
【分析解答】
先将 $x$ 和 $y$ 转换为二进制数。$x = 10 = +01010\mathrm{B}, y = -6 = -00110\mathrm{B}$。
(1) $[x]_{\mathrm{H}} = 0.01010\mathrm{B}, [y]_{\mathrm{H}} = 1.11010\mathrm{B}, [-y]_{\mathrm{H}} = 0.00110\mathrm{B}$. $[x + y]_{\mathrm{H}} = [x]_{\mathrm{H}} + [y]_{\mathrm{H}} = 0.01010\mathrm{B} + 1.11010\mathrm{B} = 0.00100\mathrm{B}$，因此，$x + y = 4$。$[x - y]_{\mathrm{H}} = [x]_{\mathrm{H}} + [-y]_{\mathrm{H}} = 0.01010\mathrm{B} + 0.00110\mathrm{B} = 0.10000\mathrm{B}$，因此，$x - y = +16$。
(2) $[x]_{\mathrm{H}} = 0.01010\mathrm{B}, [y]_{\mathrm{H}} = 1.00110\mathrm{B}$。将符号和数值部分分开处理。乘积的符号为 $0 \div 1 = 1$，数值部分采用无符号数乘法算法计算 $01010 \times 00110$ 的乘积。原码一位乘法过程：初始部分积为 0，在乘积寄存器前增加一个进位位。每次循环首先根据乘数寄存器中最低位决定 $+X$ 还是 $+0$，然后将得到的新进位、新部分积和乘数寄存器中的部分乘数一起逻辑右移一位。共循环 5 次，最终得到一个 10 位无符号数表示的乘积 00001 11100B。所以，$[x \times y]_{\mathrm{H}} = 10000111100\mathrm{B}$，因此，$x \times y = -60$。若结果取 6 位原码，则因为高 5 位 00001 是一个非 0 数，所以，结果溢出，即 $[x \times y]_{\mathrm{H}} \neq 11100$。验证：6 位原码的表示范围是 $-31 \sim +31$，显然乘积 $-60$ 不在其范围内，结果应该溢出。（过程略）
(3) $[x]_{\mathrm{H}} = 0.01010\mathrm{B}, [-x]_{\mathrm{H}} = 1.10110\mathrm{B}, [y]_{\mathrm{H}} = 1.11010\mathrm{B}$。采用布斯算法时，符号和数值部分一起参加运算，最初在乘数后面添 0，初始部分积为 0。每次循环先根据乘积寄存器中最低两位决定执行 $+X, -X$ 还是 $+0$ 操作，然后将得到的新的部分积和乘数寄存器中的部分乘数一起算术右移一位。$-X$ 用 $+[-x]_{\mathrm{H}}$ 实现。共循环 6 次。最终得到一个 12 位补码表示的乘积 111111 000100 B，所以，$[x \times y]_{\mathrm{H}} = 111111000100\mathrm{B}$，因此，$x \times y = -60$。若结果取 6 位补码，则根据乘积低 6 位 000100 的符号位为 0，而高 6 位为 111111，不等于全 0，说明结果溢出，即 $[x \times y]_{\mathrm{H}} \neq 0.00100$。验证：6 位补码的表示范围是 $-32 \sim +31$，显然乘积 $-60$ 不在其范围内，结果应该溢出。（过程略）
(4) $[x]_{\mathrm{H}} = 0.01010\mathrm{B}, [-x]_{\mathrm{H}} = 1.10110\mathrm{B}, [y]_{\mathrm{H}} = 1.11010\mathrm{B}$。采用 MBA 算法时，符号和数值部分一起参加运算，最初在乘数后面添 0，初始部分积为 0，并在部分积前加一位符号位 0。每次循环先根据乘积寄存器中最低 3 位决定执行 $+X, +2X, -X, -2X$、还是 $+0$ 操作，然后将得到的新的部分积和乘数寄存器中的部分乘数一起算术右移两位。$-X$ 和 $-2X$ 分别采用 $+[-x]_{\mathrm{H}}$ 和 $+2[-x]_{\mathrm{H}}$ 的方式进行。共循环 3 次。最终得到一个 12 位补码表示的乘积 1111 1100 0100B，所以，$[x \times y]_{\mathrm{H}} = 111111000100\mathrm{B}$，因此，$x \times y = -60$。（过程略）
(5) $[x]_{\mathrm{H}} = 0.01010\mathrm{B}, [y]_{\mathrm{H}} = 1.00110\mathrm{B}$。将符号和数值部分分开处理。商的符号为 $0 \div 1 = 1$，数值部分采用无符号数除法算法计算 01010B 和 00110B 的商和余数。无符号数不恢复余数除法过程：初始中间余数为 0 00000 01010 0，其中，最高位为添加的符号位，用于判断余数是否大于或等于 0；最后一位 0 为第一次上的商，该位商只是用于判断结果是否溢出，不包含在最终的商中。因为结果肯定不溢出，所以该位商可以直接上 0，并先做一次
<!-- page: 73 -->
$-Y$ 操作得到第一次中间余数，然后进入循环。每次循环首先将中间余数和商一起左移一位，然后根据上一次上的商（或余数的符号）决定执行 $+Y$ 还是 $-Y$ 操作，以得到新的中间余数，最后根据中间余数的符号确定上商为 0 还是 1。$-Y$ 采用 $+[-\gamma]_{\#}$ 的方式进行。整个循环内执行的要点是“正、1、减：负、0、加”。共循环 5 次。最终得到一个 6 位无符号数表示的商 0 00001 和余数 00100，其中第一位商 0 必须去掉，添上符号位后得到最终的商的原码表示为 1 00001，余数的原码表示为 0 0100。因此，$x/y$ 的商为 $-1$，余数为 4。（过程略）
12. 假设浮点数的阶码和尾数均采用补码表示，且位数分别为 5 位和 7 位（均含 2 位符号位，即变形补码）。若有两个数 $X = 2^7 \times 15/16, Y = 2^5 \times 3/8$，要求用浮点加法计算 $X + Y$ 的最终结果是什么？
## 【分析解答】
先将两个数的尾数部分变成分母为 32 的形式，即 $X = 2^7 \times 30/32, Y = 2^5 \times 12/32, X$ 和 $Y$ 转换成题设的浮点数格式，$X: 00.11110, 00111: Y: 00.01100, 00101$，然后进行浮点数加/减运算。$Y$ 对阶后为：00.00011，00111，因此尾数相加结果为 $00.11110 + 00.00011 = 01.00001$，该尾数形式需要右规，即尾数右移一位，若采用“0 舍 1 入”舍入法，右规后尾数为 00.10001，阶码加 1 后为 01000，因此，右规后为 00.10001，01000，最后要对该结果进行溢出判断。显然，阶码的两个符号位不同，故结果溢出。
13. 假设有两个实数 $x$ 和 $y, x = -68, y = -8.25$，它们在 C 语言程序中定义为 float 型变量（用 IEEE 754 单精度浮点数格式表示），$x$ 和 $y$ 分别存放在寄存器 A 和寄存器 B 中。另外，还有两个寄存器 C 和寄存器 D。寄存器 A、寄存器 B、寄存器 C、寄存器 D 都是 32 位寄存器。请回答下列问题（要求最终用十六进制表示二进制序列）。
（1）寄存器 A 和寄存器 B 中的内容分别是什么？
（2）若 $x$ 和 $y$ 相加后的结果存放在寄存器 C 中，则寄存器 C 中的内容是什么？
（3）若 $x$ 和 $y$ 相减后的结果存放在寄存器 D 中，则寄存器 D 中的内容是什么？
## 【分析解答】
（1）$x = -68 = -1000100B = -1.0001B \times 2^6$，因此，符号位为 1，阶码为 1000 0101B，尾数小数部分为 000 1000 0000 0000 0000 0000B，浮点数表示形式为 1 1000 0101 000 1000 0000 0000 0000 0000，十六进制形式为 C288 0000H。$y = -8.25 = -1000.01B = -1.00001$ $\mathrm{B} \times 2^5$，因此，符号位为 1，阶码为 1000 0010B，尾数小数部分为 000 0100 0000 0000 0000 0000B，浮点数表示形式为 1 1000 0010 000 0100 0000 0000 0000 0000，十六进制形式为 C104 0000H。因此，寄存器 A 和寄存器 B 中的内容分别是 C288 0000H、C104 0000H。
（2）两个浮点数相加的步骤如下。
① 对阶。$[E_x]_{\#} = 10000101, [E_y]_{\#} = 10000010, [\Delta E]_{\#} = [E_x - E_y]_{\#} = [E_x]_{\#} + [-[E_y]_{\#}]_{\#} = 10000101 + 01111110 = 00000011, E_x - E_y = +3, E_z$ 大于 $E_y$，所以对 $y$ 进行对阶。对阶后，$y = -0.00100001 \times 2^6$。即 $y$ 的浮点表示为 1 1000 0101（0）001 0000 1000 0000 0000 0000。
② 尾数相加。$x$ 的尾数为 $-1.0001000000000000000000, y$ 的尾数为 $-0.0010000100000000000000$。原码加法运算规则为“同号求和，异号求差”。因两数符号相同，故做加法，结果为 $-1.00110001000000000000000$。因此，$x + y$ 的结果为 $-1.00110001 \times 2^6$，符号位为 1，尾数为 001 1000 1000 0000 0000 0000，阶码为 $127 + 6 = 128 + 5 =$
<!-- page: 74 -->
1000 0101B，浮点数表示为 1 1000 0101 001 1000 1000 0000 0000 0000，转换为十六进制形式为 C298 8000H。因此，寄存器 C 中的内容是 C298 8000H。
（3）两个浮点数相减的步骤同加法，对阶的结果也一样，只是尾数相减。原码减法运算规则为“同号求差，异号求和”。因两数符号相同，故做减法。数值部分由被减数加上减数的补码（各位取反，末位加 1）得到，即
$$
\begin{array}{l}
1.000\ 1000\ 0000\ 0000\ 0000\ 0000 \\
+ )1.110\ 1111\ 1000\ 0000\ 0000\ 0000 \\
\hline
1\ 0.111\ 0111\ 1000\ 0000\ 0000\ 0000 \\
\end{array}
$$
最高数值位产生进位，表明所得数值位正确，且结果的符号取被减数的符号，即结果为负数。因此， $x$ 减 $y$ 的结果为 $-0.11101111 \times 2^6 = -1.1101111 \times 2^5$。也就是说，符号位为1，尾数为110 1111 0000 0000 0000 0000，阶码为 $127 + 5 = 128 + 4 = 1000\ 0100$B，浮点数表示为1 1000 0100 110 1111 0000 0000 0000 0000，转换为十六进制形式为C26F 0000H。因此，寄存器D中的内容是C26F 0000H。
14. 在 IEEE 754 浮点数运算中，当结果的尾数出现什么形式时需要进行左规？什么形式时需要进行右规？如何进行左规？如何进行右规？
## 【分析解答】
（1）对于结果为 $\pm 1 \times .xx \cdots x$ 的情况，需要进行右规。即尾数右移一位，阶码加 1。右规操作可以表示为：$M_h \leftarrow M_h \times 2^{-1}, E_h \leftarrow E_h + 1$。右规时注意两点：① 尾数右移时，最高位 1 被移到小数点前一位作为隐藏位，最后一位移出时，要考虑舍入；② 阶码加 1 时，直接在末位加 1。
（2）对于结果为 $\pm 0.00 \cdots 01x \cdots x$ 的情况，需要进行左规。即数值位逐次左移，阶码逐次减 1，直到将第一位 1 移到小数点左边。假定 $k$ 为结果中“$\pm$”和左边第一个 1 之间连续 0 的个数，则左规操作可以表示为：$M_h \leftarrow M_h \times 2^k, E_h \leftarrow E_h - k$。左规时注意两点：① 尾数左移时数值部分最左 $k$ 个 0 被移出，因此，相对来说，小数点右移了 $k$ 位。因为进行尾数相加时，默认小数点位置在第一个数值位（即隐藏位）之后，所以小数点右移 $k$ 位后被移到了第一位 1 后面，这个 1 就是隐藏位。② 执行 $E_h \leftarrow E_h - k$ 时，每次都在末位减 1，一共减 $k$ 次。
15. 在 IEEE 754 浮点数运算中，如何判断浮点运算的结果是否溢出？