原创 定点运算

第三节　定点数运算

　　定点数运算包括移位、加、减、乘、除几种。

一、移位运算

　　1．移位的意义

　 　移位运算在日常生活中常见。例如15米可写作1500厘米，单就数字而言，1500相当于小数点左移了两位，并在小数点前面添了两个0；同样15也相当 于1500相对于小数点右移了两位，并删去了小数点后面的两个0。可见，当某个十进制数相对于小数点左移n位时，相当于该数乘以10ⁿ；右移n位时，相当于该数除以10ⁿ。
　　计算机中小数点的位置是事先约定的，因此，二进制表示的机器数在相对于小数点作n位左移或右移时，其实质就便该数乘以或除以2ⁿ(n=1,2...n)。
　　移位运算又叫移位操作，对计算机来说，有很大的实用价值，例如，当计算机没有乘（除）运算线路时，可以采用移位和加法相结合，实现乘（除）运算。
　　计算机中机器数的字长往往是固定的，当机器数左移n位或右移n位时，必然会使其n位低位或n位高位出现空位。那么，对空出的空位应该添补0还是1呢？这与机器数采用有符号数还是无符号数有关，对有符号的移位叫算术移位。

　　2．算术移位规则

　　对于正数，由于[x]_原=[x]_补=[x]_反= 真值，故移位后出现的空位均以0添之。对于负数，由于原码、补码和反码的表示形式不同，故当机器数移位时，对其空位的添补规则也不同。下表列出了三种不同 码制的机器数（整数或小数均可），分别对应正数或负数，移位后的添补规则。必须注意的是：不论是正数还是负数，移位后其符号位均不变，这是算术移位的重要 特点。

　　不同码制机器数移位后的空位添补规则

码   制 添补代码 正数 原码、补码、反码 0   原码 0 负数 补码 左移添0 右移添1 反   码 1

　　由上表可得出如下结论：

　　（1）机器数为正时，不论左移或右移，添补代码均为0。

　　（2）由于负数的原码其数值部分与真值相同，故在移位时只要使符号位不变，其空位均添0。

　　（3）由于负数的反码其各位除符号位外与负数的原码正好相反，故移位后所添的代码应与原码相反，即全部添1。

　　（4）分析任意负数的补码可发现，当对其由低位向高位找到第一个“1”时，在此“1”左边的各位均与对应的反码相同，而在此“1”右边的各位（包括此“1”在内）均与对应的原码相同，即添0；右移时困空位出现在高位，则添补的代码应与反码相同，即添1。

　　例：设机器数字长为8位（含一位符号位），若A=±26，写出三种机器数左、右移一位和两位后的表示形式及对应的真值，并分析结果的正确性。

　　解：（1）A=+26=(+11010)₂

　　则[A]_原=[A]_补 =[A]_反=0,0011010

　　移位结果表示如下：

移位操作 机  器   数 对应的真值 [A]原=[A]补=[A]反 移位前 0,0011010 +26 左移一位 0,0110100 +52 左移两位 0,1101000 +104 右移一位 0,0001101 +13 右移两位 0,0000110 +6

　　可见，对于正数，三种机器数移位后符号位不变，左移时最高数位丢1，结果出错；右移时最低数位丢1，影响精度。

　　（2）A=-26=(-11010)2

　　三种机器数移位结果示于下表。

移位操作 机  器   数 对应的真值 移位前 原 码 1,0011010 -26 左移一位 1,0110100 -52 左移两位 1,1101000 -104 右移一位 1,0001101 -13 右移两位 1,0000110 -6 移位前 补 码 1,1100110 -26 左移一位 1,1001100 -52 左移两位 1,0011000 -104 右移一位 1,1110011 -13 右移两位 1,1111001 -7 移位前 反 码 1,1100101 -26 左移一位 1,1001011 -52 左移两位 1,0010111 -104 右移一位 1,1110010 -13 右移两位 1,1111001 -6

　　可见，对于负数，三种机器数移位后符号位均不变。负数的原码左移时，高位丢1，结果出错；低位丢1，影响精度。负数的补码左移时，高位丢0，结果出错；低位丢1，影响精度。负数的反码左移时，高位丢0，结果出错；低位丢0，影响精度。
　　下图示意了机器中实现算术左移和右移操作的硬件框图。其中（a）真值为正的三种机器数的移位操作；（b）负数原码的移位操作；（c）负数补码的移位操作；（d）负数反码的移位操作。

　　3．算术移位和逻辑移位的区别

　 　有符号数的移位称为算术移位，无符号数的移位称为逻辑移位。逻辑移位的规则是：逻辑左移时，高位移出，低位添0；逻辑右移时，低位移出，高位添0。例 如，寄存器内容为01010011，逻辑左移为1010010，算术左移为00100110（最高数位“1”移丢）。又如寄存器内容为10110010， 逻辑右移为01011001。若将其视为补码，算术右移为11011001。显然，两种移位的结果是不同的。上例中为了避免算术左移时最高数位丢1，可采 用带进位(C_y)的移位，其示意图如下图所示。算术左移时，符号位移至C_y，最高数位就可避免移出。

二、加法与减法运算

　　加减法运算是计算机中最基本的运算，因减法运算可看作被减数加上一个减数的负值，即A-B=A+(-B)，故在此将机器中的减法运算和加法运算合在一起讨论。现代计算机中都采用补码作加减法运算。

　　1．补码加减运算的基本公式

　　补码加法的基本公式为：

　　整数    [A]_补+[B]_补=[A+B]_补  (mod 2ⁿ⁺¹)

　　小数    [A]_补+[B]_补=[A+B]_补  (mod 2)

