运算方法与运算部.ppt

第三章运算方法与运算部件,在计算机中，完成数值运算的部件是CPU中的算术逻辑运算单元ALU。它的逻辑结构牵连到机器的指令系统、数据表示方法、运算方法、以及选用的逻辑器件等。,本章重点介绍计算机中完成加、减、乘、除、逻辑运算的基本运算方法和相关运算器的构成及工作原理。,一、定点加减运算(补码运算）二、溢出判别三、移位四、十进制运算五、逻辑运算（简介）,第一节算术逻辑运算基础,1.定点加减运算,一、补码加减运算计算机中，常用补码进行加减运算。补码可将减法变加法进行运算。补码运算特点：符号位与数值位一同运算。运算的基本规则：X补+Y补=X+Y补X-Y补=X补-Y补=X补+-Y补由Y补求得-Y补。其方法是：对Y补包含符号位各位求反，末位加1。,1.X补+Y补=2X0+X+2Y0+Y=2(X0+Y0)+(X+Y)（1）若X0Y0=00，则X补+Y补=X+Y=X+Y补；（2）若X0Y0=01或10，则X补+Y补=2+（X+Y）当X+Y0时，2+（X+Y）2，进位丢失，得：X补+Y补=X+Y=X+Y补；当X+YX+Y-1,22+(X+Y)1此时，X补+Y补=2+(X+Y)=X+Y补（2自然丢失）,在模2下，设X补=X0X1X2Xn，Y补=Y0Y1Y2Yn则X补=2X0+X，Y补=2Y0+Y,证明：,2、X补+Y补=X+Y补Y补=X+Y补-X补又X-Y补=X+(-Y)补=X补+-Y补-Y补=X-Y补-X补+得：Y补+-Y补=X+Y补-X补+X-Y补-X补=X+Y+X-Y补-X补-X补=X+X补-X补-X补=0-Y补=-Y补即X-Y补=X补+-Y补=X补-Y补,例1：已知机器字长n=8，X=44，Y=53求：X+Y=？,解：X原=00101100，Y原=00110101X补=00101100，Y补=00110101,结果：X+Y=(+1100001)2=+97,X补=00101100+Y补=00110101X+Y补=01100001,超出8位，模值舍弃。结果：X+Y=(-1100001)2=-97,X补=11010100+Y补=11001011X+Y补=110011111,例2：已知机器字长n=8，X=-44，Y=-53，求：X+Y=？,解：44补=00101100,53补=00110101X补=-44补=11010011+1=11010100，Y补=-53补=11001010+1=11001011,模值舍弃结果：X-Y补=(0.0111000)2，X-Y=(+0.0111)2,X补=0.1101000+-Y补=1.101000010.0111000,例3：已知机器字长n=8，X=0.1101，Y=0.0110求：X-Y=？,解：X补=0.1101000，Y补=0.0110000，-Y补=1.1010000,X补=1.0011000+-Y补=0.01100001.1001000,例4：已知机器字长n=8，X=-0.1101，Y=-0.0110求：X-Y=？,解：X补=1.0011000，Y补=1.1010000-Y补=0.0110000,结果：X-Y补=(1.1001000)2X-Y=(-0.0111)2,2.溢出的检测,溢出：运算结果超出了计算机所能表示的数据范围。正溢（上溢）：运算结果为正而绝对值超出了表示的范围。负溢（下溢）：运算结果为负而绝对值超出了表示的范围。定点数的溢出根据数值本身判断。,例：已知机器字长n=8，X=120，Y=10，求：X+Y=？,解：X补=01111000，Y补=00001010，X补=01111000+Y补=0000101010000010,X+Y补=10000010，X+Y=11111110X+Y的真值=-1111110=(-126)10运算结果超出机器数值范围发生溢出错误。8位计算机数值表达范围：(-128+127),二、溢出判断规则与判断方法,两个相同符号数相加，其运算结果符号与被加数相反则产生溢出；两个相异符号数相减，其运算结果符号与被减数相反则产生溢出。相同符号数相减，相异符号数相加不会产生溢出。溢出判断方法：进位判断法，双符号位法。,（1）进位溢出判断法SC,两单符号位的补码进行加减运算时，若最高数值位向符号位的进位值C与符号位产生的进位输出值S相同时则无溢出，否则溢出。例：X补=1.101X补=1.110+Y补=1.001+Y补=0.100X+Y补=10.110X+Y补=10.010C=0，S=1有溢出C=1，S=1无溢出X+Y=+0.010结论：OVR=SC=0（无溢出）OVR=SC=1（有溢出）其中：SC=01正溢；SC=10负溢,(2)双符号位（变形补码）溢出判断法,设第一符号位Sf1，第二符号位Sf2，Sf1Sf2双符号含义：00表示运算结果为正数；01表示运算结果正向溢出；10表示运算结果负向溢出；11表示运算结果为负数。结论：OVR=Sf1Sf2=0无溢出OVR=Sf1Sf2=1有溢出运算结果的真正符号位是左边第一位：Sf1。,例1：X=0.1001,Y=0.0101,求：X+Y=？,解:X补=00.1001+Y补=00.0101X+Y补=00.1110双符号位相同，运算结果正确，无溢出。X+Y=+0.1110,解:X补=11.0111+Y补=11.1011X+Y补=111.0010模值舍弃双符号位相同，运算结果正确，无溢出。X+Y=-0.1110,例2：X=-0.1001，Y=-0.0101，求：X+Y=？,例3：X=0.1011，Y=0.0111，求X+Y补=？,解:X补=00.1011+Y补=00.0111X+Y补=01.0010双符号位为01，运算结果不正确，正向溢出。,解:X补=11.0100+1=11.0101Y补=00.0111-Y补=11.1001X补=11.0101+-Y补=11.1001X+Y补=110.1110双符号位为10，运算结果不正确，负向溢出。,例4：X=-0.1011，Y=0.0111，求：X-Y补=？,模值舍弃,三、补码加减法运算规则如下：参加运算的操作数用补码表示。符号位与数值位一样参加运算。如果是加法运算，则直接相加如果是减法，那么减数连同符号位一起取反，然后末位加1。运算的结果仍然是补码形式。,四、移位操作,移位操作是实现算数和逻辑运算不可缺少的基本操作，分为算术移位、逻辑移位和循环移位。移位操作可以实现对操作数的左移或右移一位或若干位。移位的过程如下：,补码左移,1、算术移位：指带符号数的移位，移位后符号不变。,11010010,10100100,左移时，各位依次左移，最高有效位左移到符号位，末位补0。在补码左移时如果不发生溢出，那么对于最高有效位无论是0或1，左移至符号位使它仍保持不变，如果有溢出，那么对于单符号位补码将会破坏正确的符号。,补码右移,11010010,11101001,右移时连同符号位一起，各位依次右移，符号位的值右移至最高有效位，而符号位本身不变。,移掉,移掉,原码：不论正数负数，移位操作都相同。左移：符号位保持不变，各位依次左移，末位补0。右移：符号位保持不变，最高有效位补0，末位丢弃。注意：左移时如果最高有效位已经是1，左移后将发生溢出。,原码移位,10101101,11011010,移掉,补0,2、逻辑移位：左移低位补0、右移高位补0。,逻辑右移,01101011,00110101,移掉,补0,在程序中，常用算术逻辑移位指令实现简单的乘除运算。算术左移或右移n位，分别实现对带符号数乘以2n或除以2n逻辑左移或右移n位，分别实现对无符号数乘以2n或除以2n,3、循环移位：左移时最高位移到最低位。右移时最低位移到最高位。,常用于：实现循环控制、高低字节互换或与算术逻辑移位指令一起实现双倍字长或多倍字长的移位。,循环右移,01101011,10110101,补0,第二节算术逻辑运算部件ALU,ALU部件主要用来完成对二进制数的定点算术运算和逻辑运算。算术运算主要包括加法和减法运算。逻辑运算主要指与、或、非、异或等运算。加法又是各种运算的基础，因此ALU的核心是加法器。一、加法单元通常采用全加器。全加器有三个输入量：A操作数的第i位AiB操作数的第i位Bi低位送来的进位Ci两个输出量：全加和I和向高位的进位Ci+1全加器的框图及功能表如下：,Ci,Ci+1,FI,Xi,Yi,全加器的逻辑图,全加器功能表,第二节算术逻辑运算部件ALU,(1)用与非门构成的全加器根据功能表可以写出I和Ci+1的逻辑表达式：FIXiYiCiXiYiCiXiYiCiXiYiCiCi+1XiYiCiXiYiCIXiYiCIXiYiCI化简表达式，可得到相应的全加器的表达式如书57页(2)用半加器构成的全加器不考虑进位输入，两数码相加称为半加。半加求和可用异或门实现，所以也称异或门为半加器。显然，全加可用两次半加实现，逻辑式如下：IAiBiCICi+1AiBi+(AiBi)CI,第二节算术逻辑运算部件ALU,(3)串行加法器和并行加法器全加器只能实现对一位数的加法运算，为了完成对多位数的相加，就要组成加法器。通常有2种形式：a.串行加法器只有一位全加器，使用移位寄存器从低位到高位串行的提供操作数相加。每产生一位和需串行的送入结果寄存器中。进位信号由一位触发器保存，参与下一位运算。图见书58页。速度较慢，基本不采用。b.并行加法器并行加法器中全加器的位数与操作数的位数相同，可以同时对操作数的各位进行相加。由于操作数各位是同时提供的，最低进位逐级影响到最高位。因此它的最长运算时间是由进位信号的传递时间决定，而每位全加器本身的求和延迟是次要的，所以提供并行加法器速度的关键是尽量加快进位的产生和传递。,第二节算术逻辑运算部件ALU,二、并行加法器进位链进位链：并行加法器中传递进位信号的逻辑线路。1.基本进位公式每一位的进位表达式为：Ci1=XiYi+(XiYi)Ci其中Xi、Yi取决于本位参加运算的两个数，而与低位进位无关，因此称XiYi为进位产生函数，用Gi表示:GiAiBi(AiBi)Ci不但与本位的两个数有关，还依赖于低位的进位，因此称AiBi为进位传递函数，用Pi表示PiAiBi其含义为：当两个输入均为1，必然要向高位产生进位当两个输入中有一个为1，低位传来的进位Ci-1将超越本位向更高的位传递所以有Ci1=Gi+PiGi,第二节算术逻辑运算部件ALU,2.并行加法器的串行进位如图：书59页当操作数为n位长时，需要n位全加器构成加法器如图3.并行进位(先行进位、同时进位）为了解决并行加法器的运算速度，就必须解决进位传递的问题，方法是让各级进位信号同时形成，而不是串行形成。线路图如图书61页。组内并行、组间串行的进位链以16位加法器为例，将它分为4组，每组4位，各组内采用4位并行进位加法器，组间串行。采用这种结构，尽管进位延迟较纯串行方式缩短很多，但如果需要进一步提高速度，可采用组内并行、组间并行的进位链。5.组内并行、组间并行的进位链组间也采用并行进位，此结构相当于将加法器分为两级，4个小组的组内进位链为0级，组间进位链为1级,第二节算术逻辑运算部件ALU,三、ALU举例ALU能完成多种算术和逻辑运算。为了简化结构，ALU在加法器的基础上扩展其他运算功能。以一个4位片ALUSN74181为例：1.SN74181外特性,第二节算术逻辑运算部件ALU,2.SN74181内部特性（详见书63页表31)当选择M1时，ALU执行逻辑运算当选择M0时，ALU执行算术运算,第二节算术逻辑运算部件ALU,3.SN74181功能表列出了这种ALU可以完成的16种不同的算术或逻辑运算操作。例题：P64页表324.用SN74181构成多位的ALU每片74181可作为一个4位的小组，组间可以采用串行进位也可采用并行进位。书65页图38既是一个16位并行进位ALU结构。,下课,第二节算术逻辑运算部件ALU,第三节定点乘法运算,在计算机中实现乘除法运算，有三种方式：(1)软件实现：在低档微机中无乘除指令，只能用乘法或除法子程序实现。(2)在原有实现加减运算的ALU的基础上增加一些逻辑线路以实现乘除运算。(3)设置专用的乘除法器：主要用于要求快速乘除运算的机器中。一、无符号数一位乘,手工乘法：设X=0.1101Y=0.1011求XY=?0.11010.101111011101000011010.10001111XY=+0.10001111如果在计算机中实现乘法计算，要解决：1.局限于加法器的两个输入端。2.结合移位，N位加法器可实现2个N数相乘。3.完成运算后，寄存器中保存乘积的高位部分，乘数寄存器中保存乘积的低位部分。,第三节定点乘法运算,由于计算机的局限性，多位数的乘法要执行多次加法而且要浪费大量的器件，因此在计算机中乘法运算采用的方法是：将n位乘转换成n次“累加与移位”，也就是每一步只求一位乘数所对应的新部分积，并与原部分积作一次累加，然后右移一次。计算机内实现原码一位乘：无符号数一位乘的算法流程框图为下图：其中：图中使用了三个寄存器A、B和CB用来存放被乘数，C存放乘数。A初值为0，然后存放部分积，最后存放乘积高位,第三节定点乘法运算,开始,N位被乘数BN位乘数C，0A,C0=1?,A+BA,A+0A,A、C右移一位,重复n次,结束,Y,N,N,Y,设X=1101Y=1011求XY=?B(被乘数）C0AC(乘数）C0AC(乘数）000001011C00B110101101001101101C01B110110011010011110C000000001001001001111C01B110110001010001111,1101,0000,0,1011,初始状态,第一节拍,第二节拍,第三节拍,第四节拍,1101101110001111,第三节定点乘法运算,硬件实现无符号数一位乘软件实现无符号数一位乘可用子程序实现乘法运算。算法仍然是将乘法化为多次累加和移位二、带符号数一位乘定点原码一位乘的方法和无符号数的方法一样。实现方法是将符号位与数值位分别处理一般带符号数的运算用补码比较方便，可以先讨论论补码一位乘的算法。,第三节定点乘法运算,校正法设X补=X0X1X2Xn，Y补=Y0Y1Y2Yn（1）当Y0，即Y0=0时，X补Y补=X补Y=XY补（2）当Y0，即Y0=1时，则Y补=2+Y,Y=Y补-2=1Y1Y2Yn2=0Y1Y2Yn-1XY=X(0Y1Y2Yn)X则XY补=X补(0Y1Y2Yn)+-X补,校正法定点补码一位乘的规律,（1）乘数Y的符号位不参加运算，用X补乘上Y补的数值位。（2）若Y为负数，则对求得的积再做一次加-X补的校正。（3）结果的符号由运算结果得出。,例1X=-0.1101,Y=+0.1011,求XY=？X补=11.0011，Y补=0.1011,高位部分积低位部分积/乘数操作说明00.00001011开始部分积为0,判断乘数末位+)11.0011乘数最低位为1，+X补11.001111.100111011（丢掉）右移部分积和乘数，判末位+)11.0011乘数最低位为1，+X补10.110011.011001101（丢掉）右移部分积和乘数，+)00.0000乘数最低位为0，+011.011011.101100110（丢掉）右移部分积和乘数，计数+)11.0011乘数最低位为1，+X补10.111011.011100011（丢掉）右移部分积和乘数，计数X*Y补=11.01110001,XY=-0.10001111,例2X=-0.1101,Y=-0.1011,求XY=？,X补=11.0011，Y补=11.0101，-X补=00.1101高位部分积低位部分积/乘数操作说明00.00000101开始部分积为0,判末位+)11.0011乘数最低位为1，+X补11.001111.100110101（丢掉）右移部分积和乘数，+)00.0000乘数最低位为0，+011.100111.110011010（丢掉）右移部分积和乘数，+)11.0011乘数最低位为1，+X补10.111111.011111101（丢掉）右移部分积和乘数，+)00.0000乘数最低位为0，+011.011111.101111110（丢掉）右移部分积和乘数，,XY=11.10111111,Y为负数，对求得的积需再做一次加-X补的校正。-X补=00.1101X+Y补=11.10111111+00.1101=00.10001111所以:XY=+0.10001111,X=-0.1101,Y=-0.1011,求XY=？,比较法(Booth法)这种方法不用区分乘数符号的正负，而且让乘数符号位也参加运算。运算规则如下：（1）参加运算的数用补码表示（2）符号位参加运算（3）乘数最低一位后面增加一位附加位Y-1其初值是0（4）逐次比较相邻两位并按下表的规则运算.（5）移位按补码右移规则进行,即右移过程中符号位也随着右移并且符号位保持不变.,开始,N位被乘数B,0AN位乘数C，0C-1,C0C-1=?,A-BA,A+BA,A、C右移一位,重复n次,结束,Y,N,=01,=10,A+0A,=00或11,例：设X补=0.1101，Y补=1.0110，求XY=？,加法器和被乘数采用双符号位。-X补=11.0011高位部分积低位部分积/乘数附加位操作说明00.000010110000.0000010110YnYn+1=00,右移部分积和乘数一位+11.0011YnYn+1=10,+-X补11.001111.1001101011右移部分积和乘数一位11.1100110101YnYn+1=11,右移部分积和乘数一位+00.1101YnYn+1=01,+X补00.100100.0100111010右移部分积和乘数一位+11.0011YnYn+1=10,+-X补11.01111110最后一次不右移XY补=11.01111110,XY=-0.10000010,第四节定点除法运算,一、无符号数一位除运算和定点原码的乘法一样,两个原码数相除,通常有恢复余数法和不恢复余数法.1.无符号数恢复余数法在计算机中实现除法运算，就要解决如何判断够减与否的问题，可用2种方法：(1)设置一个比较线路，专门用来比较被除数(余数)与除数的大小。(2)直接作减法试探。,开始,被除数A、C除数B,A0，商=1。0010001A、C左移一位B1101减除数A011110010A0，不够减，商=0。B0011恢复余数，加除数。,例1用恢复余数法计算:000010000011除数0011B；被除数放到A、C中除数的补码1101,商,余数,对于小数来说，运算规则：第一次做减法即-B补，用来判别溢出的情况当某一次求商，它减得的差值为负，本次商上0，同时把除数加到差上，恢复余数为原来得正值，然后再左移。当某一次求商，减得的差值为正，就没有恢复余数的操作，上商为1，余数左移一位。注意余数一般是通过n次左移后得出的结果，那么真正的结果应该是这个数2n例题：书P-74,2.无符号数不恢复余数法当余数为正时，商上1，求下一位商的办法是余数左移一位，再减去除数；当余数为负时，商上0。求下一位商的办法是余数左移一位，再加上除数。如果最后一次上商为0，而又需得到正确余数则在这最后一次仍需恢复余数。,开始,被除数A、C除数B,A0?,A、C左移一位A+BA,重复n-1次?,结束,Y,N,A、C左移一位,ABA,Y,N,商0：0C0,商1：1C0,A、C左移一位A-BA,A0?,N,A+BA,对于整数而言,对于小数来说，运算规则：第一次做减法即-B补，用来判别溢出的情况当某一次求商，它减得的差值为负，本次商上0，然后左移，并且加上除数。当某一次求商，减得的差值为正，上商为1，余数左移一位，然后-Y补。注意余数一般是通过n次左移后得出的结果，那么真正的结果应该是这个数2n如果最后一次的余数为负，正确的余数应为Y恢复后的正余数2n。用不恢复余数除法完全可以代替恢复余数除法，且n位数除以n位数，只用做n1次加减法，n次移位就可以了，缩短了除法时间。,被除数（余数）A商C操作说明0010110000初始状态）110011+Y补11111000000不够减，商上0,1111000000左移）001101+Y00100100001够减，商上10100100001左移）110011+Y补00010100011够减，商上10010100011左移）110011+Y补11110100110不够减，商上01110100110左移）001101+Y00011101101够减，商上1,例2X=0.1011,Y=0.1101,求X/Y=？-Y补=11.0011,商,余数,X/Y=0.1101余数0.0111x2-4,需要说明的问题：对于定点小数除法，先要比较除数和被除数的绝对值的大小，用来检查是否有商溢出，所以此时第一步通常是B补。商的符号为相除二数的符号的半加和被除数的位数可以是除数的两倍，低位的数值部分开始时放在商寄存器中。然后在运算过程中，放被除数和商的寄存器同时移位，并将商寄存器中的最高位移到被除数寄存器的最低位。实现除法的逻辑电路与乘法的逻辑电路极相似，但在A寄存器中放被除数/余数，B寄存器放除数，C寄存器放商。,第四节定点除法运算,3.软件实现无符号数除法在无除法指令的机器中，可用子程序实现除法运算。二、带符号数一位除实现符号数一位除的一种方法是：将被除数和除数的绝对值按无符号数除法得到商及余数；若两数异号，商符取负，否则取正；余数符号与被除数符号相同。一般符号数用补码表示，所以我们直接用补码进行进行除法运算。补码一位除（补码不恢复余数法）为：,第四节定点除法运算,参加运算的数用补码表示，符号位参加运算首先将被除数左移一位，若被除数与除数同号，求商时用移位后的被除数高位部分减去除数；若异号，则用移位后的被除数高位部分加上除数。若余数与除数同号，上商1，下次左移一位后作余数减除数操作；若异号，上商0，下次左移一位后作余数加除数操作。商的修正。将商最末位恒置1，这样在商的末位上可能存在误差，但将商与余数当作一个整体看待则是没有误差的。商的符号。如果第一步操作不发生溢出，得到的就是正确的商符。,第五节浮点算术运算,浮点数通常可写成：M2E其中：M为该浮点数的尾数，一般为绝对值小于1的规格化二进制小数，用原码或补码表示E是该浮点数的阶码，为二进制整数，用移码或补码表示。阶的底可用2、8或16，常用2。一、浮点加减运算1.运算规则及硬件实现设有2个浮点数：X=MX2EXY=MY2EY需要5个步骤才能完成加减运算：,第五节浮点算术运算,(1)对阶操作：2个浮点数的阶码可能不同，要对齐后才能运算。对阶的规则是：阶码小的数向阶码大的数对齐。一般方法是用减法比较，即求：E=EX-EYE=0,表示两数阶码相等，不需对阶。若0，则将原来阶码小的数的尾数右移E位，并将其阶码值加上E；尾数右移时，对原码形式的尾数，符号位不参加移位，尾数最高有效位补0；对补码形式的尾数，符号位保持不变并参加右移。尾数右移后，应对移掉的最高位进行舍入，常用0舍1入法或恒置1法。,第五节浮点算术运算,(2)实现尾数的加(减)运算：完成对阶后，按定点数加减运算规则求两数的和(差)(3)结果规格化：当运算的结果不是规格化数时，需将它转变成规格化