补码的加.doc

一.补码的加、减运算

在计算机中，通常总是用补码完成算术的加减法运算。其规则是：
　　[X+Y]补= [X]补 + [Y]补 ，[X-Y]补= [X]补 - [Y]补 = [X]补 + [-Y]补

　　这表明，有了补码表示的被加（减）数和加（减）数，要完成计算补码表示的二数之和或二数之差，只需用二数的补码直接执行加减运算即可，符号位与数值位同等对待，一起参加运算，若运算结果不溢出，即不超出计算机所能表示的范围，则结果的符号位和数值位同时为正确值。此外，还可以看到，实现减运算时，用的仍是加法器线路，把减数的负数的补码送加法器即可。在有了一个数的补码之后，求这个数的负数的补码，是简单地把这个数的补码逐位取反再在最低位加1即可得到。例如，[Y]补=101101，则[-Y]补=010011，这大大简化了加减运算所用的线路和加减运算的实现算法。

　　下面的问题是如何检查加减运算中的溢出问题。通常有三种表述方式（说法）：
　　(1) 两个符号相同的补码数相加，如果和的符号与加数的符号相反，或两个符号相反的补码数相减，差的符号与减数的符号相同，都属于运算结果溢出。这种判别方法比较复杂，要区别加还是减两种不同运算情况，还要检查结果的符号与其中一个操作数的符号的同异，故很少使用；

　　(2) 两个补码数相加减时，若最高数值位向符号位送的进位值与符号位送向更高位的进位值不相同，也是运算结果溢出。

　　(3) 在采用双符号位（如定点小数的模4补码）运算时，若两个符号位的得值不同（01或10）则是溢出。01表明两个正数相加，结果大于机器所能表示的最大正数，称为"上溢"；10表明两个负数相加，结果小于机器所能表示的最小负数，称为"下溢"；双符号位的高位符号位，不管结果溢出否，均是运算结果正确的符号位，这个结论在乘法运算过程中是很有实际意义的。请注意，在采用双符号位的方案中，在寄存器和内存储器存储数据时，只需存一位符号，双符号位仅用在加法器线路部分。

　　再次强调，这三种不同说法是对同一个事实的略有区别的表述，实现时用到的线路可以有所区别，但问题的实质是完全一样的。请看 [X]补 + [Y]补 的运算情况：

　　01011 　　 　　　　10101 　　 　　　10100 　　　　
　+ 01000 　　　　 　+ 11000 　　　　 + 11001 　　　　
------------- ------------- ------------ 　　 　
　　10011 　　　　　　101101 　　　　　101101 　　　　
　　（1） 　　　　　　（2） 　　　　　　（3）

　　10111 　　　　　　001011 　　　　　110111
　+ 10101 　　　　　+ 001000 　　　　 110101
--------- -------------- ----------　　
　 101000 　　　　　　010011 　　　　 1101100
　　（4） 　　　　　　（5） 　　　　　　（6）

　　这全都是溢出情况，前4个使用一个符号位，后2个使用二个符号位。用前面说的任何一种表述解释这里的溢出都是可以的。例如，对于（1），从正加正的得负，或数据位向符号位送的进位值为1，而符号位送向更高位的进位值却为0，二者不相同，或在（5）中使用双符号位方案时，其双符号位结果为01，都是运算结果溢出。

　　凡补码加减运算其结果不属于上述情况的，均不是溢出，结果的符号位和数值位均正确。这里虽然讨论的都是加法运算，对减运算亦适用。正减负等同正加正，正减正等同正加负，正如前面说过的，减运算也是用加法器完成的。例如：

　　01011 　　　　　11101 　　　　　001011 　　　　111101
　+ 00100 　　　　+ 11010 　　　　+ 000100 　　　+ 111010

　　01111 　　　　　10111 　　　　　001111 　　　　110111
　　（1） 　　　　　（2） 　　　　　 （3） 　　　　 （4）

　　（1）、（2）使用一位符号位，（3）、（4）使用二位符号位，符号位送向更高位的进位值，不论其值为0或为1一律在取模后丢弃。

