题目
43. 有实现 x*y 的两个 C 语言函数如下:unsigned umul ( unsigned x , unsigned y)( return x*y; )int imul ( int x, int y )( return x * y; )假定某计算机 M 中 ALU 只能进行加减运算和逻辑运算。请回答:(1)若 M 的指令系统中没有乘法指令,但有加法、减法和位移等指令,则在 M 上也能实现上述两个函数中的乘法运算,为什么?(2)若 M 的指令系统中有乘法指令,则基于 ALU、位移器、寄存器以及相应控制逻辑实现乘法指令时,控制逻辑的作用是什么?(3)针对以下 3 种情况:(a)没有乘法指令;(b)有使用 ALU 和位移器实现的乘法指令;(c)有使用阵列乘法器实现的乘法指令,函数 umul()在哪种情况下执行时间最长?哪种情况下执行的时间最短?说明理由(4)n 位整数乘法指令可保存 2n 位乘积,当仅取低 n 位作为乘积时,其结果可能会发生溢出。当 n=32, x=231-1,y=2 时,带符号整数乘法指令和无符号整数乘法指令得到的 x*y 的 2n 位乘积分别是什么(用十六进制表示)?此时函数 umul()和 imul()的返回结果是否溢出?对于无符号整数乘法运算,当仅取乘积的低 n 位作为乘法结果时,如何用 2n 位乘积进行溢出判断?【
43. 有实现 x*y 的两个 C 语言函数如下:unsigned umul ( unsigned x , unsigned y){ return x*y; }int imul ( int x, int y ){ return x * y; }假定某计算机 M 中 ALU 只能进行加减运算和逻辑运算。请回答:(1)若 M 的指令系统中没有乘法指令,但有加法、减法和位移等指令,则在 M 上也能实现上述两个函数中的乘法运算,为什么?(2)若 M 的指令系统中有乘法指令,则基于 ALU、位移器、寄存器以及相应控制逻辑实现乘法指令时,控制逻辑的作用是什么?(3)针对以下 3 种情况:(a)没有乘法指令;(b)有使用 ALU 和位移器实现的乘法指令;(c)有使用阵列乘法器实现的乘法指令,函数 umul()在哪种情况下执行时间最长?哪种情况下执行的时间最短?说明理由(4)n 位整数乘法指令可保存 2n 位乘积,当仅取低 n 位作为乘积时,其结果可能会发生溢出。当 n=32, x=231-1,y=2 时,带符号整数乘法指令和无符号整数乘法指令得到的 x*y 的 2n 位乘积分别是什么(用十六进制表示)?此时函数 umul()和 imul()的返回结果是否溢出?对于无符号整数乘法运算,当仅取乘积的低 n 位作为乘法结果时,如何用 2n 位乘积进行溢出判断?【
题目解答
答案
解析】(1) 乘法运算也可以通过加法操作和移位操作实现x * y 可视为 y 个 x 或 x 个 y 相加的结果(2) 实现相加和移位的控制(3) 最长:a 最短:ca) 情况下执行时间最长,需要利用其他指令来实现乘法功能b) 情况下使用了 ALU 与位移器,由多次相加及位移操作串行实现乘法操作c) 情况使用阵列乘法器做并行乘法运算,时间显然最快(4) 带符号整数指令乘法: 7FFF FFFFH * 2 = 0000 0000 FFFF FFFEH无符号整数指令乘法: 7FFF FFFFH * 2 = 0000 0000 FFFF FFFEHumul()返回 FFFF FFFEH 未溢出imul()返回 FFFF FFFEH 有溢出(结果成了负数)高 n 位全 0 则未产生溢出,否则产生溢出
解析
- 乘法的本质:乘法运算可以通过加法和移位操作实现。例如,二进制乘法中,每一位的权值对应移位次数,通过累加移位后的部分积即可得到结果。
- 硬件与软件实现差异:无乘法指令时需软件模拟(加法+移位),有乘法指令时硬件加速。阵列乘法器通过并行计算大幅缩短时间。
- 溢出判断:无符号乘法的溢出可通过检查乘积的高n位是否全0判断,若非全0则溢出。
(1)无乘法指令时实现乘法的原理
关键思路:利用加法和移位模拟乘法。
- 二进制展开:将乘数分解为二进制位,每一位对应被乘数的移位结果。
- 累加部分积:通过循环移位和加法,逐位累加部分积得到最终结果。
(2)乘法指令的控制逻辑作用
核心功能:
- 协调硬件单元:控制ALU、位移器、寄存器的工作时序。
- 管理运算步骤:确定移位次数、部分积的累加顺序,处理进位。
(3)三种情况的执行时间比较
- 情况(a):纯软件实现,需多次加法和移位,时间最长。
- 情况(b):硬件辅助但串行运算,时间次之。
- 情况(c):阵列乘法器并行计算,时间最短。
(4)溢出分析与判断
- 带符号乘法:结果超出
int
范围(-2³¹
到2³¹-1
)时溢出。 - 无符号乘法:结果超出
unsigned int
范围(0
到2³²-1
)时溢出。 - 溢出判断:若2n位乘积的高n位非全0,则无符号乘法溢出。