原码补码乘除法

1、原码一位乘运算以定点小数为例,0. 1 1 0 1 0. 1 0 1 1 0. 0 0 0 0 1 1 0 1 0. 0 0 0 1 1 0 1 0. 0 0 0 0 0 0 +0. 0 1 1 0 1 0 . 1 0 0 0 1 1 1 1,返回,例如： X = 0.1101 Y = - 0.1011,笔算乘法过程,机器实现问题： 1. 加法器只有两个数据输入端； 2. 加法器与运算数据位数相同。 解决方案： 1. 改n输入数相加过程为两两相加； 2. 改2n位相加过程为n位相加。,X Y = - 0.10001111,原码一位乘运算,返回,基本公式： 设 被乘数 X原 = xf . x1

2、x2 x n 乘 数 Y原 = yf . y1 y2 y n 则 X Y原 =( xf yf ). ( X* Y* ) 其中， X* 和Y*分别是X和Y的绝对值,例如： X = 0.1101 Y = - 0.1011 X原= 0.1101 Y原 = 1.1011 X* = 0.1101 Y* = 0.1011 0. 1 1 0 1 . 累加器初值取零值 0. 1 0 1 1 + . 1 1 0 1 . 初值加被乘数 1 1 0 1 . 部分积右移， 0 0 0 0 将移出的一位保存起来 + 1 1 0 1 求第一次部分积 0 . 1 0 0 0 1 1 1 1 手工运算过程,原码一位乘运算,原

3、码一位乘运算,X* = 0.1101 Y* = 0.1011 0. 1 1 0 1 . 1 0. 1 0 1 1 + . 1 1 0 1 . 前次部分积加被乘数 1 1 0 1 . 部分积右移 0 0 0 0将移出的一位保存起来 + 1 1 0 1 求第二次部分积 0 . 1 0 0 0 1 1 1 1 手工运算过程,返回,原码一位乘运算,X* = 0.1101 Y* = 0.1011 0. 1 1 0 1 . 1 1 0. 1 0 1 1 + . 1 1 0 1 . 前次部分积加 1 1 0 1 .部分积右移 0 0 0 0将移出的一位保存起来 + 1 1 0 1 求第三次部分积 0 . 1

4、 0 0 0 1 1 1 1 手工运算过程,返回,原码一位乘运算,X* = 0.1101 Y* = 0.1011 0. 1 1 0 1 . * 0. 1 0 1 1 + . 1 1 0 1 .前次部分积加被乘数 1 1 0 1 .部分积右移 0 0 0 0将移出的一位保存起来 + 1 1 0 1 求第四次部分积 0 . 1 0 0 0 1 1 1 1 手工运算过程,再用一步完成两数符号异或求积的符号, 结果为 -0.10001111,返回,原码一位乘运算规则,原码一位乘运算规则： 1. 乘积的符号位由两数符号位“异或”产生，符号 位不参与运算； 2. 部分积可采用一位或两位符号位； 3. 乘积

5、的数值部分由两数绝对值相乘产生，通过n 次“加法”和“右移”操作实现。(n为乘数整数部分位数),返回,原码一位乘运算实例,部分积 乘数 0. 0 0 0 0 0.1 0 1 1 + 0. 1 1 0 1 0. 1 1 0 1 0. 0 1 1 0 1 0 1 0 1 + 0. 1 1 0 1 1. 0 0 1 1 0. 1 0 0 1 1 1 0 1 0 0. 0 1 0 0 1 1 1 0 1 + 0. 1 1 0 1 1. 0 0 0 1 0. 1 0 0 0 1 1 1 1 0,返回,0. 1 1 0 1 0. 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 + 1 1

6、0 1 0 . 1 0 0 0 1 1 1 1,例如： X = 0.1101 Y = - 0.1011,手工运算过程,计算机内运算的实现方法,则 X* = 0.1101 Y* = 0.1011,X原 = 0.1101 Y原 = 1.1011,X Y原 = 1.10001111,补码乘法运算,原码乘法不难实现，但有两个问题: 1. 符号位与数值位分别处理，不方便； 2. 若数据为补码形式，可能需要多于两次 补原码变换。 也可以直接用补码完成乘法运算，即从补码开始，直接得到补码的积。 下面看一看补码乘运算的实现算法。,返回,= (Yi+1 - Yi ) 2-i,设 被乘数 X补 = x0. x1