实现补码加减运算的逻辑电路
运算前，X、Y寄存器分别存储被加（减）数 和 加（减）数，计算结果存回X寄存器；F为加法器，能在命令X→F和Y→F信号的控制下接收两个寄存器中的数据并完成加法运算，运算结果在F→X命令信号的控制下接收回X寄存器中。

　　为实现减运算，应将Y寄存器中补码数据的负数表示送到加法器F，这可以通过送Y寄存器中每位数据的反码并在F的最低位给出进位1输入信号变通完成，用/Y→F和1→F控制命令实现。

图2.5 实现补码加减运算的逻辑电路

二、原码一位乘的实现：
设X=0.1101，Y=－0. 1011，求X*Y
解：符号位单独处理， x符＋ y符
数值部分用原码进行一位乘，如下图所示：

高位部分积
低位部分积/乘数
说明

      0 0 0 0 0 0  
1 0 1 1

起始情况
＋） 0 0 1 1 0 1

乘数最低位为1，+X

      0 0 1 1 0 1

      0 0 0 1 1 0
1 1 0 1
1(丢)
右移部分积和乘数

＋） 0 0 1 1 0 1

乘数最低位为1，+X

      0 1 0 0 1 1

      0 0 1 0 0 1
1 1 1 0
1(丢)
右移部分积和乘数

＋） 0 0 0 0 0 0

乘数最低位为0，+0

      0 0 1 0 0 1

      0 0 0 1 0 0
1 1 1 1
0(丢)
右移部分积和乘数

＋） 0 0 1 1 0 1

乘数最低位为1，+X

      0 1 0 0 0 1

      0 0 1 0 0 0
1 1 1 1
1(丢)
右移部分积和乘数

2、原码一位除的实现：一般用不恢复余数法（加减交替法）

部分积
低位部分积 附加位
操作说明

      0 0 0 0 0 0  
   1 0 1 1

起始情况
＋） 0 0 0 0 0 0

乘数最低位为1，+X

      0 0 0 0 0 0

      0 0 0 0 0 0
1 1 0 1
1(丢)
右移部分积和乘数

＋） 1 1 0 0 1 1

乘数最低位为1，+X

      0 1 0 0 1 1

      0 0 1 0 0 1
1 1 1 0
1(丢)
右移部分积和乘数

＋） 0 0 0 0 0 0

乘数最低位为0，+0

      0 0 1 0 0 1

      0 0 0 1 0 0
1 1 1 1
0(丢)
右移部分积和乘数

＋） 0 0 1 1 0 1

乘数最低位为1，+X

      0 1 0 0 0 1

      0 0 1 0 0 0
1 1 1 1
1(丢)
右移部分积和乘数

原码一位乘法的实现算法(二)

　　用原码实现乘法运算是十分方便的。原码表示的两个数相乘，其乘积的符号为相乘两数符号的异或值，数值则为两数绝对值之积。
下面是恢复余数除法的一个例子。
　　假定 X=0.1011 , Y=0.1101, 则有 [X]补 = 00 1011
　　　　　　　　 [Y]补 = 00 1101 , [-Y]补 = 11 0011

　　除法计算结束,二数符号异或为0,商是 +0.1101,余数为0.0111 * 2-4 ,余数0111是左移4次后得到的结果,所以真正的结果为这个值乘上2-4。若最后一次的余数为负,正确的余数应为 +Y 恢复后的正余数乘上2-4 。

　　这种方法的缺点是明显的，当某一次 -Ｙ的差值为负时，要多一次＋Y恢复正余数的操作,降低了执行速度,又使控制线路变得复杂,因此在计算机中很少采用。在计算机中普遍采用的是不恢复余数的除法方案,它是对恢复余数除法的一种修正措施,即当某一次减得的差值为负时,不是恢复它为正差值后再继续运算,而是设法直接用这个负的差值直接求下一位商,其实现原理叙述如下:

　　在恢复余数的除法运算中,若第i-1次求商时的余数为 +Ri-1 ,本次上商为1，下一次求商用的办法是
　　　　Ri= 2Ri-1 - Y