　　即补码表示肋两个数在进行加法运算时，可以把符号位与数位同等处理，只要结果不超出机器能表示的数值范围，运算后的结果按2ⁿ⁺¹取模(对于整数)；或按2取模(对于小数)，就能得到本次加法的运算结果。

　　对于减法因A-B=A+(-B)

　　则[A-B]_补=[A+(-B)]_补

　　由补妈加法基本公式可得：

　　整数    [A-B]_补=[A]_补+[-B]_补  (mod 2ⁿ⁺¹)

　　小数    [A-B]_补=[A]_补+[-B]_补  (mod 2)

　　因此，若机器数采用补码， 当求A-B时， 只需先求[-B]_补（称[-B]_补为“求补”后的减数），就可按补码加法规则进行运算。而[-B]_补由[B]_补连同符号位在内，每位取反，末位加1而得。

　　例：x=0.1010，y=-0.0011，用补码的加法求x+y

　　解：[x]_补=0.1010，[y]_补=1.1101

　　[x]_补+[y]_补=0.1010+1.1101=0.0111（按模2的意义，最左边的1丢掉）

　　　　　　x+y=0.0111　

　　例：x=0.1001，y=-0.0011，用补码的减法求x-y

　　解：[x]_补=0.1001，[y]_补=1.1101,[-y]_补=0.0011

　　[x]_补-[y]_补=[x]_补+[-y]_补=0.1001+0.0011=0.1100

　　　　　　x-y=0.1100

　　例：设机器数字长为8位，其中一位为符号位，令A=-93，B=+45，求[A-B]_补。

　　解：由A=-93=-1011101，得[A]_补=1,0100011

　　    由B=+45=+0101101，得[B]_补=0,0101101，[-B]_补=1,1010011

　　    [A-B]_补=[A]_补+[-B]_补=1,0100011+1,1010011=10,1110110

　　按模2ⁿ⁺¹的意义，最左边的“1”自然丢掉，故[A-B]_补=0,1110110，还原成真值得A-B=118，结果出错，这是因为A-B=-138超出了机器字长所能表示的范围。在计算机中，这种超出机器字长的现象，叫溢出。为此，在补码定点加减运算过程中，必须对结果是否溢出作出明确的判断。

　　解：由A=-93=-1011101，得[A]_补=1,0100011

　　2．溢出判断

　　补码定点加减运算判断溢出有三种方法。

　 　(1)用一位符号位判断溢出。对于加法，只有在正数加正数和负数加负数两种情况下才可能出现溢出，符号不同的两个数相加是不会出现溢出的。对于减法，只 有在正数减负数或负数减正数两种情况下才可能出现溢出，符号相同的两个数相减是不会出现溢出的。因此在判断溢出时可以根据参加运算的两个数据和结果的符号 位进行；两个符号位相同的补码相加，如果和的符号位与加数的符号相反，则表明运算结果溢出；两个符号位相反的补码相减，如果差的符号位与被减数的符号位相 反，则表明运算结果溢出。这种方法需要判断操作是加法还是减法，以及运算结果与操作数的符号关系。
　　符号不同的两个数相加不会产生溢出的原因是字长为n+1位时，数值部分为n位，数值部分的最大绝对值为2ⁿ。如果参加运算的两个数x和y的绝对值都小于2ⁿ，则(+x)+(-y)和(-x)+(+y)的绝对值都不会大于2ⁿ，因此只需考虑(+x)+(+y)和(-x)+(-y)的情况，这时结果z的符号应与x和y的符号相同，即当x₀=1且y₀=1时，z₀=0说明数据溢出；或者当x₀=0且y₀=0时，z₀=1说明数据溢出。这样可列出下表所示的判断逻辑的真值表。

x0    y0    z0 V 0     0     0 0 0     0     1 1 0     1     0 0 0     1     1 0 1     0     0 0 1     0     1 0 1     1     0 1 1     1     1 0

　　根据真值表，可得判断溢出的逻辑表达式：

 

　　这种溢出判断方法不仅需要判断加法运算的结果，而且需要保持原操作数。

　　（2）利用数据编码的最高位（符号位）和次高位（数值部分的最高位）的进位状况来判断运算结果是否发生了溢出。

　　

　　两个补码数实现加减运算时，若最高数值位向符号位的进位值与符号位产生的进位输出值不相同，则表明加减运算产生了溢出。因为当x和y均为n+1位正整数时，其和有两种情况：当x+y<2ⁿ时，不会发生溢出；当x+y≥2ⁿ时符号位没有进位，表明发生溢出。当x和y都是n+1位负数时，其和也有两种情况：当x+y≥-2ⁿ时，不会发生溢出；当x+y<-2ⁿ时，符号位相加后变成0并且有进位，而数值部分的最高位相加时无进位，结果变为正数，表明发生了溢出。减法的情况与此类似，这种判断方法的逻辑表达式如下：

　　例：设x=+1011， y=+1001，求[x+y]_补。

　　解：[x]_补=01011， [y]_补=01001

　　       [x+y]_补=01011+01001=10100

　　两个正数相加，最高两位的进位为01，表示发生了溢出，其结果为负数，显然是错误的。

　　例：设x=-1101，y=-1011，求[x+y]_补。

　　解：[x]_补=10011， [y]_补=10101

　　　　[x+y]_补=10011+10101=01000

　　两个负数相加，最高两位的进位为10，表示发生了溢出，其结果为正数，显然是错误的。

