0.1 0 1 1

第 3 版 · OCR 辅助 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照

#### 0.1 0 1 1
被乘数X=0.X?X?X?X?=0.1011
×0.1101
乘数Y=0.Y?Y?Y?Y?=0.1101
1011⋯⋯⋯⋯⋯X×Y?× 2-+
### 0 000⋯⋯⋯⋯⋯⋯⋯ X×Y?× 2-
1011⋯⋯⋯⋯⋯⋯⋯⋯X×Y× 2-?
1011⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯X×Y× 2-1
#### 0.1 0.0.0111.1
由此可知，x×Y=≥(x×Y,×2-)=0.1000111。
从上述手算乘法过程可以看出，两个无符号数相乘具有以下几个特点。
(1)用乘数Y的每一位依次去乘以被乘数得X×Y,i=4,3,2,1。若Y,=0,则得0;若
Y,=1,则得X。
(2)把(1)中求得的各项结果X×Y,在空间上向左错位排列，即逐次左移，可以表示为
X×Y,×2-'。
(3)对(2)中求得的结果求和，这就是两个无符号数的乘积。
计算机中两个无符号数相乘，类似于手算乘法。但为了提高效率，作了相应改进。主要


<!-- page: 80 -->

运算方法和运算部件
的改进措施有以下几方面。
(1)每将乘数Y的一位乘以被乘数得X×Y,后，就将该结果与前面所得的结果累加，
得到 P,,称之为部分积。因为没有等到全部计算后一次求和，所以减少了保存每次相乘结
果X×Y,的开销。
(2)在每次求得X×Y,后，不是将它左移与前次部分积P,相加，而是将部分积 P,右
移一位与X×Y,相加。
(3)对乘数中为1的位执行加法和右移运算；对为0的位只执行右移运算，而不需执行
加法运算。
因为每次进行加法运算时，只需要将X×Y,与部分积中的高n位进行相加，低n位不
会改变，因此，只需用n位加法器就可实现两个n位数的相乘。
上述思想可以写成如下数学推导过程：
X×Y=X×(0.Y?Y?⋯Y。)
=X×Y?×2-1+X×Y?×2-2+X×Y?×2-*+⋯+X×Y。×2-"
=(-⋯(0+X×Y,)+X×Y-)+⋯+x×Y)+x×Y)
n个2
上述推导过程具有明显的递归性质，其递推公式为
Pi=2-1(P,+X×Y-)(i=0,1,2,3,⋯,n-1)
(3-5)
设Po=0,无符号数乘法过程可以归结为循环地计算下列算式的过程。
P?=2-1(Pa+X×Y。)
P?=2-'(P?+X×Y。-)
P,=2-1(Pn-1+X×Y?)
上述推导过程中的 P,称为部分积，每一步迭代过程如下。
(1)取乘数的最低位Y。判断。
(2)若Y。-,为1,则将上一步迭代部分积P,与X相加；若Y,为0,则什么也不做。
(3)右移一位，产生本次部分积P+。
部分积 P,和X进行无符号数相加，可能会产生进位，因而需要有一个专门的进位位
C。整个迭代过程从乘数最低位Y。和P。=0开始，经过n次“判断一加法一右移”循环，直
到求出P。为止。P。就是最终的乘积。假定每次循环在一个时钟周期内完成，则n位乘法
需要用n个时钟周期来完成。图3.10是实现两个32位无符号数乘法的逻辑结构图。
图3.10中被乘数寄存器X用于存放被乘数；乘积寄存器P开始时置初始部分积P。=
0,结束时存放的是64位乘积的高32位；乘数寄存器Y开始时置乘数，结束时存放的是64
位乘积的低32位；进位触发器C保存加法器的进位信号；计数器C,存放循环次数，初值是
32,每循环一次，C,减1,当C,=0时，乘法运算结束；ALU是乘法器核心部件，在控制逻辑
的控制下，对乘积寄存器 P和被乘数寄存器X的内容进行“加”运算，在“写使能”控制下运
算结果被送回乘积寄存器 P,进位位存放在C中。
每次循环都要对进位位C、乘积寄存器P和乘数寄存器Y实现同步“右移”,此时，进位
信号C移入寄存器P的最高位，寄存器P的最低位移出到寄存器Y的最高位，寄存器Y的最
低位移出，0移入进位位C中。从最低位Y,开始，逐次把乘数的各个数位Y。移到寄存器Y
第3章
63