　　当Ri < 0时,第i位的商上0,而恢复余数的操作结果应为Ri + Y,下一次,即第i+1次求商的减法操作是
　　　　Ri+1= 2 (Ri+ Y ) - Y = 2 Ri + 2Y - Y = 2Ri+ Y

　　上述公式表明,当某一次求商,其减得的差值为负,即R<0时,本次上商为0,继续求下一位商时,可以不必恢复正余数,而是直接将负的差值左移一位(得2R)后,再采用加上除数的办法来完成,即通过判别2R+Y运算的结果为正还是为负。由此可得出不恢复余数的除法运算规则为:

　　当余数为正时,商上1,求下一位商的办法,是正余数左移一位,用减去除数的办法得到;
　　余数为负时,商上0,求下一位商的办法,是负余数左移一位,用加上除数的办法得到。即在本方案中,在求得本位商值的同时,还要影响到用减去还是用加上除数的操作继续求下一位商,所以不恢复余数除法又叫加减交替除法。

　　下面给出不恢复余数除法执行除运算过程的一个例子。用的还是X=0.1011,Y=0.1101这两个值, [X]补 = 00 1011 , [Y]补 = 00 1101 , [-Y]补 = 11 0011。

　　运算结果,商的数值位为1101,符号位为相除二数符号的异或值0,结果为+0.1101。
原码一位除的不恢复余数的运算过程的详细控制流程如图2.9所示。

图2.9 不恢复余数除法的运算的控制过程

　　至此,我们可把定点原码一位除的实现方案小结如下:
　　(1) 对定点小数除法,首先要比较除数和被除数的绝对值的大小,需要防止出现数值溢出的错误。
　　(2) 商的符号为相除二数的符号的半加和。
　　(3) 计算机中用加减交替法实现除法运算时,被除数的位数可以是除数的两倍,其低位的数值部分，开始时放在用于保存商的寄存器中。运算过程中,放被除数和商的寄存器同时左移一位。
　　(4) 在计算机中,求差和移位是在同一个操作步骤中完成的,而不是像我们书面写的那种形式用两个步骤完成。
补码一位乘法(Booth布斯算法)
本文适用于补码表示的定点小数或定点整数乘法运算（硬件或软件实现）
◆ 先考查两个补码乘法运算的例子
例1： 已知 X=0.1011Y=0.0001（真值）
[X]补=01011 , [Y]补= 00001
[X*Y]补=000001011
[X]补*[Y]补=000001011
这时有，[X*Y]补=[X]补*[Y]补
例2： 已知 X=0.1011，Y= – 0.0001（真值）
[X]补=01011 , [Y]补= 11111
[X*Y]补=111110101
[X]补*[Y]补=101010101
显然，[X*Y]补 ≠ [X]补*[Y]补
▲ 对两个正数来说，它们补码的乘积等于它们乘积的补码。若乘数是负数时，这种情况就不成立了。
原码乘法的主要问题是符号位不能参加运算，单独用一个异或门产生乘积的符号位。故自然提出能否让符号数字化后也参加乘法运算，补码乘法就可以实现符号位直接参加运算。
为了得到补码一位乘法的规律，先从补码和真值的转换公式开始讨论。（以纯小数为例）
1．  补码与真值的转换公式
设　[x]补 = x0 . x1x2…xn ，有：

n

x = - x0＋∑  xi2-i
i＝1
等式左边 x 为真值。此公式说明真值和补码之间的关系。
2.  补码的右移
正数右移一位，相当于乘1/2(即除2)。负数用补码表示时，右移一位也相当于乘1/2。因此，在补码运算的机器中，一个数不论其正负，连同符号位向右移一位（即符号扩展），若符号位保持不变，就等于乘1/2。
3.  补码乘法规则
设被乘数 [x]补 = x0.x1x2…xn 和乘数 [y]补 = y0.y1y2…yn （注意：包括符号位共n+1位）均为任意符号，则有补码乘法算式

n