7、x2 x n 乘 数 Y补 = y0. y1 y2 y n 先复习两个概念: 已知 X补 = x0. x1x2 x n 时 X/2补 = x0. x0 x1 x2 xn-1 已知 Y补 = y0. y1 y2 yn 时 Y = - y0 yi 2-i,补码一位乘法的实现算法推导(比较法),返回,X Y = X - y0 yi 2-i ,补码一位乘法运算算法推导(比较法),返回,= X (0 .y1 y2 yn) - X y0 X Y补 = X (0 .y1 y2 yn) - X y0 补 = X (0 .y1 y2 yn) 补- X y0 补 = X 补 (0 .y1 y2 yn) - y0

8、X补 = X 补 Y,证明 X (0 .y1 y2 yn) 补 = X 补 (0 .y1 y2 yn),(1) 当X 0 时， X (0 .y1 y2 yn) 补 = X (0 .y1 y2 yn) = X 补 (0 .y1 y2 yn),(2) 当X 0 时， X (0 .y1 y2 yn) 补 = 2+ X (0 .y1 y2 yn) (mod 2) = 2n+1+ X (0 .y1 y2 yn) (mod 2) = 2n+1 (0 .y1 y2 yn) + X (0 .y1 y2 yn) (mod 2) = (2n+1+ X) (0 .y1 y2 yn) (mod 2) = (2+ X)

9、 (0 .y1 y2 yn) (mod 2) = X 补 (0 .y1 y2 yn) (mod 2),= -y0*20 + (y1*20-y1*2-1) + (y2*2-1 -y2*2-2) + +,补码一位乘法运算算法推导(比较法),= (yi+1 - yi ) * 2-i,X Y补补 ,返回,= -y0*20 + y1*2-1 + y2*2-2 + + y n*2-n,= (y1-y0)*20 + (y2-y1)*2-1 + + (yn+1-yn)*2-n,最低1位后再补1位,令 yn+1 = 0,补码一位乘法运算的实现(比较法),补码一位乘公式： Z 补= X Y补 = 补（- y0 y

10、i 2-i ）,返回,= 补 (yi+1 - yi ) 2-i,部分积递推公式： Z0补= 0 Z1补= 2-1 Z0补+ (yn+1 - yn) 补 (令 yn+1 = 0) Zi补= 2-1 Zi-1补+ (yn-i+2 - yn-i+1) 补 Zn补= 2-1 Zn-1补+ (y2 - y1) 补 Zn+1补= Zn补+ (y1 - y0) 补 = X Y补,补码一位乘法运算的算法规则(比较法),yn yn+1= 00 时， Zi补= Zi-1补+ 0， 右移1位; yn yn+1= 01 时， Zi补= Zi-1补+ X补， 右移1位； yn yn+1= 10 时， Zi补= Zi-1

11、补+ -X补，右移1位； yn yn+1= 11 时， Zi补= Zi-1补+ 0， 右移1位；,补码一位乘算法规则：,X、Y的符号位都参加运算，部分积采用双符号位； 2. 乘数最低位之后增加一位附加位yn+1 ，且令yn+1=0； 3. 每位部分积运算规则如下：,4. 重复n+1次比较和运算，但只进行n次右移，最后一 次不移位。 积符由运算过程自动产生。,补码一位乘法运算实例,已知: X补 = 0.1101 Y补 = 0.1011,部分积 乘数 yn yn+1 0 0. 0 0 0 0 0.1 0 1 1 0 +1 1. 0 0 1 1 1 1. 0 0 1 1 1 1. 1 0 0 1 1