　 　（3）采用双符号位补码进行判断。正常时两个符号位的值相同，在运算结果中当两个符号位不同时则表明发生了溢出。运算结果的符号位为01表明两个正数相 加，结果大于机器所能表示的最大正数，称为上溢；运算结果的符号位为10表明两个负数相加，结果小于机器所能表示的最小负数，称为下溢。也就是说，两个正 数相加，数值位不应向符号位同时产生进位，使得结果数的符号位和操作数的一样，为00：
　　　　00+00+00（进位）=00   （mod 4）

　　两个负数相加，数值位应向符号位产生进位，使得两个负数的双符号位的运算为11；
　　　11+11+01（进位）=11   （mod 4）

　　当运算结果的两个符号位不相同时，表明出现了溢出。判断溢出的逻辑表达式：

 

　　其中Z′为增加的符号位。

　　例：设x=+1100，y=+1000，求6位双符号位补码之和[x+y]_补。

　　解：[x]_补=001100, [y]_补=001000

　　　　[x+y]_补=001100+001000=010100

　　　　[x+y]_补=010100，其中两个符号位出现01，表示已溢出。

　　例：设x=-1100,y=-1000，求6位双符号位补码之和[x+y]_补。

　　解：[x]_补=110100， [y]_补=111000

　　　　[x+y]_补=110100+111000=101100

　　　　[x+y]_补=101100，其中两个符号位出现10，表示已溢出。

　 　从上述例子中还看出，不论溢出与否，最高位始终指示正确的符号。采用双符号位补码后，任何小于1的正数，两个符号位都是0；任何大于-1的负数，两个符 号位都是1。如果两个数相加后，其结果的符号位出现01或10时，表示发生溢出。因为两个绝对值小于1的数相加，其结果不会大于或等于2，所以最高位总是 表示正确的符号。这也可以表示为：当最高数据位有进位而符号位无进位时产生上溢出；当最高数据位无进位而符号位有进位时，表示下溢出。
　　在双符号位补码中，正常的数据中两个符号位总是相同的，所以在存储数据时不必重复存储，只是在将数据送往运算部件进行运算时才把符号位进行复制形成双符号位补码。

　　3．基本的二进制加法/减法器

　　设加法器的输入端为x_i和y_i，进位输入端为c_i，结果输出端为z_i，进位输出端为c_i+1，则一位加法器的真值表如下表所示。

输入 输出 x0    y0    ci ci+1   zi 0     0     0 0     0 0     0     1 0     1 1     0     0 0     1 1     0     1 1     0 0     1     0 0     1 0     1     1 1     0 1     1     0 1     0 1     1     1 1     1

　　第i位加减法电路的输入输出关系可表示为

 

　　同一套加法器电路，可以完成[x+y]_补和[x-y]_补的运算，实现过程中的差别仅表现在加法时y用其原值，而减法时对y求一次补。求补的操作就是在按位求反的基础上最低位再加上1，结果得到[-y]_补。求补操作可以通过在输入端增加一个反相输入实现，加1操作可通过在最低位上设置进位输入信号为1来实现。这样改进的加法器电路ALU如下图所示。

　　在上图所示的具有加减法功能的电路中增加了一个信号M，用于控制加减法运算。
　　当M=0时得到上述相同的全加器公式：

 

　　当M=1时得到求差公式：

 

 

三、乘法运算

　　在计算机中，乘法运算是一种很重要的运算，有的机器由硬件乘法器直接完成乘法运算，有的机器内没有乘法器，但可以按机器作乘法运算的方法，用软件编程实现、因此，学习乘法运算方法不仅有助于乘法器的设计，也有助于乘法编程。
　　下面从分析笔算乘法入手，介绍机器中用到的几种乘法运算方法。

　　(1)分析笔算乘法：

　　设A=0.1101，B=0.1011，求A×B。

　　笔算乘法时乘积的符号由两数符号心算而得：正正得正；其数值部分的运算如下：

　　所以  A×B=+0.10001111

　　可见，这里包含着被乘数4的多次左移，以及四个位积的相加运算。
　　若计算机完全模仿笔算乘法步骤，将会有两大困难：其一，将四个位积一次相加，机器难以实现；其二，乘积位数增长了一倍，这将造成器材的浪费和运算时间的增加。为此，对笔算乘法做些改进。

　　(2)笔算乘法的改进：