<!-- page: 81 -->

计算机组成与系统结构(第3版)
被乘数寄存器X
64
32
、32
32位 ALU,
加
、32
64位
右移
控制逻辑
C
乘积寄存器P
乘数寄存器Y
计数器C。
写使能
332
|时钟
图3.10 实现 32 位无符号数乘法运算的逻辑结构
的最低位上。因此，寄存器Y的最低位被送到控制逻辑以决定被乘数是否“加”到部分积上。
对于原码定点小数的乘法运算，只要根据上述无符号数的乘法运算得到乘积的数值部
分，然后再加上符号位，就可以得到最终原码表示的乘积。需要补充说明一点，当被乘数或
乘数中至少有一个为全0时，结果直接得0,不需要再进行乘法运算。
例3.2已知[x]=0.1101,[y]w=0.1011,用原码一位乘法计算[x×y]原。
解：先采用无符号数乘法计算1101×1011的乘积，原码一位乘法过程如下。
C
P
y
说明
0
0000
1011
P?=0
+Ii0I
X=1.+X
0
1101
C,P和 Y同时右移一位
0
0110
101-
+1101
1
0011
C,P和 Y同时右移一位
0
1001
11
得P?
10
+0000
Y?=0,不做加法(加0)
0
1001
1110
C,P和 Y同时右移一位
得P?
0
0100
1111
+1101
Y=1.+X
1
0001
C,P和 Y同时右移一位
0
1000
1111
得P?
符号位为0+0=0,因此，[x×y]x=0.10001111。
2.原码两位乘法
对于n位原码一位乘法来说，需要经过n次“判断—加法—右移”循环，运算速度较慢。
如果对乘数的每两位取值情况进行判断，使每步求出对应于该两位的部分积，则可将乘法速
度提高一倍。这种方法被称为原码两位乘法，只需在原码一位乘法的基础上增加少量的逻
辑线路，就可实现原码两位乘法。
考查乘数每两位的组合以及对应的求部分积的操作情况，归纳如下：
若Y-Y,=00,则P+=2-2(P,+0)
若Y-Y,=01,则P+=2-(P,+X)
若Y-Y,=10,则P=2-2(P,+2X)
若Y-;Y,=11,则P?=2-2(P,+3X)


<!-- page: 82 -->

