第五讲定点运算(除法).ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第五讲,定点运算（除法）,本讲主要内容,原码一位除法,补码一位除法,并行除法器,一、分析笔算除法,x,=,0.1011,y,=0.1101,求,x,y,0.1 0 1 1,0.1 1 0 1,0.0 1 1 0 1,0.0 1 0 0 1,0.0 0 1 1 0 1,0.0 0 0 1 0 1,0.0 0 0 0 1 1 0 1,0.0 0 0 0 0 1 1 1,1,商符单独处理,心算上商,余数不动低位补“,0”,减右移一位的除数,上商位置不固定,x,y,=,0.1 1 0 1,余数,0.0 0 0 0 0 1 1 1,商符心算求得,0,0.,1,0,1,0,0,0,？,？,？,二,.,机器运算与手算的不同,(1),在计算机中,小数点是固定的,不能简单地采用手算的办法。,为便于机器操作,除数,Y,固定不变,被除数和余数进行,左移,(,相当于乘,2),手工算法的改进算法：,结果与手算相同,，,但余数不是真正的余数,，,多乘了,2,n,，,故正确的余数应为,2,-n,r,n,，即：,0.,0000,0001,00.0001,第四次余数,r,4,01.0010,被除数左移一位，,2xy,，商,1,+11.0101,减,y,，即,+-y,补,00.0111,第一次余数,r,1,00.1110,r,1,左移一位，,2r,1,y,，商,1,+11.0101,减,y,00.0011,第二次余数,r,2,00.0110,r,2,左移一位，,2r,2,y,，商,1,+11.0101,减,y,00.1011,00.1001 xy,，商,0,00.,1,1,0,1,x=0.1001,y=0.1011,，,-y,补,=1.0101,(2),机器不会心算,必须先作减法,若余数为正,才知道够减；若 余数为负,才知道不够减。不够减时必须恢复原来的余数,以便再继续往下运算。这种方法称为,恢复余数法,。,要恢复原来的余数,只要当前的余数加上除数即可。,但由于 恢复余数,使除法进行过程的步数不固定,因此控,制比较 复杂。,实际中常用,不恢复余数法,又称,加减交替法,。其特点是,运算过程中如出现不够减,则不必恢复余数,根据余数符号,可以继续往下运算,因此步数固定,控制简单。,机器运算与手算的不同,笔算除法和机器除法的比较总结,笔算除法,机器除法,商符单独处理,心算上商,符号位异或形成,|,x,|,|,y,|,0,上商,1,|,x,|,|,y,|,0,上商,0,余数,不动,低位补“,0”,减右移一位,的除数,2,倍字长加法器,上商位置,不固定,余数,左移一位,低位补“,0”,减,除数,1,倍字长加法器,在寄存器,最末位上商,三,.,原码除法,以小数为例,x,原,=,x,0,.,x,1,x,2,x,n,y,原,=,y,0,.,y,1,y,2,y,n,式中,x,*,=0,.,x,1,x,2,x,n,为,x,的绝对值,y,*,=0,.,y,1,y,2,y,n,为,y,的绝对值,数值部分为绝对值相除,x,*,y,*,被除数不等于,0,除数不能为,0,小数定点除法,x,*,y,*,整数定点除法,x,*,y,*,商的符号位单独处理,x,0,y,0,原,=(,x,0,y,0,).,x,y,x,*,y,*,约定,被除数减除数，够减时，商,1,；不够减时商,0,。,由于商时若不够减，即不能作减法，但现在在判断是否商时，已经减了除数，为了下次能正确运算，必须把已减掉的除数加回去恢复余数。这就是,“,恢复余数法,”,。,(1),恢复余数法,0.1 0 1 1,1.0 0 1 1,1.0 0 1 1,1.0 0 1 1,0.0 0 0 0,+,y,*,补,0,1.1 1 1 0,余数为负，上商,0,0.1 1 0 1,恢复余数,0,0.1 0 0 1,余数为正，上商,1,+,y,*,补,1.0 1 1 0,0,1,1.0 0 1 0,0 1,1,+,y,*,补,解：,被除数（余数）商 说 明,x,原,=1.1011 ,y,原,=1.1101,x,0,y,0,=1,1=0,x,=,0.1011,y,=0.1101,求,原,x,y,例,24,1,0.1 0 1 1,恢复后的余数,0,+,y,*,补,y,*,补,=0.1101 ,y,*,补,=1.0011,逻辑左移,逻辑左移,+,+,+,+,0.0 1 0 1,0 1,余数为正，上商,1,被除数（余数）商 说 明,1.0 0 1 1,0.1 1 0 1,1.0 0 1 1,1,0.1 0 1 0,0 1 1,+,y,*,补,1.1 1 0 1,0 1 1,余数为负，上商,0,恢复余数,1.0 1 0 0,0 1 1 0,1,+,y,*,补,0.0 1 1 1,0 1 1 0,余数为正，上商,1,=0.1101,x,*,y,*,原,x,y,=0.1101,上商,5,次,第一次上商判溢出,余数为正 上商,1,余数为负 上商,0,，恢复余数,移,4,次,1,0,0.1 0 1 0,恢复后的余数,0 1 1,0,1,+,y,*,补,逻辑左移,逻辑左移,+,+,+,【,例,】x=0.1001,y=0.1011,用恢复余数法求,x/y,.,解：,x,原,=x*,补,=x=,.1001,y*,补,=0.1011,-y*,补,=1.0101,0 0.1 0 0 1,+-y*,补,1 1.0 1 0 1 x,减,y*,1 1.1 1 1 0,余数,r,0,0,，商“,1”,0 0.1 1 1 0 0.1,商,1,移入,q,，,r,1,左移,+-y*,补,1 1.0 1 0 1,减,y*,0 0.0 0 1 1 r,2,0,，商“,1”,0 0.0 1 1 0 0.1 1,商,1,移入,q,，,r,2,左移,+-y*,补,1 1.0 1 0 1,减,y*,1 1.1 0 1 1 r,3,0,，商“,1”,0 0.0 0 0 1 0.1 1 0 1,商,1,移入,q,，,r,4,不左移,被除数,x/,余数,r,商,q,说明,x,原,=,.1001,y*,补,=0.1011,-y*,补,=1.0101,余数每次左移相当于乘以,2,，在求得,n,位商后，相当于多乘了,2,n,，所以最后余数应乘以,2,n,才是正确的值。,故：,q,原,=0.1 1 0 1,余数,r,4,原,=0.,0000,0001,(2),不恢复余数法,余数,R,i,0,上商“,1”,，,2,R,i,y,*,余数,R,i,0,上商“,0”,，,R,i,+,y,*,恢复余数,2(,R,i,+,y,*,),y,*=,2,R,i,+,y,*,加减交替,恢复余数法运算规则,不恢复余数法运算规则,上商“,1”2,R,i,y,*,上商“,0”2,R,i,+,y,*,（加减交替法）,x,=,0.1011,y,=0.1101,求,原,x,y,解：,例,25,0.1 0 1 1,1.0 0 1 1,0.1 1 0 1,1.0 0 1 1,1.0 0 1 1,0.1 1 0 1,0.0 0 0 0,+,y,*,补,0,1.1 1 1 0,余数为负，上商,0,1.1 1 0 0,0,1,+,y,*,补,0,0.1 0 0 1,余数为正，上商,1,+,y,*,补,1.0 0 1 0,0 1,1,+,y,*,补,+,y,*,补,0.1 0 1 0,0 1 1,1,1.1 0 1 0,0 1 1 0,1,0.0 1 0 1,0 1,余数为正，上商,1,0.0 1 1 1,0 1 1 0,余数为正，上商,1,1.1 1 0 1,0 1 1,余数为负，上商,0,x,原,=1.1011,y,*,补,=0.1101,y,*,补,=1.0011,y,原,=1.1101,1,1,0,1,逻辑左移,x,*,补,=0.1011,逻辑左移,逻辑左移,逻辑左移,x,0,y,0,=1,1=0,x,*,y,*,=0.1101,=0.1101,原,x,y,上商,n,+1,次,例,25,结果,特点,用移位的次数判断除法是否结束,第一次上商判溢出,移,n,次,，,加,n,+1,次,例,x=0.1001,y=0.1011,用恢复余数法求,x/y,.,解：,x,原,=x*,补,=x=,.1001,y*,补,=0.1011,-y*,补,=1.0101,0 0.1 0 0 1,+-y,补,1 1.0 1 0 1 x,减,y,1 1.1 1 1 0,余数,r,0,0,，商“,1”,0 0.1 1 1 0 0.1,商,1,移入,q,，,r,1,左移,+-y,补,1 1.0 1 0 1,减,y,0 0.0 0 1 1 r,2,0,，商“,1”,0 0.0 1 1 0 0.1 1,商,1,移入,q,，,r,2,左移,+-y,补,1 1.0 1 0 1,减,y,1 1.1 0 1 1 r,3,0,，商“,1”,0 0.0 0 0 1 0.1 1 0 1,商,1,移入,q,，,r,4,不左移,被除数,x/,余数,r,商,q,说明,x,原,=,.1001,y,补,=0.1011,-y,补,=1.0101,余数每次左移相当于乘以,2,，在求得,n,位商后，相当,于多乘了,2,n,，所以最后余数应乘以,2,n,才是正确的值。,故：,q,原,=0.1 1 0 1,余数,r,4,原,=0.,0000,0001,(3),原码加减交替除法硬件配置,A,、,X,、,Q,均,n,+1,位,用,Q,n,控制加减交替,0,A,n,n,+1,位加法器,控 制 门,0,X,n,0,Q,n,计数器,C,G,D,加,减,移位和加控制逻辑,S,V,左移,R,i,补,=0.1000,x,补,=1.1101,y,补,=1.0101,四,.,补码除法（加减交替法）,(1),商值的确定,x,=0.1011,y,=0.0011,x,补,=0.1011,y,补,=0.0011,x,补,=0.1011,y,补,=1.1101,R,i,补,=0.1000,x,=,0.0011,y,=,0.1011,x,补,=1.1101,y,补,=0.1011,x,*,y,*,R,i,补,与,y,补,同号,“够减”,x,*,y,*,R,i,补,与,y,补,异号,“不够减”,+,+,比较被除数和除数绝对值的大小,x,与,y,同号,小结,x,=0.1011,y,=,0.0011,x,补,=0.1011,y,补,=1.1101,x,补,=0.1011,y,补,=1.1101,R,i,补,=0.1000,x,=,0.0011,y,=0.1011,x,补,=1.1101,y,补,=0.1011,x,补,=1.1101,y,补,=0.1011,R,i,补,=0.1000,x,*,y,*,R,i,补,与,y,补,异号,“够减”,x,*,y,*,R,i,补,与,y,补,同号,“不够减”,+,+,x,与,y,异号,x,补,和,y,补,求,R,i,补,R,i,补,与,y,补,同号,异号,x,补,y,补,x,补,+,y,补,同号，“够减”,异号，“够减”,商值的确定,x,补,与,y,补,同号,正,商,按原码上商,“够减”上“,1”,“不够减”上“,0”,x,补,与,y,补,异号,负,商,按反码上商,“够减”上“,0”,“不够减”上“,1”,原码,0,.,1,反码,1,.,1,末位恒置“,1”,法,小 结,简 化 为,（同号）,（异号）,（异号）,（同号）,.,1,x,补,与,y,补,商,R,i,补,与,y,补,商 值,够减,不够减,够减,不够减,同 号,异 号,正,负,1,0,0,1,原码上商,反码上商,R,i,补,与,y,补,商值,同 号,异 号,1,0,(2),商符的形成,除法过程中自然形成,x,补,和,y,补,同号,x,补,y,补,比较,R,i,补,和,y,补,同号,(,够,)“1”,异号,(,不够,)“0”,原码上商,小数除法 第一次“不够”上,“,0”,正商,x,补,和,y,补,异号,x,补,+,y,补,比较,R,i,补,和,y,补,异号,(,够,)“0”,同号,(,不够,)“1”,反码上商,小数除法 第一次“不够”上,“,1”,负商,(3),新余数的形成,加减交替,R,i,补,和,y,补,商,新余数,同 号,异 号,1,0,2,R,i,补,+,y,补,2,R,i,补,+,y,补,补码一位除法的算法是在商的末位,“,恒置,1,”,的舍入条件下推导的，故此算法存在误差，这样引起的最大误差是,2,-n,。在对计算精度没有特殊要求的情况下，一般就采用商的末位,“,恒置,1,”,的办法，这样操作比较简单，而且易于实现。,如果需要进一步提高商的精度，可按上述方法多求一位，再用以下方法进行校正：,(1),刚好能除尽时，若除数为正，商不必校正；,若除数为负，则商加,2,-n,。,(4),.,商的校正,(2),不能除尽时，若商为正，则不必校正；,若商为负，则商加,2,-n,。,例,26,设,x,=,0.1011,y,=0.1101,求 并还原成真值,补,x,y,解：,x,补,=1.0101 ,y,补,=0.1101 ,y,补,=1.0011,1.0 1 0 1,0.1 1 0 1,1.0 0 1 1,0.1 1 0 1,0.1 1 0 1,0.0 0 0 0,异号做加法,1,0.0 0 1 0,同号上“,1”,1.0 1 1 1,1,异号上“,0”,+,y,补,1.1 0 1 1,1 0,异号上“,0”,+,y,补,0.0 0 1 1,1 0 0,同号上“,1”,0.0 1 0 0,1,1,0.1 1 1 0,1 0,1,1.0 1 1 0,1 0 0,1,末位恒置“,1”,0.0 1 1 0,1 0 0 1,1,补,=,1.0011,x,y,0,0,1,1,+,y,补,x,y,=,0.1101,则,逻辑左移,逻辑左移,逻辑左移,逻辑左移,(5),小结,补码除法共上商,n,+1,次（末位恒置,1,）,第一次为商符,第一次商可判断溢出,加,n,次 移,n,次,用移位的次数判断除法是否结束,精度误差最大为,2,-,n,(6),补码除和原码除（加减交替法）比较,x,0,y,0,自然形成,绝对值补码,补码,余数的正负,比较余数和除数的符号,n+,1,n+,1,原码除,补码除,商符,操作数,上商原则,上商次数,加法次数,移位次数,第一步操作,移位,x*,补,y*,补,n,逻辑左移,n,n,+1,逻辑左移,n,同号,x,补,y,补,异号,x,补,y,补,