　　将A?B= A?0.1011
　　　　 =0.1A+0.001?A+0.0001?A
　　　　 =0.1A+0.00?A+0.001(A+0.1A）
　　　　 =0.1A+0.01[0?A+0.1(A+0.1A)]
　　　　 =0.1{A+0.1[0?A+0.1(A+0.1A)]}
　　　　 =2^-1{A+2^-1 [0?A+2^-1 (A+2^-1A)]}
　　　　 =2^-1{A+2^-1 [0?A+2^-1 (A+2^-1(A+0))]}

　　由上式可见，两数相乘的过程，可视作加法和移位(乘2^-1相当于做一位右移)两种运算，这对计算机来说是非常容易实现的。

　　从初始值为0开始，对上式作分步运算，则
　　第一步：被乘数加零　　　　　　A+0=0.1101+0.0000=0.1101
　　第二步：右移一位，得新的部分积　　　2^-1 (A+0)＝0.01101
　　第三步：被乘数加部分积　A+2^-1(A+0)=0.1101+0.01101=1.00111
　　第四步：右移一位，得新的部分积　2^-1 A+2^-1 (A+0)=0.100111
　　第五步：　　　　　　　　0?A +2^-1 [A+2^-1 (A+0)] =0.100111
　　第六步：　　　　　　2^-1{0?A+2^-1 [A+2^-1 (A+0)]}=0.0100111
　　第七步：　　　　　　A+2^-1{0?A+2^-1 [A+2^-1 (A+0)]}=1.0001111
　　第八步：　　2^-1 {A+2^-1[0?A+2^-1 (A+2^-1 (A+0))]}=0.10001111

　　上述运算过程可归纳为：
　　①乘法运算可用移位和加法来实现，当两个四位数相乘，总共需做四次加法和四次移位。
　　②由乘数的末位值确定被乘数是否与原部分积相加，然后右移一位，形成新的部分积；同时，乘数也右移一位，由次低位作新的末位，空出最高位放部分积的最低位。
　　③每次做加法时，被乘数仅仅与原部分积的高位相加，其低位被移至乘数所空出的高位位置。
　　计算机很容易实现这种运算规则。用一个寄存器存放被乘数，一个寄存器存放乘积的高位，又用一个寄存器存放乘数及乘积的低位，再配上加法器及其他相应电路，就可组成乘法器。又因加法只在部分积的高位进行，故不但节省了器材，而且还缩短了运算时间。

　　1．原码一位乘法

　　由于原码表示与真值极为相似，只差一个符号，而乘积的符号又可通过两数符号的逻辑异或求得，因此，上述讨论的结果可以直接用于原码一位乘，只需加上符号位处理即可。

　　上图是一个32位乘法器的结构框图，其中32位被乘数放在R2中，运算开始时32位乘数放在R1中，运算结束时64位乘积的高位放在R0中，低位放在R1中，R0和R1串联移位。完成这个定点原码一位乘法的运算规则可以用如下图所示的逻辑流程图表示。

　　在该乘法过程中，每次操作是根据乘数的一位进行操作，对于32位数的乘法，需要循环32次完成一个乘法操作，因此称为一位乘法。

　　例：用原码的乘法方法进行2×3的四位乘法。

　　解：在乘法开始之前，R0和R1中的初始值为0000和0011，R2中的值为0010。

　　在乘法的第一个循环中，判断R1的最低位为1，所以进入步骤1a，将R0的值加上R2的值，结果0010送人R0，然后进入第二步，将R0和R1右移一位，R0、Rl的结果为0001 0001，见下表的循环1，表中黑体字的数据位是乘法过程中判断的R1最低位。
　　第二个循环过程中，判断R1的最低位为l，仍进入步骤la，加0010，结果为0011，然后在第二步中将R0和R1右移一位，结果为0001 1000，见下表的循环2。
　　第三次循环中，因R1的最低位为0，进入步骤lb，R0不变，第二步移位后结果为00001100，见下表的循环3。
　　第四次循环时仍因R1最低位为0，只作移位，结果为00000110，这就是乘法的结果6，见下表的循环4。

循环 步骤 乘积（R0，R1） 0 初始值 0000 0011 1 1a：加0010 0010 0011 2：右移1位 0001 0001 2 1a：加0010 0011 0001 2：右移1位 0001 1000 3 1b：加0 0001 1000 2：右移1位 0000 1100 4 1b：加0 0000 1100 2：右移1位 0000 0110

　　2．原码两位乘法

　　原码两位乘与原码一位乘一样，符号位的运算和数值部分是分开进行的，但原码两位乘是用两位乘数的状态来决定新的部分积如何形成，因此可提高运算速度。

　　两位乘数共有4种状态，对应这4种状态可得下表。

乘数yn-1yn 新的部分积 00 等于原部分积右移两位 01 等于原部分积加被乘数后右移两位 10 等于原部分积加2倍被乘数后右移两位 11 等于原部分积加3倍被乘数后右移两位

　 　表中2倍被乘数可通过将被乘数左移一位实现，而3倍被乘数的获得可以分两步来完成，利用3=4-1，第一步先完成减1倍被乘数的操作，第二步完成加4倍 被乘数的操作。而加4倍被乘数的操作实际上是由比“11”高的两位乘数代替完成的，可以看作是在高两位乘数上加“1”。这个“1”可暂时存在C_j触发器中。机器完成置“1” C_j即意味着对高两位乘数加1，也即要求高两位乘数代替本两位乘数“11”来完成加4倍被乘数的操作。由此可得原码两位乘的运算规则如下表所示。

乘数判断位yn-1y n 标志位Cj 操 作 内 容 00 0 z→2,y*→2,Cj保持“0” 01 0 z+x*→2, y*→2,Cj保持“0” 10 0 z+2x*→2, y*→2,Cj保持“0” 11 0 z-x*→2, y*→2,置“1”Cj 00 1 z+x*→2, y*→2,置“0”Cj 01 1 z+2x*→2, y*→2,置“0”Cj 10 1 z-x*→2, y*→2, Cj保持“1” 11 1 z→2,y*→2,Cj保持“1”

　　表中z表示原有部分积，x*表示被乘数的绝对值，y*表示乘数的绝对值，→2表示右移两位，当作-x*运算时，一般采用加[-x*]_补来实现。这样，参与原码两位乘运算的操作数是绝对值的补码，因此运算中右移两位的操作也必须按补码右移规则完成。尤其应注意的是，乘法过程中可能要加2倍被乘数，即+[2x*]_补，使部分积的绝对值大于2。为此，只有对部分积取三位符号位，且以最高符号位作为真正的符号位，才能保证运算过程正确无误。
　　此外，为了统一用两位乘数和一位C_j共同配合管理全部操作，与原码一位乘不同的是，需在乘数（当乘数位数为偶数时）的最高位前增加两个0。这样，当乘数最高两个有效位出现“11”时， C_j需置“1”，再与所添补的两个0结合呈001状态，以完成加x*的操作（此步不必移位）。

例：设x=0.111111，y=-0.111001，用原码两位乘求[x? y]_原。

　　解：①数值部分的运算如下表所示，其中x*=0.111111, [-x*]_补=1.000001,2x*=1.111110, y*=0.111001。

部分积 乘数y* Cj 说   明 000.000000 000.111111 00111001 0 开始，部分积为0, Cj=0 根据yn-1ynCj=010加x*，保持Cj=0 000.111111 000.001111 001.111110 11001110 0 →2,得新的部分积，乘数同时→2位 根据yn-1ynCj=100加2x*，保持Cj=0 010.001101 000.100011 111.000001 11 01110011 0 →2,得新的部分积，乘数同时→2位 根据yn-1ynCj=110减x*，Cj置“1” 111.100100 111.111001 000.111111 0111 00011100 1 →2,得新的部分积，乘数同时→2位 根据yn-1ynCj=001加x*，Cj置“0” 000.111000 000111 形成最终结果

　　②乘积的符号为 

　　故[x? y]_原=1.111000000111。

　　不难理解，当乘数为偶数时，需作n/2次移位，最多作n/2+1次加法。当乘数为奇数时，乘数高位前可只增加一个“0”，此时需作n/2+1次加法，n/2+1次移位（最后一步移一位）。
　　虽然两位乘法可提高乘法速度，但它仍基于重复相加和移位的思想，而且随着乘数位数的增加，重复次数增多，仍然影响乘法速度的进一步提高。采用并行阵列乘法器可大大提高乘法速度。
　　原码乘法实现比较容易，但由于机器都采用补码作加减运算，倘若做乘法前再将补码转换成原码，相乘之后又要将负积的原码变为补码形式，这样增添了许多操 作步骤，反而使运算复杂。为此，有不少机器直接用补码相乘，机器里配置实现补码乘法的乘法器，避免了码制的转换，提高了机器效率。

　　3．补码一位乘法

　 　一种比较好的带符号数乘法的方法是布斯(Booth)算法。它采用相加和相减的操作计算补码数据的乘积。Booth算法对乘数从低位开始判断，根据两个 数据位的情况决定进行加法、减法还是仅仅移位操作。判断的两个数据位为当前位及其右边的位(初始时需要增加一个辅助位0)，移位操作是向右移动。在上例 中，第一次判断被乘数0110中的最低位0以及右边的位(辅助位0)，得00；所以只进行移位操作；第二次判断0110中的低两位，得10，所以作减法操 作并移位，这个减法操作相当于减去2a的值；第三次判断被乘数的中间两位，得11，于是只作移位操作；第四次判断0110中的最高两位，得01，于是作加 法操作和移位，这个加法相当于加上8a的值，因为a的值已经左移了三次。
　　一般而言，设y=y₀,y_ly₂…y_n为被乘数，x为乘数，y_i是a中的第i位(当前位)。根据y_j与y_i+1的值，Booth算法表示如下表所示，其操作流程如下图所示。在Booth算法中，操作的方式取决于表达式(y_i+1-y_i)的值，这个表达式的值所代表的操作为：

　　　0    无操作

　　　+1    加x

　　　-1    减x

Booth算法操作表示

yi yi+1 操作 说明 0 0 无 处于0串中，不需要操作 0 1 加x 1串的结尾 1 0 减x 1串的开始 1 1 无 处于1串中，不需要操作

实现32位Booth乘法算法的流程图

　　乘法过程中，被乘数相对于乘积的左移操作可表示为乘以2，每次循环中的运算可表示为对于x(y_i+1-y_i)2^31-i项的加法运算(i=3l，30，…，1，0)。这样，Booth算法所计算的结果  可表示为：

　　 x×(0-y₃₁)×2⁰

　　+x×(y₃₁-y₃₀)×2¹

　　+x×(y₃₀-y₂₉)×2²

　　…

　　+x×(y₁-y₀)×2³¹

　　=x×(-y₀×2³¹ +y₁×2³⁰ +y₂×2²⁹+y₃₁×2⁰)

　　=x×y

　　例：用Booth算法计算2×(-3)。

　　解：[2]_补=0010，  [-3]_补=1101，在乘法开始之前，R0和R1中的初始值为0000和1101，R2中的值为0010。

　　在乘法的第一个循环中，判断R1的最低位和辅助位为10，所以进入步骤1c，将R0的值减去R2的值，结果1110送人R0，然后进人第二步，将R0和Rl右移一位，R0和R1的结果为11110110，辅助位为l。
　　在第二个循环中，首先判断Rl的最低位和辅助位为0l，所以进入步骤1b，作加法，R0+R2=1111+0010，结果0001送入R0，这时R0R1的内容为0001 0110，在第二步右移后变为0000 1011，辅助位为0。
　　在第三次循环中，判断位为10，进入步骤lc，R0减去R2，结果1110送入R0，R1不变；步骤2移位后R0和R1的内容为1111 01011，辅助位为1。
　　第四次循环时，因两个判断位为11，所以不作加减运算，向右移位后的结果为1111 1010，这就是运算结果(—6)。
　　这个乘法的过程描述如下表所示，表中乘积一栏表示的是R0、R1的内容以及一个辅助位P，黑体字表示对两个判断位的判断。

用Booth补码一位乘法计算2 ×(-3)的过程

循环 步骤 乘积（R0,R1, P） 0 初始值 0000 1101 0 1 1c：减0010 1110 1101 0 2：右移1位 1111 0110 1 2 1b：加0010 0001 0110 1 2：右移1位 0000 1011 0 3 1c：减0010 1110 1011 0 2：右移1位 1111 0101 1 4 1a：无操作 1111 0101 1 2：右移1位 1111 1010 1

　　4．补码两位乘

　　补码两位乘运算规则是根据补码一位乘的规则，把比较y_iy_i+1的状态应执行的操作和比较y_i-1y_i 的状态应执行的操作合并成一步，便可得出补码两位乘的运算方法。

补码两位乘法运算规则如下

判断位yi-1y iyi+1 操作内容 000 [zi+1]补=2-2[zi]补 001 [zi+1]补=2-2{[zi]补+[x]补} 010 [zi+1]补=2-2{[zi]补+[x]补} 011 [zi+1]补=2-2{[zi]补+2[x]补} 100 [zi+1]补=2-2{[zi]补+2[-x]补} 101 [zi+1]补=2-2{[zi]补+ [-x]补} 110 [zi+1]补=2-2{[zi]补+-x}补} 111 [zi+1]补=2-2[zi]补