运算方法和运算部件
对于上述“+0”和“+X”的情况，与前面原码一位乘法一样计算即可；对于“+2X”,可通过
X左移1位来实现；对于“+3X”,则以4X—X代替3X,在本次运算中只执行一X,而+4X
则延迟到下一次执行。因此，这种情况下，部分积可以由下式得到：P=22(P,+3X)=
2-2(P(-X+4X)=2-*(P;-X)+X。“-X”用+[-X]#实现。因为下一次部分积已右
移了两位，所以，上次未完成的“+4X”已变成“+X”。可用一个触发器T记录是否需要下
次执行“+X”,若是，则1→T。因此，实际操作中用Y-1、Y,和T三位来控制乘法操作。
3.3.4补码乘法运算
补码作为机器中带符号整数的表示形式，需要计算机能实现定点补码整数的乘法运算。
根据每次部分积是一位相乘得到还是两位相乘得到，有补码一位乘法和补码两位乘法。
1.补码一位乘法
A.D.Booth提出了一种补码相乘算法，可以将符号位与数值位合在一起参与运算，直接
得出用补码表示的乘积，且正数和负数同等对待。这种算法被称为布斯(Booth)乘法。
因为补码用来表示带符号整数，机器字长都是字节的倍数，所以考查偶数位的补码定点
整数的乘法运算。即假定[x]#和[y]n是两个偶数位补码定点整数，[x×y]#的布斯乘法
递推公式推导如下。
设：[x]n=X⋯X?X,[y]=Y,-⋯Y?Y。,根据补码定义，可得到真值y的计算公
式如下。
y=-Y.12*1+2v:2
=-Y2*1+Y.-22*-2+⋯+Y?21+Y?2°
=-Y2°-1+Y,-22*1-Y-2*-2+⋯+Y?22-Y?21+Y21-Y,2°
=(Y,-?-Y-)2"-1+(Y--Y,-)2-2+⋯+(Y。-Y?)21+(0-Y?)2°
-2(x-Y)2
这里假设Y-=0。因此，
Cx×y]n=[x×≥(x--Y)2]。
(3-6)
与推导无符号数乘法算法一样，可以不考虑小数点位置，只要最终的乘积约定好小数点位置
就可以了。因此，式(3-6)的右边可以通过乘以2~“来变换成以下形式：
[=×2x--Y]2*]。
(3-7)
将式(3-7)展开后，得到如下递推公式：
[P+]=[2-'(P,+(Y--Y)x)](i=0,1,2,⋯,n-1)
此公式中 P,为上次部分积，P,为本次部分积。令[P。]#=0,则有：
(3-8)
[P?]n=[2-1(P?+(Y_?-Y?)×x)]
[P?-:]#=[2-1(P-z+(Y--Y。-z)×x)]
[P.]#=[2-1(P-?+(Y--Y-)×x]
(3-9)
第3章
65


<!-- page: 83 -->

计算机组成与系统结构(第3版)
66
比较式(3-6)和式(3-9),可以得出结论：[x×y]n=2"[P.],因此，只要将最终部分积
[P.]#的小数点约定到最右边就行了。
由递推公式(3-8)可知，在求得[P,]后，根据对乘数中连续两位Y,Y,的判断，就可求
得[Pa]#。
若Y,Y,-;=01,则[P]=[2~'(P,+x)]#。
若Y,Y-?=10,则[Pi]#=[2-'(P,-x)]#。
若Y,Y,-?=00或11,则[P]=[2-1(P,+0)]。
上述式子[2~`(P,±x)]可通过执行[P,]m+[±x]m后右移一位实现。此时，采用
的是补码右移方式，即带符号整数的算术右移。
根据上述分析，归纳出补码乘法运算规则如下：
(1)乘数最低位增加一位辅助位Y-=0;
(2)根据Y,Y,-;的值，决定是“+[x]”“-[r]#”还是"+0”;
(3)每次加减后，算术右移一位，得到部分积；
(4)重复第(2)和第(3)步n次，结果得[x×y]#。
图3.11是实现32位补码一位乘法的逻辑结构图，和图3.10所示的无符号数乘法电路
的逻辑结构很类似，只是部分控制逻辑不同。
被乘数寄存器X
32
32
加/减
32位ALU
32
64位
右移
控制逻辑
乘积寄存器P!乘数寄存器Y
计数器C
写使能
332
『时钟
图3.11实现补码一位乘法的逻辑结构
例3.3 已知[x]n=1101,[y]#=0110,要求用布斯乘法计算[x×y]。
解：[-x]#=0011,布斯乘法过程如下。
P
Y
Y
说 明
0000
0110
0000
+0011
0011
0001
0|011
1001
0000
110|0
8+
1110
1110|
因此，[x×y]=1110 1110。
0
0
1
1
0
设Y,=0,[P]=(
Y?Y=00,P、Y直接右移一位
得[P]
Y,Y=10,+[-x]
P、Y同时右移一位
得[P]
Y?Y?=11,P、Y直接右移一位
得[P]
Y?Y?=01,+[x]。
P、Y同时右移一位
得[P?]


<!-- page: 84 -->

运算方法和运算部件
验证：x=-011B=-3,y=+110B=6,x×y=-001 0010B=-18,结果正确。
布斯乘法的算法过程为n次“判断一加减一右移”循环，从流程图可以看出，在布斯乘
法中，遇到连续的1或连续的0时，可跳过加法运算直接进行右移操作，因此，布斯算法的运
算效率较高。
2.补码两位乘法
补码乘法也可以采用两位乘的方法，把乘数分成两位一组，根据两位代码的组合决定加
或减被乘数的倍数，形成的部分积每次右移两位。补码两位乘的方法可以用布斯乘法过程
来推导。
假设用布斯乘法已经求得部分积[P,],则部分积[P]和[P:]可分别写为
[P]#=2-1([P]#+(Y;-1-Y)[x]#)
(3-10)
[P]#=2-1([P]#+(Y,-Y+)[x])
(3-11)
把式(3-10)代入式(3-11)中，可以得到：
[P2]=2-1(2-1([P,]*+(Y-1-Y)[x]#)+(Y?-Y-)[x])
(3-12)
=22([P,]+(Y,-?+Y,-2Y+)[x])
从式(3-12)可看出，由乘数中相邻3位YY、Y的组合作为判断依据，可以跳过
[P+]的计算步骤，即从[P,]直接求得[P+]。补码两位乘法运算过程与布斯乘法相
似，因此称为改进布斯算法(modified booth algorithm,MBA),也称为基4布斯算法。因为
字长总是8的倍数，所以补码的位数n应是偶数，因此，总循环次数为n/2。该算法可将部
分积数目压缩一半，从而提高运算速度。
*3.3.5快速乘法器
乘法是数字信号处理中重要的基本运算。在图像、语音、加密等数字信号处理领域，乘
法器扮演着重要的角色，并在很大程度上决定着系统性能。乘法器也是处理器中进行数据
处理的关键部件，大约1/3是乘法运算。因此，有必要考虑实现高速乘法运算。前面介绍的
原码两位乘法和补码两位乘法(MBA),通过一次判断两位乘数来提高乘法速度。同理，可
以采用一次判断更多位乘数的乘法，但是多位乘法运算的控制复杂度呈几何级数增长，实现
难度很大。随着大规模集成电路技术的飞速发展，出现了采用硬件叠加或流水处理的快速
乘法器件，如阵列乘法器就是其中之一。
图3.12是用手算进行两个4位无符号数相乘的示意图。在手算算式中，每个XY,(i=
1～4,j=1～4)都是由两个1位的二进制数相乘得到的。第一行为X,Y?(i=1～4);第二行
为X,Y?(i=1～4);第三行为X,Y?(i=1～4);第四行为X,Y?(i=1～4)。所以，每个X,Y,
(i=1～4,j=1～4)可以用一个“与”门实现。每行都向左错一位，最终将权相等的位的积相
加，形成最终的乘积P=P?P;P;P?P?P?P?P。。
在计算机内，用组合逻辑线路可以构成一个实现上述执行过程的乘法器。如图3.13所
示，该乘法器为阵列结构形式，故称为阵列乘法器(array multiplier)。图中实现了X×Y.其
中X=X?X?X?X?,Y=Y?Y?Y?Y?。X和Y是无符号数。一位乘积X,Y,可以用一个两输
入端的“与”门实现。每一次加法操作用一个全加器实现。2和2'的因子所蕴含的移位由
全加器的空间错位来实现。与门和全加器的功能可用一个单元组合起来，称为一个细胞模
块，在图中用一个方框来表示。
第3章
67


<!-- page: 85 -->

计算机组成与系统结构(第3版)
68
X?
X?
X?
0
0
0
0
X
X?
X?
X?
X
X?
X?
X?
X?
X?
X?
X?
X?
-- 初始部分积
-- Y?
⋯ Y?
-Y?
Y?
P?
P?
P?
P?
图3.12
P?
P?
P
P?
### 4 位无符号数的手算过程
进位输出
部分积输入
全加器
部分积输出
X
-Y
进位输入
### 0 X?
被乘数X
0
X?
0
-Y?0
oY
X?
Y?
0
X?
Y?
0
P?
P?
P?
P?
P?
P?
图3.13 4×4位基于 CRA的阵列乘法器
P?
P?
阵列乘法器基于移位与求和算法，每一行中被乘数与乘数中的某一位相乘，产生一组部
分积。即每一行由乘数的每一数位Y,(j=1,2,3,4)控制得到本级的部分积X,2?-”×Y,(i=
1,2,3,4)。而每一斜列则由被乘数的每一数位X(i=1,2,3,4)控制，即为X,×Y,24-)(j=
1,2,3,4)。如此求出全部部分积，最后对所有部分积求和得到乘积，整个电路的延迟取决于
用于求和的加法阵列结构。
图3.13中采用的是基于行波进位加法器(carry ripple adder,CRA)的阵列乘法器，采用
串行进位，每一级部分积的生成不仅依赖上一级的部分积，还依赖于上一级的最终进位，因
而运算速度慢。为加快运算速度，加法阵列可改用基于进位保留加法器(carry save adder,
CSA)方式的结构，如图3.14所示。CSA将本级进位与本级和一样同时输出至下一级，而不
是向前传递到本级的下一位，因而求和速度快，且向下级传递的速度与字长无关。
阵列乘法器结构规范，标准化程度高，有利于布局布线，适合用超大规模集成电路实现，
且能获得较高的运算速度，其乘法速度仅取决于逻辑门和加法器的传输延迟。随着集成电
路价格的不断下降，阵列乘法器在某些数字系统中也被大量使用，例如在数字信号处理系统
中受到重视。
阵列乘法器至少要做O(N)次加法，速度较慢。为了进一步提高速度，部分积求和电路


<!-- page: 86 -->

运算方法和运算部件
Xg
X?
X?
X?L
X?
Xq
Y?
全加器
Xs
Xq
X?L
X?L
X
Xq
Y
X? X
x;
x?
x?
x?
半加器
-Y?
X? X? x
x?
x
x?
Y
X?X?
X? x
X?
X?
Y
X? X?
x?
X?
x?
X?
-Y?
加法器
P? P? P?
P?
P?
P?
P? P?
P?
P?
P?
P?
图3.14 6×6位基于CSA的阵列乘法器
可采用树形结构。树形结构可以减少求和级数，是提高乘法运算速度的一种方法。1961年
C.S.Wallac提出的华莱士树(Wallace tree,WT)结构是其中最著名的一种，它对16位以上
的乘法运算尤其适用。WT结构将全部部分积按列分组，每列对应一组加法器，各列同时相
加，前一列进位传至后一列，生成新的部分积阵列；按同样的方法化简新的阵列，直至只剩两
行部分积，最后用高速加法器求和得到最终乘积。WT结构只需做O(logN)次加法，因而
运算速度快。可将 MBA和 WT结合起来进一步加快乘法速度，MBA用来减少部分积个
数，而WT用来缩短部分积求和时间。
3.3.6原码除法运算
在进行定点数除法运算前，首先要对被除数和除数的取值和大小进行相应的判断，以确
定除数是否为0、商是否为0、是否溢出或为不确定的值NaN。通常的判断操作如下。
(1)若被除数为0、除数不为0,或者定点整数除法时|被除数|<|除数|,则说明商为0,
余数为被除数，不再继续执行。
(2)若被除数不为0、除数为0,对于整数，则发生“除数为0”异常；对于浮点数，则结果
为无穷大。
(3)若被除数和除数都为0,对于整数，则发生除法错异常；对于浮点数，则有些机器产
生一个不发信号的NaN,即 quiet NaN。
只有当被除数和除数都不为0,并且商也不可能溢出(如补码中最大负数除以一1)时，
才进一步进行除法运算。
原码作为浮点数尾数的表示形式，需要计算机能实现定点原码小数的除法运算。因此，
本节接下来介绍原码除法运算。除法运算与乘法运算很相似，都是一种移位和加减运算的
第3章
69


<!-- page: 87 -->

计算机组成与系统结构(第 3版)
70
迭代过程，但比乘法运算更加复杂。下面以两个定点正数为例，说明手算除法步骤。
假定被除数X=10011101,除数Y=1011,以下是这两个数相除的手算过程：
### 1110 商
除数1011 10011101
被除数
1011
10001
1011
01100
中间余数
1011
0011
0000
0011
余数
从上述过程和结果来看，手算除法的基本要点如下。
(1)被除数与除数相减，若够减，则上商为1;若不够减，则上商为0。
(2)每次得到的差为中间余数，将除数右移后与上次的中间余数比较。用中间余数减
除数，若够减，则上商为1;若不够减，则上商为0。
(3)重复执行第(2)步，直到求得的商的位数足够为止。
计算机内部的除法运算与手算算法一样，通过被除数(中间余数)减除数来得到每一
位商。
原码除法运算与原码乘法运算一样，要将符号位和数值位分开来处理。商的符号为相
除两数符号的“异或”值，商的数值为两数绝对值之商。因此，以下考虑定点正整数和定点正
小数的除法运算。如图3.15所示是一个32 位除法逻辑结构示意图。
除数寄存器Y
32
32
32位 ALU
加/减
、32
64位
左移
控制逻辑
余数寄存器R|余数/商寄存器Q
计数器C。
写使能
32
|时钟
图3.15 32 位除法运算逻辑结构
图3.15中除数寄存器Y存放除数；余数寄存器R开始时置被除数的高32位，作为初
始中间余数R。的高位部分，结束时存放的是余数；余数/商寄存器Q开始时置被除数的低
32位，作为初始中间余数R。的低位部分，结束时存放的是32 位商，在运算过程中，Q中存
放的并不是商的全部位数，而是部分为被除数或中间余数，部分为商，只有到最后一步才是
商的全部位数；计数器C。存放循环次数，初值是32,每循环一次，C。减1,当C,=0时，除
法运算结束；ALU 是除法器核心部件，在控制逻辑控制下，对于余数寄存器R 和除数寄存
器Y的内容进行“加/减”运算，在“写使能”控制下运算结果被送回寄存器R。
每次循环都要对寄存器R和Q实现同步“左移”,左移时，Q的最高位移入R的最低


<!-- page: 88 -->

运算方法和运算部件
位，Q中空出的最低位上被上“商”。从低位开始，逐次把商的各个数位左移到Q中。每次
由控制逻辑根据ALU 运算结果的符号位来决定上商为0还是1。
由图3.15可知，两个32位数相除，必须把被除数扩展成一个64位数。推而广之，n位
定点数的除法，实际上是用一个2n位的数去除以一个n位的数，得到一个n位的商。因此
需要进行被除数的扩展。
定点正整数和定点正小数的除法运算，都可以用图3.15所示的除法逻辑来实现。只是
被除数扩展的方法不太一样，此外，导致溢出的情况也有所不同。
(1)对于两个n位定点正整数相除的情况，即当两个n位无符号数相除时，只要将被除
数X的高位添n个0即可。即X=X。X。-⋯X。变成X=0⋯0X,-;X。-⋯X。。显然，
对被除数预置时，R寄存器中为全0,Q寄存器中为被除数X。这种方式通常称为单精度除
法，其商的位数一定不会超过n位，因此不会发生溢出。
(2)对于两个n位定点正小数相除的情况，即当两个作为浮点数尾数的n位原码小数
相除时，只要在被除数X的低位添加n个0即可。即将X=0.X,X,-⋯X。变成X=0.
XX?-z⋯X?0⋯0,显然，扩展为2n位后，R寄存器中为被除数X,Q寄存器中为全0。
(3)对于一个2n位的数与一个n位的数相除的情况，则无须对被除数X进行扩展，这
种情况下，商的位数可能多于n位，因此，有可能发生溢出。采用这种方式的机器，其除法
指令给出的被除数在两个寄存器或一个双倍字长寄存器中，这种方式通常称为双精度除法。
综合上述几种情况，可把定点正整数和定点正小数归结在统一的假设下，并将其统称为
无符号数的除法。因而，可以假定：除法运算时，被除数X为2n位，除数Y和商Q都为n
位。本书后续对无符号数除法和原码定点小数除法的算法描述也都基于这个假设。
参考手工除法过程，得到计算机中两个无符号数除法的运算步骤和算法要点如下。
(1)操作数预置。在确认被除数和除数都不为0后，将被除数(必要时进行0扩展)置
于余数寄存器R和余数/商寄存器Q中，除数置于除数寄存器Y中。
(2)做减法试商。根据R-Y的符号来判断两数大小。若为正，则上商1;若为负，则上
商0。
(3)上商为0时恢复余数。把减掉的除数再加回来，恢复原来的中间余数。
(4)中间余数左移，以便继续试商。手算除法中，每次试商前，除数右移后，与中间余数
进行比较。在计算机内部进行除法运算时，除数在除数寄存器中不动，因此，需要将中间余
数左移，将左移结果与除数相减以进行比较。左移时中间余数和商一起左移，Q的最低位
空出，以备上商。
上述算法要点(3)中，采用了“上商为0时恢复余数”的方式，所以，把上述这种方法称为
“恢复余数法”。也可以不这样做，而是在下一步运算时把当前多减的除数补回来。这种方
法称为“不恢复余数法”,又称“加减交替法”。根据余数恢复方式的不同，有“恢复余数除法”
和“不恢复余数除法”两种。
1.恢复余数除法
假定被除数X为2n位，除数Y和商Q都为n位，X、Y和Q分别表示为：X=X-
X?-z⋯X,X-⋯X。,Y=Y?-Yn-2⋯Y。,Q=Qn-1Q?-⋯Q,则恢复余数除法的算法步骤
如下。
第1步，R?=X-Y,若R?<0,则上商Qn=0,同时恢复余数，即R?=R?+Y;若R?≥
第3章
71


<!-- page: 89 -->

计算机组成与系统结构(第3版)
72
0,则上商Q=1。这里求得的商Q,是商的第n位数值。显然，若Q,=1,则商将会有n+1
位数。这对于以下不同的情况，意味着不同的结果。
(1)对于无符号整数除法来说，如果被除数为2n位，则商有可能会超出n位无符号整
数范围，所以，若Q=1,则发生溢出。
(2)对于原码定点小数除法来说，若Q。=1,则相除结果的数值从小数部分溢出到了整
数部分，按道理两个定点小数相除，结果也应是定点小数，故应当作溢出处理。但浮点数尾
数溢出时，可通过右规来消除，最终只要阶码不溢出，结果仍然正确。所以，这种情况下，保
留最高位的商Q。=1,继续执行下去。
第2步，若已求得第i次的中间余数为R,则第i+1次的中间余数为R=2R,-Y。若
R+<0,则上商Q-=0,同时恢复余数，即R=R,+Y;若R≥0,则上商Q-,=1。
第3步，循环执行第2步n次，直到求出所有n位商Q。～Q。为止。
最终商在Q寄存器中、余数在R寄存器中。
例3.4 已知[x]m=0.1011,[y]w=1.1101,用恢复余数法计算[x/y]。
解：分符号位和数值位两部分进行。
商的符号位：0+1=1。
商的数值位采用恢复余数法。减法操作用补码加法实现，是否够减通过中间余数的符
号来判断，所以中间余数要加一位符号位。因此，需先计算出[lx|]w=0.1011,[ly|]+=
0.1101,[-|y|]*=1.0011。
因为是原码定点小数，所以在低位扩展0。虽然实际参加运算的是[lx|]n和[ly|]n,
但为简单起见，以下说明中分别标识为X和Y。
运算过程如下：
余数寄存器 R
余数/商寄存器 Q
说 明
01011
0000□
开始 R?=X
R?=X-Y
0000|0
R?<0,则Q?=0
-810+
恢复余数：R?=R?+Y
得R
10110
+10011
010.01
0.0.00□
000|0 1
2R?(R和Q同时左移，空出一位商)
R?=2R?-Y
R?>0,则Q?=1
10010
+10011
00101