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

3 3 3定点乘法运算 2 补码一位乘法 1 算法分析X补 X0 X1X2 Xn Y为正 Y补 0 Y1Y2 Yn XY 补 X补 0 Y1Y2 Yn Y为负 Y补 1 Y1Y2 Yn XY 补 X补 0 Y1Y2 Yn X 补 证明 2 对于定点小数 Y 补 2 Y 1 Y1Y2 Yn 则Y Y 补 2 1 0 Y1Y2 Yn 2 0 Y1Y2 Yn 1 所以 X Y X 0 Y1Y2 Yn 1 X 0 Y1Y2 Yn X 则 X Y 补 X 0 Y1Y2 Yn X 补 X 0 Y1Y2 Yn 补 X 补 X 补 0 Y1Y2 Yn 补 X 补 因为 0 Y1Y2 Yn 0 所以 X Y 补 X 补 0 Y1Y2 Yn X 补 将 和 结合起来 有如下的 式 Y符号任意 XY 补 X补 0 Y1Y2 Yn X 补Y0 符号位 展开为部分积的累加和形式 X补 0 Y1Y2 Yn X补Y0 X补 Y0 2 1Y1 2 2Y2 2 nYn X补 Y1 Y0 2 1 Y2 Y1 2 2 Y3 Y2 2 n 0 Yn XY 补 X补 0 Y1Y2 Yn X 补Y0 X补 Y0 Y1 2 1Y1 2 1Y2 2 2Y2 2 n 1 Yn 2 nYn 0 XY 补 X补 Y1 Y0 2 1 Y2 Y1 2 2 Y3 Y2 2 n Yn 1 Yn 在机器实现中可在末位Yn之后再增设一个附加位Yn 1 其初始值为0 对乘数Y的值并无影响 若定义 A0 补为初始部分积 A1 补 An 补依次为各步求得的累加和并且右移后的部分积 则可将上式改写为如下递推形式 它更接近于乘法的分步运算形式 A0 补 0 A1 补 2 1 A0 补 Yn 1 Yn X 补 A2 补 2 1 A1 补 Yn Yn 1 X 补 An 补 2 1 An 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 步数条件操作ACCnCn 1 00 0000 1 10 B 00 1101 00 1101 00 0110 11 0101 2 01 B 11 0011 11 1001 11 1100 111 010 3 10 B 00 1101 00 1001 00 0100 1111 01 4 01 B 11 0011 CnCn 1 1 01010 XY 补 0 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 10110 0 11111 0 10110 1101 0 11111 0 11111 0 0 11111 10101 0 11111 1011 0 0 1 0 1 1 0 0 00000 商 0 10110余数 0 10110 2 5 实现除法的关键 比较余数 除数绝对值大小 决定如何上商 可以推演出以下三种可由机器实现方法 比较法比较余数与除数的大小 够减则做减法 并商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 算法 新余数 步数条件操作AC 00 101100 00000 1 0 B 01 01100 11 00001 00 01101 0 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 商 步数条件操作AC 00 10101 5 0 B 01 01010 11 00001 00 01011 0 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 10100 4 0 B 11 00001 2r2 0 00101 Q 0 10110 R 0 10110 2 5 3 说明 A B双符号位 对X Y绝对值 X 小于 Y 运算结束后 余数乘以2 n 与被除数同号 X Q Y R 2 原码不恢复余数法 加减交替法 1 算法分析 设Y表示除数 r表示余数 第i步将余数左移一位后减除数 2ri 1 Y 则其上商与下一步操作可能出现两种情况 够减 余数ri 2ri 1 Y 0 商1 Qi 1 下一步作ri 1 2ri Y 2ri Y 即 ri 1 2ri Y 但是 ri 1 2ri Y 2 ri Y Y 不够减 ri 2ri 1 Y 0 商0 Qi 0 如果恢复余数 则ri ri Y 2ri 1 下一步做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 步数条件操作AC 00 101100 00000 1 为正 B 01 01100 11 00001 00 01101 0 00001 2 为负 B 00 11010 11 00001 11 11011 0 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 01011 0 01011 Q4 2r3 r4 步数条件操作AC 00 010110 01011 6 为负 恢复余数 B 00 11111 00 10110 Q 0 10110 Cn Q4 r4 5 为正 B 00 10110 11 00001 11 10111 0 10110 Q5 2r4 r5 r5 R 0 10110 2 5 4 4 运算规则 A B取双符号位 X Y取绝对值运算 且 X Y 根据余数的正负决定商值及下一步操作 求n位商 作n步操作 若第n步余数为负 则第n 1步恢复余数 以保证r 0 不移位 3 补码不恢复余数法 加减交替法 如何上商 如何确定商符 1 判断是否够减 X Y 同号相除 够减 不够减 够减 不够减 够减 r与X Y同号 不够减 r与X Y异号 如何判断是否够减 r与Y同号 r与Y异号 异号相除 够减 r与X同号 与Y异号 不够减 r与X异号 与Y同号 判断规则 同号 作X补 Y补 够减 r补与Y补同号 不够减 r补与Y补异号 异号 作X补 Y补 够减 r补与Y补异号 不够减 r补与Y补同号 2 求商值 上商规则 余数与除数同号商1 异号商0 余数的符号 除数的符号 因为商为负 而负数的补码与真值相反 除末位以外 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 商的校正 商 余数 真商 假商 1 000 01 Q0 Q1Q2 Qn 1 求n 1位商 假商 2 n 第n位商 末位商 恒置1 1 商符变反 n位 余数求至rn 6 实例 X 0 10110 Y 0 11111 求X Y 给出商Q和余数R 初值 A X补 00 10110B Y补 11 00001 B 00 11111C Q补 0 00000 步数条件操作AC 00 101100 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 步数条件操作AC 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 r4 2r4 r5 Q4 Q3 假商 0 0100 真商 0 0100 1 00001 1 01001 补码 Q 0 10111R 0 01001 2 5 真值 余数 11 10111 补码 7 运算规则 A B取双符号位 符号参加运算 X Y 根据余数与除数的符号决定商值及下一步操作 求n 1位商 作n步操作 求出rn 对商校正 商符变反 第n位商恒置1