DJ10第3章-算术逻辑运算基础.ppt

3.3.3 定点乘法运算 2、补码一位乘法 (1) 算法分析 X补 = X0. X1 X2 Xn Y为正: Y补 = 0. Y1 Y2 Yn (XY)补 = X补(0. Y1Y2Yn) Y为负: Y补 = 1. Y1 Y2 Yn (XY)补 = X补(0. Y1Y2Yn)+(X)补 证明(2): 对于定点小数, Y补= 2 +Y=1.Y1 Y2 Yn 则 Y = Y补 2 = (1 + 0. Y1 Y2 Yn) 2 = 0. Y1 Y2 Yn 1 所以: XY= X (0. Y1 Y2 Yn1) = X (0. Y1 Y2 Yn) X 则: XY补 = X (0. Y1 Y2 Yn) X补 = X (0. Y1 Y2 Yn)补+X补 = X 补 (0. Y1 Y2 Yn)补+X补 因为: 0. Y1 Y2 Yn 0 所以: XY补 = X 补 (0. Y1 Y2 Yn) +X补 将和 结合起来, 有如下的式: Y符号任意: (XY)补 = X补(0. Y1Y2Yn)+(X)补Y0 符号位 展开为部分积的累加和形式: = X补(0.Y1Y2 .Yn) X补Y0 = X补(Y0+21 Y1 + 22 Y2 + . 2n Yn ) = X补(Y1 Y0)+21(Y2 Y1)+22(Y3 Y2) + +2n(0Yn) (XY)补 = X补(0. Y1Y2 .Yn)+(X)补Y0 = X补Y0 +(Y121 Y1 + 21 Y2 22Y2) + + +(2(n1) Yn 2n Yn)+0 (XY)补 = X补(Y1 Y0)+21(Y2 Y1)+22(Y3 Y2) + . + 2n(Yn+1 Yn) 在机器实现实现 中可在末位Yn之后再增设一个附加位Yn+1， 其初始值为0，对乘数Y的值并无影响。 若定义A0补为初始部分积， A1补 An补依次为各步求 得的累加和并且右移后的部分积，则可将上式改写为如下递推 形式，它更接近于乘法的分步运算形式。 A0补0 A1补21A0补+(Yn+1 - Yn) X补 A2补21A1补+(Yn Yn-1) X补 An补21An-1补+(Y2 Y1) X补 XY补 An补+(Y1 Y0) X补 上式表明补码一位乘的基本操作：被乘数X补乘以对应的相 邻两位乘数之差值，再与原部分积累加，然后右移一位，形成 该步的部分积累加和。 比较法: 用乘数的相邻两位比较(低位减高位)的结果决定部分积: 当 Yi+1 Yi = 1 +X补 当 Yi+1 Yi = 1 X补 当 Yi+1 Yi = 0 + 0 (2) 比较法算法 (3) 运算实例 X= 0.1101, Y= 0.1011, 求(XY)补。 初值: A=00.0000, B=X补=11.0011, B=(X)补=00.1101, C =Y补=1.0101 0 0 0 1 1 0 1 1 1/2A补 加0右移 1/2(A补+X补) 加X补右移 1/2(A补X补) 减X补右移 1/2A补 加0右移 Yn(高位) Yn+1(低位) 操作(A补为部分积累加和) (0) (1) (1) (0) 步数 条件 操作 A C CnCn+1 00.0000 1)1 0B+ 00.1101 00.1101 00.011011.0101 2)0 1+B+ 11.0011 11.1001 11.1100111.010 3)1 0B+ 00.1101 00.1001 00.01001111.01 4)0 1+B+ 11.0011 CnCn+1 1.0101 0 (XY)补 = 0.10001111 4)0 1+B+ 11.0011 11.0111 11.101111111.0 5)1 0 B+ 00.1101 00.10001111修正 不再移位 (4) 运算规则 A、B取双符号位, 符号参加运算; C取单符号位, 符号参加移位, 以决定最后是否修 正; C末位设置附加位Cn+1, 初值为0, CnCn+1组成判 断位, 决定运算操作; 作n步循环, 若需作第n+1步, 则不移位, 仅修正。 因为算法: (XY)补 = X补(Y1 Y0)+2 1 (Y2 Y1) . An补+(Y1 Y0) X补 即, 第n+1次是(Y1与Y0)的比较, 该项没有权值, 不需要移位。 当Y1 =Y0时, 无需与X补相乘。 因此, 在第n步完成后, 如果Y1 =Y0, 不需要作第 n+1步。当Y1 Y0, 作+B或B, 即修正, 但不移 位。即有: 1.0 : B修正 0.1 : +B修正 0.0 : 不修正 1.1 : 不修正 乘法运算学习思路三个步骤 (1) 从运算的定义和性质推导出由计算机实现 的算法; (2) 由实例演示和验证该算法; (3) 归纳总结计算机实现该算法的规则; 3.3.4 定点除法运算 除法的步骤: 余数与除数加减、移位。 例. 0.101100.11111 0.1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0.11111 0 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 0 1 10 0.10 1 1 0 0. 0 0 0 0 0 商: 0.10110 余数: 0.1011025 实现除法的关键: 比较余数、除数绝对值大小; 决定如何上商。 可以推演出以下三种可由机器实现方法: 比较法 比较余数与除数的大小, 够减则做减法, 并 商1; 不够减则不做减法, 并商0。 不恢复余数法 先做减法再判断, 不够减时, 通过下一步的加 除数来恢复余数。 恢复余数法 先做减法再判断是否够减, 够减商1; 不够减 商0, 并加除数以恢复做减法前的余数(相当 与取消这一步的减法操作)。 1、原码恢复余数法 2余数 除数 为正: 够减, 商1 为负: 不够减, 商0, 恢复原余数 (2) 实例 (假设 X/Y且 | X | | Y | ) X= 0.10110, Y=0.11111, 求X/Y, 给出商Q和余数R。 设置 A: 被除数、余数, B: 除数, C: 商 初值: A= | X |= 00.10110 B= | Y | = 00.11111 C= | Q | = 0.00000 B= 11.00001 比较两数大小可用减法试探 (1) 算法 (=新余数) 步数 条件 操作 A C 00.10110 0.00000 1) 0 B 01.01100 +11.00001 00.011010.00001 2) 1 B 00.11010 +11.00001 11.11011 0.00010 3) 恢复余数 +B+00.11111 00.11010 Cn SA Q1 Q2 r0 2r0 r1 2r1 r2 r2 设置 A: 被除数、余数, B: 除数, C: 商 步数 条件 操作 A C 00.10101 5) 0 -B 01.01010 +11.00001 00.010110.01011 6) 1 -B 00.10110 +11.00001 11.10111 0.10110 7) 恢复余数 +B+00.11111 00.10110 Cn Q4 Q5 Q3 r3 2r3 r4 2r4 r5 r5 01.101004) 0 B +11.00001 2r2 0.00101 Q= - 0.10110R= - 0.10110 25 X/Y= - 0.10110 + - 0.1011025 0.11111 (3) 说明 A、B双符号位, 对X、Y 绝对值, | X | 小于 | Y | ; 运算结束后, 余数乘以2n, 与被除数同号。 X= QY+R + + + + + - - + - - + - - + - - 2、原码不恢复余数法(加减交替法) (1) 算法分析 设设Y表示除数，r表示余数。第i步将余数左移一位后减 除数(2ri-1-Y), 则则其上商与下一步操作可能出现现两种情况： 够减: 余数ri =2ri1 Y 0, 商1；Qi =1,下一步作 ri+1 = 2ri Y； = 2ri + Y 即: ri+1 =2ri + Y 但是: ri+1 = 2ri Y =2(ri+Y) Y 不够减: ri =2ri1 Y 0, 商0；Qi =0, 如果恢复余 数, 则ri = ri+Y = 2ri1 ; 下一步做ri+1 = 2ri Y; 所以:2ri Y与2ri+ Y 等效 (= ri+1) (2) 算法 ri为正, 则Qi为1, 第i+1步作2ri Y; ri为负, 则Qi为0, 第i+1步作2ri +Y。 (3) 实例 X= 0.10110, Y= 0.11111, 求X/Y, 给出商Q和 余数R。 初值: A= | X | = 00.10110 B= | Y | = 00.11111 C= | Q |= 0.00000 B补=11.00001 由此可得: ri+1 = 2ri + (1 2Qi)Y 步数 条件 操作 A C 00.10110 0.00000 1) 为正 B 01.01100 +11.00001 00.011010.00001 2) 为负 B 00.11010 +11.00001 11.110110.00010 3) +B+00.11111 11.10110 0.00101为正00.10101 Cn Q1 Q2 Q3 r0 2r0 r1 2r1 r2 2r2 r3 4) 为正 B 01.01010 +11.00001 00.010110.01011 Q4 2r3 r4 步数 条件 操作 A C 00.01011 0.01011 6) 为负 恢复余数 +B+00.11111 00.10110 Q= 0.10110 Cn Q4 r4 5) 为正 B 00.10110 +11.00001 11.101110.10110 Q5 2r4 r5 r5 R= 0.1011025 X/Y= 0.10110 + 0.1011025 0.11111 4) (4) 运算规则 A、B取双符号位, X、Y取绝对值运算, 且 | X | | Y | 。 根据余数的正负决定商值及下一步操作。 求n位商, 作n步操作; 若第n步余数为负,则 第n+1步恢复余数(以保证r0),不移位。 3、补码不恢复余数法(加减交替法) 如何上商？ 如何确定商符？ (1) 判断是否够减 (X/Y) 同号相除 4 7 1 4 3 4 7 1 ( 4) 3 7 4 0 (7) 3 够减 7 4 0 7 3 不够减够减 不够减 够减: r与X、Y同号;不够减: r与X、Y异号。 如何判断是否够减？ (r与Y同号)(r与Y异号) 异号相除 4 7 1 +(4) 3 够减 够 减: r与X同号, 与Y异号; 不够减: r与X异号, 与Y同号。 7 4 0 +7 3 不够减 4 7 1 +4 3 够减 不够减 7 4 0 +(7) 3 判断规则 同号: 作X补Y补 X补 Y补 够 减: r补与Y补同号 不够减: r补与Y补异号 异号: 作X补+Y补 够 减: r补与Y补异号 不够减: r补与Y补同号 (2) 求商值 X补 Y补 同号: 商为正 (r、Y同号) (r、Y异号) 够减商1 不够减商0 上商规则 ： Qi = Sri SY 余数与除数同号商1, 异号商0。 异号: 商为负 够减商0 不够减商1 (r、Y异号) (r、Y同号) 余数的符号除数的符号 因为商为负, 而负数的补码与真值相反( 除末位以外) (3) 算法 (ri+1)补=2ri补+(1 2Qi补)Y补 ri补与Y补同号, 则Qi补为1, 第i+1步作2ri补Y补; ri补与Y补异号, 则Qi补为0, 第i+1步作2ri补+Y补。 (4) 求商符 令 X补 = r0补 r0补与Y补 同号: Q0补= 1 异号: Q0补= 0 与实际商符相反 商符 便于与上商规则统一, 除法完成后进行修正 (5) 商的校正 X补 Y补 2n rn补 Y补 = (1+2n + 2i Qi补) + n1 i=0 商 余数 真商= 假商+1.00001 = Q0.Q1Q2Qn-1求n-1位商(假商) 2i Qi补 n1 i=0 +2n第n位商(末位商)恒置1 +1 商符变反 n位 余数求至rn (6) 实例 X=0.10110, Y= 0.11111, 求X/Y, 给出商Q和 余数R。 初值: A=X补=00.10110 B =Y补=11.00001 B=00.11111 C =Q补=0.00000 步数 条件 操作 A C 00.10110 0.0000 1) 异号 +B 01.01100 +11.00001 00.01101 0.0000 Cn-1 r、Y Q1 r0 2r0 r1 求商符 Q0 异号 余数与除数同号商1, 异号商0 2) 同号 +B 00.11010 +11.00001 11.11011 0.0001 Q2 2r1 r2 步数 条件 操作 A C Cn-1 5) +B+11.00001 00.10110 11.10111 3) 异号 B 11.10110 +00.11111 00.10101 0.0010 4) 异号 +B 01.01010 +11.00001 00.01011 0.0100 2r2 r3 2r3