12、 0 1 0 1 1 1 1. 1 1 0 0 1 1 0 1 0 1 +0 0. 1 1 0 1 0 0. 1 0 0 1 0 0. 0 1 0 0 1 1 1 0 1 0 +1 1. 0 0 1 1 1 1. 0 1 1 1 1 1. 1 0 1 1 1 1 1 1 0 1 +0 0. 1 1 0 1 0 0. 1 0 0 0 1 1 1 1 0 清0,则 -X补 = 1.0011,X Y补 = 0.10001111,补码一位乘硬件配置及实例演示（比较法）,补码一位乘综合演示.swf,设 被乘数 X补 = x0 .x1 x2 x n 乘 数 Y补 = y0 .y1 y2 y n,补码两位乘

13、法的实现算法推导(比较法),返回,由一位乘算法得：,Zi+2补= 2-12-1 Zi补+ (yn-i+1 - yn-i) 补+ (yn-i - yn-i-1) 补,= 2-2 Zi补+ (yn-i+1 + yn-i - 2 yn-i-1) 补,结论： 补码两位乘比较法的部分积运算由乘数相邻的三位比较决定，运算后每次右移两位。,Zi+1补= 2-1 Zi补+ (yn-i+1 - yn-i) 补,补码两位乘法运算的算法规则(比较法),yn-1 yn yn+1= 000 时， Zi+2补= Zi补+ 0， 右移2位; yn-1 yn yn+1= 001 时， Zi +2补= Zi补+ X补， 右移2

14、位; yn-1 yn yn+1= 010 时， Zi +2补= Zi补+ X补， 右移2位; yn-1 yn yn+1= 011 时， Zi +2补= Zi补+ 2X补， 右移2位; yn-1 yn yn+1= 100 时， Zi +2补= Zi补+ 2-X补，右移2位; yn-1 yn yn+1= 101 时， Zi +2补= Zi补+ -X补， 右移2位; yn-1 yn yn+1= 110 时， Zi +2补= Zi补+ -X补， 右移2位; yn-1 yn yn+1= 111 时， Zi +2补= Zi补+ 0， 右移2位;,X、Y的符号位都参加运算，部分积采用三位符号位； 乘数最低位

15、之后增加一位附加位yn+1 ，且令yn+1=0； 每位部分积运算规则如下：,补码两位乘法运算的算法规则(续)(比较法),4. 设乘数数值部分为n位， 当n为奇数时，乘数设1位符号位，做(n+1)/2次运算和移位，最后一步右移1位； 当n为偶数时，乘数设2位符号位，做n/2+1次运算和移位，最后一步不右移； 积符由运算过程自动产生。,补码两位乘法运算实例,已知: X补 = 0.1101 Y补 = 0.1011,部分积 乘数 yn yn+1 0 0. 0 0 0 0 0 1 0 1 1 0 +1 1. 0 0 1 1 1 1. 0 0 1 1 1 1. 1 0 0 1 1 0 1 0 1 1 1

16、1. 1 1 0 0 1 1 0 1 0 1 +0 0. 1 1 0 1 0 0. 1 0 0 1 0 0. 0 1 0 0 1 1 1 0 1 0 +1 1. 0 0 1 1 1 1. 0 1 1 1 1 1. 1 0 1 1 1 1 1 1 0 1 +0 0. 1 1 0 1 0 0. 1 0 0 0 1 1 1 1 0 清0,1,1,1,部分积 乘 数 yn yn+1 0 0 0. 0 0 0 0 0 0.1 0 1 1 0 +1 1 1. 0 0 1 1 1 1 1. 0 0 1 1 1 1 1. 1 1 0 0 1 1 0 0 1 0 1 +1 1 1. 0 0 1 1 1 1 0.

17、 1 1 1 1 1 1 1. 1 0 1 1 1 1 1 1 0 0 1 +0 0 0. 1 1 0 1 0 0 0. 1 0 0 0 1 1 1 1 0 0 清0,2,1,2,则 -X补 = 1.0011,X Y补 = 0.10001111,原 码 除 法以定点小数为例,例如： X = 0.1011 Y = - 0.1101 笔算除法过程 0.1101 0.1101 0.10110 -0.01101 0.010010 -0.001101 0.00010100 -0.00001101 0.00000111,原码除运算方法分析以定点小数为例,返回,机器实现问题： 1. 需单独设计比较器线路；