　　由上表可见，操作中出现加2[x]_补和加2[-x]_补，故除右移两位的操作外，还有被乘数左移一位的操作；而加2[x]_补和加2[-x]_补，都可能因溢出而侵占双符号位，故部分积和被乘数采用三位符号位。

　　例：[x]_补=0.0101，[y]_补=1.0101 求： [x? y]_补。

　　解：求解过程如下表所示。其中乘数取两位符号位即11.0101,[-x]_补=1.1011取三符号位为111.1011。

部分积 乘数 说    明 000.0000 + 000.0101 1101010 判断位为010，加[x]补 000.0101 000.0001 + 000.0101 0111010 →2位 判断位为010，加[x]补 000.0110 000.0001 + 111.1011 01 1001110 →2位 判断位为110，加[-x]补 111.1100 1001 最后一步不移位，得[x? y]补

　　故[x? y]_补=1.11001001

　 　可见，与补码一位乘相比，补码两位乘的部分积多取一位符号位（共3位），乘数也多取一位符号位（共2位），这是由于乘数每次右移2位，且用3位判断，故 采用双符号位更便于硬件实现。可见，当乘数数值位为偶数时，乘数取2位符号位，共需作n/2次移位，最多作n/2+1次加法，最后一步不移位；当n为奇数 时，可补0变为偶数位，以简化逻辑操作。也可对乘数取1位符号位，此时共作n/2+1次加法和n/2+1次移位（最后一步移一位）。
　　对于整数补码乘法，其过程与小数乘法完全相同。为了区别于小数乘法，在书写上可将符号位和数值位中间的“.”改为“，”即可。