[x·y]补= [x]补·( -y0＋∑ yi2-i )
i＝1
为了推出串行逻辑（递推），实行分步算法，将上式展开加以变换：
[x·y]补 = [x]补·[ - y0 + y12-1 + y22-2 + … + yn2-n]
= [x]补·[ - y0 + (y1 - y12-1) + (y22-1 - y22-2) + … + (yn2-(n-1) - yn2-n)]
= [x]补·[(y1 - y0) + (y2 - y1) 2-1 + … + (yn - yn-1) 2-(n-1) + (0 - yn)2-n]
= [x]补·[...................................] (yn+1 =  0)
写成递推公式如下：
[ z0 ]补 = 0 (赋初值0)
[ z1 ]补 = 2 -1{ [ z0 ]补 +  ( yn+1 - yn ) [x]补 }       (yn+1 =  0)
; 注：2 -1表示右移，带符号扩展。补码的加减法在移位时不考虑进位C
…
[ zi ]补 = 2 -1{ [ zi-1 ]补 +  ( yn-i+2 - yn-i+1 ) [x]补 }
…
[ zn ]补 = 2 -1{ [ zn-1 ]补 +  ( y2 - y1 ) [x]补 }
[ zn+1 ]补 = [ zn ]补 +  ( y1 - y0 ) [x]补 = [ x·y ]补 此最后一步不需要移位（对纯小数！）
开始时，部分积为 0，即 [z0]补 = 0。然后每一步都是在前次部分积的基础上，由 ( yi+1 -  yi ) ( i = 0，1，2，…，n) 决定对[x]补的操作，再右移一位，得到新的部分积。如此重复 n + 1步，最后一步不移位，便得到 [ x·y ]补 ，这就是有名的Booth布斯算法。
实现这种补码乘法规则时，在乘数最末位后面要增加一位补充位 yn+1 。开始时，由 ynyn+1 判断第一步该怎么操作；然后再由 yn - 1 yn 判断第二步该怎么操作。因为每做一步要右移一位，故做完第一步后，yn - 1 yn 正好移到原来 ynyn+1 的位置上。依此类推，每步都要用 ynyn+ 1 位置进行判断，我们将这两位称为判断位。
如果判断位 ynyn+1 = 01，则 yi+1－ yi = 1，做加[x]补操作；
如果判断位 yn yn+1 = 10，则 yi+1 －yi =  - 1，做加[ - x]补（或者－[x]补）操作；
如果判断位 yn yn+1 = 11 或 00，则 yi+1－yi = 0，[ zi ] 加0，即保持不变。
4. 补码一位乘法运算规则
(1) 如果 yn = yn+1，部分积 [ zi ] 加0，再右移一位；
(2) 如果 yn yn+1 = 01，部分积加[ x ]补，再右移一位；
(3) 如果 yn yn+1 = 10，部分积加[ - x]补（或减[x]补），再右移一位；
这样重复进行 n+1 步，但最后一步不移位（对纯小数）。包括一位符号位，所得乘积为 2n+1 位，其中 2n 为尾数位数。对于码整数相乘，最后一步也要移位！乘积有2n+2 位，其中 2n 为尾数位数。
【例 】  x = 0.1101， y = 01011，用补码一位乘法计算 x·y = ？
[解:]     求解过程如下：

部分积

乘数
说明

00.0000

0.
1
0
1
1
0
yn+1 =  0

+

11.0011

ynyn+1 = 10，加[-x]补

11.0011

→
11.1001

1
0
1
0
1
1
右移一位

+

00.0000

ynyn+1 = 10，加0

11.1001

→
11.1100

1
1
0
1
0
1
右移一位

+

00.1101

ynyn+1 = 01，加[x]补

00.1001

→
00.0100

1
1
1
0f
1
0
右移一位

+

11.0011

ynyn+1 = 01，加[-x]补

11.0111

→
11.1011

1
1
1
1
0
1
右移一位

+

00.1101

ynyn+1 = 01，加[x]补

00.1000

1
1
1
1
0
1
最后一步不移位
所以                        [x · y]补 = 0.10001111

实现32位Booth乘法算法的流程图
例：用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