18、2. 需2n位的减法器线路。,解决方案： 1. 比较操作改由“试减”实现； 2. 将除数右移改为部分余数左移； 3. 减法由+-Y补转化为加法实现。,被除数（余数） 商 说 明 0 0. 1 0 1 1 0. 0 0 0 0 + 1 1. 0 0 1 1 + -Y *补 （减除数） 1 1. 1 1 1 0 余数 0, 商上1 0 1. 0 0 1 0 0 0 0 0 1 左移一位 + 1 1. 0 0 1 1 + -Y *补 0 0. 0 1 0 1 余数 0, 商上1 0 0. 1 0 1 0 0 0 0 1 1 左移一位 + 1 1. 0 0 1 1 + -Y *补 1 1. 1 1 0

19、 1 余数 0, 商上1,例如： X = -0.1011 Y = - 0.1101 X原= 1.1011 Y原= 1.1101 X* = 0.1011 Y* = 0.1101 -Y*补 = 1.0011,恢 复 余数 除 法,X/Y原=0.1101 R原=0.01112-4,原码加减交替除法原理证明,1. 若第 i - 1次求商，余数为 R i-1 0 ， 本次商上1，且余数左移 1 位得 2R i-1 ； 2. 第 i 次求商，余数为 R i =2R i-1 Y*, 若R i 0,则商上1，跳至3； 若R i 0, 则商0，恢复余数为正且左移得 2(R i + Y*)，跳至4； 3. 第 i

20、 + 1次求商，余数为 R i+1 = 2 R i Y* 4. 第 i + 1次求商，余数为 R i+1 = 2( R i + Y* ) Y* = 2R i + Y* 实质: 对上次的负余数值直接左移一位, 本次用+Y*求商即可。,返回,原码加减交替除法算法规则,1.除法运算前，应满足条件：X*Y*,且Y*0,否则，按溢出或非法除数处理； 2.符号位不参与运算，单独处理：qf= xf yf ; 3.部分余数采用单符号位或双符号位； 4.每步部分余数运算规则：,试减 X* +-Y *补,余数为正，商上1，余数和商左移一位，减除数；,余数为负，商上0，余数和商左移一位，加除数；,5.第n+1步：若

21、余数为正，商上1，商左移一位； 若余数为负，商上0，商左移一位，但当结果需 要余数时，需恢复余数，R = R n 2-n 。,重复n步,被除数（余数） 商 说 明 0 0. 1 0 1 1 0. 0 0 0 0 + 1 1. 0 0 1 1 + -Y *补 (减除数) 1 1. 1 0 1 1 余数 0, 商上1 0 1. 0 0 1 0 0 0 0 0 1 左移一位 + 1 1. 0 0 1 1 + -Y *补 0 0. 0 1 0 1 余数 0, 商上1 0 0. 1 0 1 0 0 0 0 1 1 左移一位 + 1 1. 0 0 1 1 + -Y *补 1 1. 1 1 0 1 余数 0

22、, 商上1 0 1 1 0 1 商左移一位,例如： X = -0.1011 Y = - 0.1101 X原= 1.1011 Y原= 1.1101 X* = 0.1011 Y* = 0.1101 -Y*补 = 1.0011,加减交替 除 法,X/Y原= 0.1101 R = 0.0111 2-4,原码加减交替除法运算过程演示,原码加减交替除法控制流程及实例.swf,原码加减交替除法运算的基本硬件配置,0 A n,加法器(n+1位),控 制 门,GD,计数器C,V,0 X n,补码除法运算,算法思想： 被除数与除数为补码表示， 直接用补码除，求出反码商， 再修正为近似的补码商。,返回,主要解决：