四、除法运算

　　1．分析笔算除法

　　以小数为例，设 x=-0.1011，y=0.1101，求x/y

　　笔算除法时，商的符号心算而得：负正得负；其数值部分的运算如下面竖式。

　　所以商x/y=0.1101，余数=-0.00000111

　　其特点可归纳如下：

　　①每次上商都是由心算来比较余数(被除数)和除数的大小，确定商为1还是0。
　　②每做一次减法，总是保持余数不动，低位补0，再减去右移后的除数。
　　③商符单独处理。如果将上述规则完全照搬到计算机内，实现起来有一定困难，主要问题是：
　　a．机器不能“心算”上商，必须通过比较被除数(或余数)和除数绝对值的大小来确定商值，即|x|-|y|，若差为正(够减)上商1,差为负(不够减)上商0。
　　b．按照每次减法总是保持余数不动低位补0，再减去右移后的除数这一规则，则要求加法器的位数必须为除数的两倍。仔细分析发现，右移除数可以用左移余 数的办法代替，其运算结果是一样的，但对线路结构更有利。不过此刻所得到的余数不是真正的余数，只有将它乘上2^-n才是真正的余数。
　　c．笔算求商时是从高位向低位逐位求的，而要求机器把每位商直接写到寄存器的不同位也是不可取的。计算机可将每一位商直接写到寄存器的最低位，并把原来的部分商左移一位。

　　综上所述便可得原码除法运算规则。

　　2．原码除法：

　　原码除法和原码乘法一样，符号位是单独处理的。以小数为例：

　　设



　　　   

　　式中  为x的绝对值，记作x*

　　　 为y的绝对值，记作y*

　　即商符由两数符号位“异或”运算求得，商值由两数绝对值相除(x*/y*)求得。
　　小数定点除法对被除数和除数有一定的约束，即必须满足下列条件：

　　　0＜|被除数|≤|除数|

　　实现除法运算时，还应避免除数为0或被除数为0。前者结果为无限大，不能用机器的有限位数表示；后者结果总是0，这个除法操作等于白做，浪费了机器时间。至于商的位数一般与操作数的位数相同。
　　原码除法中由于对余数的处理不同，又可分为恢复余数法和不恢复余数法(加减交替法)两种。

　　（1）恢复余数法。恢复余数法的特点是：当余数为负时，需加上除数，将其恢复成原来的余数。
　　由上所述，商值的确定是通过比较被除数和除数的绝对值大小，即x*-y*实现的， 而计算机内只设加法器， 故需将x*-y*操作变为[x*]_补+[-y*]_补的操作。

　　例：已知：x=-0.1011,y=-0.1101,求：[x÷y]_原

　　解：由x*=0.1011，[x]_原=1.1011

　　　　y*=0.1101，[-y]_补=1.0011,[y]_原=1.1101

　　商值的求解过程如下：