23、上值的确定； 求商符； 获得新余数； 商的校正。,补码除法算法分析,(1) 商和新余数的确定 上商的过程实际上时比较被除数（余数）和除数所对应绝对值大小的过程。 若X与Y同号：做减法，即 R0补 =X补 +-Y补 够减：R0 与Y 同号，商上1，左移一位，减除数。 即 R1补 =2R0补 +-Y补 。 不够减：R0 与Y 异号，商上0，左移一位，加除数。 即 R1补 =2R0补 +Y补 。,补码除法算法分析（续1）,若X与Y异号：做加法，即 R0补 =X补 +Y补 够减：R0 与Y异号，商上0，左移一位，加除数。 即 R1补 = 2R0补 +Y补 。 不够减：R0 与Y同号，商上1，左移一位，

24、减除数。 即 R1补 = 2R0补 +-Y补 。,同样的分析方法，可以得出如下结论： Ri 与Y同号，商上1， Ri+1补 = 2Ri补 +-Y补 ; Ri 与Y异号，商上0， Ri+1补 = 2Ri补 +Y补 。,补码除法算法分析（续2）,(2) 求商符 由于运算前，满足 0 X Y 所以第一次试减后的上商结果为： 若X与Y同号：不够减，即R0 与Y异号，商上0 ； 若X与Y异号：不够减，即R0 与Y同号，商上1 。 因此，商符由第一次试减后自动形成，且与商的数值位上商规则相同。,补码除法算法分析（续3）,(3) 商的校正 从前面的分析知：当商为负时，算法以反码形式上商，而按补码运算要求，应

25、得商的补码，两者之间相差2-n。为了最终得到补码商，通常采用商末位“恒置1”的舍入方法进行处理。采用这种方法产生的误差为： 2-n。这种方法简单，便于实现，运算后不需要对商校正。,补码加减交替除法算法规则,1.除法运算前，应满足条件：X*Y*,且Y*0,否则，按溢出或非法除数处理； 2.符号位参与运算，商符由运算自动产生; 3.部分余数采用单符号位或双符号位； 4.每步部分余数运算规则：,试减：,X、Y同号，做减法；,X、Y同号，做加法；,5.第n+1步：商恒置1，商左移一位。,重复n步,上商：,余数与Y同号，商上1，余数和商左移一位，做减法；,余数与Y异号，商上0，余数和商左移一位，做加法；

26、,若要求求余数：,若余数与Y同号，除法结束。 若余数与Y异号，应恢复余数，方法同上。,R = R n 2-n,被除数（余数） 商 说 明 1 1. 0 1 1 1 0. 0 0 0 0 X与Y异号 + 0 0. 1 1 0 1 +Y补 0 0. 0 1 0 0 余数与Y同号, 商上1 0 0. 1 0 0 0 0 0 0 0 1 左移一位 + 1 1. 0 0 1 1 +-Y补 1 1. 1 0 1 1 余数与Y异号, 商上0 1 1. 0 1 1 0 0 0 0 1 0 左移一位 + 0 0. 1 1 0 1 + Y补 0 0. 0 0 1 1 余数与Y同号, 商上1 0 0. 1 0 1

27、0 0 0 1 0 1 左移一位 + 1 1. 0 0 1 1 + -Y补 1 1. 1 0 0 1 余数与Y异号, 商上0 1 1. 0 0 1 0 0 1 0 1 0 左移一位 1.0 1 0 1 商末位恒置1, 商左移一位,例如： X = -0.1001 Y = +0.1101 X补 = 1.0111 Y补= 0.1101 -Y补 = 1.0011,补码加减交替除法,X/Y补= 1.0101 R补= 1.00102-4,补码加减交替除法运算过程演示,补码加减交替除法控制流程及实例.swf,三、快速乘除法运算,已经讲过的原码或补码一位乘除法运算，采用的是逐位循环迭代算法，完成时间直接取决于数据的位数，当位数较多时，用时较长。 提高乘除法运算速度的出路之一， 是每次完成多位运算，用的较多的是双位乘法， 跳零跳一除法，更快的乘法则可以采用阵列乘法器，可以用阵列除法器实现快速除法运算。 快速乘除法运算不作为计算机组成原理课的基本要求， 同学们