被除数(余数) 商 说     明 0.1011 + 1.0011 0.0000 +[-y*]补（减去除数） 1.1110 + 0.1101 0 余数为负，上商0 恢复余数+[y*]补 0.1011 1.0110 + 1.0011 　　0 被恢复的被除数 ← 1位 +[-y*]补（减去除数） 0.1001 1.0010 + 1.0011 01      01 余数为正，上商1 ← 1位 +[-y*]补（减去除数） 0.0101 0.1010 +1.0011 011     011 余数为正，上商1 ← 1位 +[-y*]补（减去除数） 1.1101 + 0.1101 0110 余数为负，上商0 恢复余数+[y*]补 0.1010 1.0100 + 1.0011 　0110 被恢复的被除数 ← 1位 +[-y*]补（减去除数） 0.0111 01101 余数为正，上商1

　　故商值为0.1101

商的符号位为 

　　由此可见，共上商5次，第一次上的商在商的整数位上，这对小数除法而言，可用它作溢出判断。即当该位为“1”时，表示此除法为溢出，不能进行，应由程序进行处理；当该位为“0”时，说明除法合法，可以进行。
　　在恢复余数法中，每当余数为负时，都需恢复余数，这变延长了机器除法的时间，操作也很不规则，对线路结构不利。加减交替法可克服这些缺点。

　　（2）加减交替法。加减交替法又称不恢复余数法，可以认为它是恢复余数法的一种改进算法。
　　分析原码恢复余数法得知：
　　当余数Ri>0时，可上商“1”，再对Ri左移一位后减除数，即2R_i-y*。
　　当余数Ri>0时，可上商“0”，然后再做R_i+y*，即完成恢复余数的运算，再做2(R_i+y*)-y*，也即2R_i+y*。
　　可见，原码恢复余数法可归纳为：
　　当余数Ri>0时，商上“1”，做2R_i-y*的运算；
　　当余数Ri<0时，商上“0”，做2R_i+y*的运算。
　　这里已看不出余数的恢复问题了，而只是做加y*或减y*，因此，一般把它叫做加减交替法或不恢复余数法。

　　例：已知：x=-0.1011,y=-0.1101,求：[x÷ y]_原

　　解：[x]_原=1.1011, x*=0.1011

　　　　[y]_原=0.1101, y*=0.1101, [-y*]_补=1.0011

　　商值的求解过程如下表所示：

被除数(余数) 商 说     明 0.1011 + 1.0011 0.0000 +[-y*]补（减除数） 1.1110 1.1100 + 0.1101 0       0 余数为负，上商0 ← 1位 +[y*]补 (加除数) 0.1001 1.0010 + 1.0011 01 01 余数为正，上商1 ← 1位 +[-y*]补（减除数） 0.0101 0.1010 + 1.0011 011 011 余数为正，上商1 ← 1位 +[-y*]补（减除数） 1.1101 1.1010 + 0.1101 0110    0110 余数为负，上商0 ← 1位 +[y*]补 (加除数) 0.0111 01101 余数为正，上商1

　　商的符号位为 

　　所以 

　　分析此例可见，n位小数的除法共上商n+1次，第一次商用来判断是否溢出。倘若比例因子选择恰当，除数结果不溢出，则第一次商肯定是0。如果省去这位商，只需上商n次即可，此时除法运算一开始应将被除数左移一位减去除数，然后再根据余数上商。

　　(3)原码加减交替法所需的硬件配置。下图是实现原码加减交替除法运算的基本硬件配置框图。

　　图中A、X、Q均为n+1位寄存器，其中A存放被除数的原码，X存放除数的原码。移位和加控制逻辑受Q的末位Qn控制。(Qn=1作减法，Qn=0作加法)，计数器C用于控制逐位相除的次数n，G_D为除法标记，V为溢出标记，S为商符。

　　(4)原码加减交替除法控制流程。下图为原码加减交替除法控制流程图。

　 　除法开始前，Q寄存器被清0，准备接收商，被除数的原码放在A中，除数的原码放在X中，计数器C中存放除数的位数n。除法开始后，首先通过异或运算求出 商符，并存于S。接着将被除数和除数变为绝对值，然后开始用第一次上商判断是否溢出。若溢出，则置溢出标记V为1，停止运算，进行中断处理，重新选择比例 因子：若无溢出，则先上商，接着A、Q同时左移一位，然后再根据上一次商值的状态，决定是加还是减除数，这样重复n次后，再上最后一次商(共上商n+1 次)，即得运算结果。

　　对于整数除法，要求满足以下条件：

　　0<|除数|≤|被除数|

　　因为这样才能得到整数商。通常在做整数除法前，先要对这个条件进行判断，若不满足上述条件，机器发出出错信号，程序要重新设定比例因子。
　　上述讨论的小数除法完全适用于整数除法，只是整数除法的被除数位数可以是除数的两倍，且要求被除数的高M位要比除数(n位)小，否则即为溢出。如果被除数和除数的位数都是单字长，则要在被除数前面加上一个字的0，从而扩展成双倍字长再进行运算。

　　3．补码除法

　　与补码乘法类似，也可以用补码完成除法操作。补码除法也分恢复余数法和加减交替法，后者用得较多，在此只讨论加减交替法。

　　(1)补码加减交替法运算规则。补码除法其符号位和数值部分是一起参加运算的，因此在算法上不像原码除法那样直观，主要需解决三个问题：第一，如何确定商值；第二，如何形成商符；第三，如何获得新的余数。
　　①商值的确定。欲确定商值，必须先比较被除数和除数的大小，然后才能求得商值。

　　a． 比较被除数(余数)和除数的大小。补码除法的操作数均为补码，其符号又是任意的，因此要比较被除数[x]_补和除数[y]_补的大小就不能简单地用[x]_补减去[y]_补。实质上比较[x]_补和[y]_补的大小就是比较它们所对应的绝对值的大小。同样在求商的过程中，比较余数[R_i]_补与除数[y]_补的大小，也是比较它们所对应的绝对值。这种比较的算法可归纳为以下两点：
　　第一，当被除数与除数同号时，做减法，若得到的余数与除数同号，表示“够减”，否则表示“不够减”。
　　第二，当被除数与除数异号时，做加法，若得到的余数与除数异号，表示“够减”，否则表示“不够减”。
　　此算法如下表所示。

比较[x]补与[y]补的符号 求余数 比较 [Ri]补与[y]补的符号 同号 [x]补-[y]补 同号，表示“够减” 异号 [x]补+[y]补 异号，表示“够减”

　　b．商值的确定。补码除法的商也是用补码表示的，如果我们约定商的末位用“恒置1”的舍入规则，那么除末位商外，其余各位的商值对正商和负商而言，上 商规则是不同的。因为在负商的情况下，除末位商以外，其余任何一位的商与真值都正好相反。因此，上商的算法可归纳为以下两点：
　　第一，如果[x]_补与[y]_补同号，商为正，则“够减”时上商“1”。“不够减”时上商“0”(按原码规则上商)。
　　第二，如果[x]_补与[y]_补异号，商为负，则“够减”时上商“0”，“不够减”时上商“1”(按反码规则上商)。
　　结合比较规则与上商规则，使可得商值的确定办法，如下表所示。

[x]补与[y]补 商 [R]补与[y]补 商值 同号 正 同号，表示“够减” 1 异号，表示“不够减” 0 异号 负 异号，表示“够减” 0 同号，表示“不够减” 1

　　进一步简化，商值可直接由下表确定。

[x]补与[y]补 商值 同号 1 异号 0

　　②商符的形成。在补码除法中，商符是在求商的过程中自动形成的。
　　 在小数定点除法中，被除数的绝对值必须小于除数的绝对值，否则商大于1而溢出。因此，当[x]_补与[y]_补同号时，[x]_补-[y]_补所得的余数[R₀]_补与[y]_补异号，商上“0”，恰好与商的符号(正)一致；当[x]_补与[y]_补异号时，[x]_补+[y]_补所得的余数[R₀]_补与[y]_补同号，商上“1”，这也与商的符号(负)一致。可见，商符是在求商值过程中自动形成的。
　　此外，商的符号还可用来判断商是否溢出。例如，当[x]_补与[y]_补同号时，若[R₀]_补与[y]_补同号，上商“l”，即溢出。当[x]_补与[y]_补异号时，若[R₀]_补与[y]_补异号，上商“0”，即溢出。
　　当然，对于小数补码运算，商等于“-1”应该是允许的，但这需要特殊处理，为简化问题，这里不予考虑。
　　③新余数[R_i+1]_补的获得。
　　新余数[R_i+1]_补的获得方法与原码加减交替法极相似，其算法规则为：
　　当[R₀]_补与[y]_补同号时，商上“l”，新余数
　　　[R_i+1]_补=2[R_i]_补-[y]_补=2[R_i]_补+[-y]_补
　　当[R₀]_补与[y]_补异号时，商上“0”，新余数
　　　[R_i+1]_补=2[R_i]_补+[y]_补

　　将此法列于下表：

[R]补与[y]补 商 新余数[Ri+1]补 同号 1 [Ri+1]补=2[Ri]补+[-y]补 异号 0 [Ri+1]补=2[Ri]补+[y]补

　　如果对商的精度没有特殊要求，一般可采用“末位恒置1”法，这种方法操作简单，易于实现，而且最大误差仅为2^-n。

　　例：已知：x=-0.1001, y=+0.1101 求： [x÷y]_补

　　解：[x]_补=1.0111,[y]_补=0.1101,[-y]_补=1.0011

　　运算过程如下：

被除数（余数） 商  上商 说    明 1.0111 +   0.1101 0.0000 [x]补与[y]补异号，+[y]补 0.0100    0.1000 +  1.0011        1      1 [R]补与[y]补同号，上商1 ← 1位 +[-y]补 1.1011    1.0110 +  0.1101 10 10 [R]补与[y]补异号，上商0 ← 1位 +[y]补 0.0011    0.0110 +  1.0011 101 101 [R]补与[y]补同号，上商1 ← 1位 +[-y]补 1.1001    1.0010   1010 10101 [R]补与[y]补异号，上商0 ← 1位,末位商恒置“1”

　　所以[x÷y]_补=1.0101

　　(2)补码加减交替法所需的硬件配置。补码加减交替法所需的硬件配置基本上与原码加减交替法所需的硬件配置相似。

　　(3)补码加减交替法的控制流程。

　　上图示出了补码加减交替除法的控制流程。

　 　除法开始前，Q寄存器被清0，准备接收商，被除数的补码在A中，除数的补码在x中，计数器C中存放除数的位数M。除法开始后，首先根据两操作数的符号确 定是作加法还是减法，加(或减)操作后，即上第一次商(商符)，然后A、Q同时左移一位，再根据商值的状态决定加或减除数，这样重复”次后，再上一次末位 商“1”(恒置“1”法)，即得运算结果。

    补充说明几点：
　　①图中未画出补码除法溢出判断的内容；②按流程图所示，多作一次加(或减)法，其实末位恒置“1”前，只需移位不必作加(或减)法；⑨与原码除一样， 图中均未指出对0进行检测，实际上在除法运算前，先检测被除数和除数是否为0，若被除数为0，结果即为0；若除数为0，结果为无穷大，这两种情况都无需继 续作除法运算；④为了节省时间，上商和移位操作可以同时进行。