第5讲定点除法.ppt

计算机组成原理 PrinciplesofComputerOrganization 广义双语教学课程 http 211 64 192 109 skyclass25 青岛理工大学校级精品课程 1 2 第6章计算机的运算方法 4 Severalalgorithmsexisttoperformdivisionindigitaldesigns Thesealgorithmsfallintotwomaincategories slowdivisionandfastdivision Slowdivisionalgorithmsproduceonedigitofthefinalquotientperiteration Examplesofslowdivisionincluderestoring non performingrestoring non restoring andSRTdivision Fastdivisionmethodsstartwithacloseapproximationtothefinalquotientandproducetwiceasmanydigitsofthefinalquotientoneachiteration Newton RaphsonandGoldschmidtfallintothiscategory 3 6 3 4除法运算 Binary Fixed Point DivisionArithmetic 原码除法 补码除法 Tow scomplementDivision UnsignedBinaryDivision 4 计算机的除法运算对除数和被除数的大小有限制 首先 除数不能为零 其次 定点除法运算可能会发生溢出 对于定点小数 若被除数大于或等于除数 则商将大于或等于1 发生溢出 所以 小数除法要求0 被除数 除数 对于定点整数 商也应是整数 要求0 除数 被除数 计算机在做除法之前 必须先检查除数和被除数是否为零 若除数为零 则转出错处理 若被除数为零 则直接得出商为零 若除数和被除数都不为零 则判断是否可能发生溢出 若除数是n位 则得到n位的商Quotient和n位的余数Remainder 整数除法若被除数Dividend只有n位 是不会发生溢出的 但是 若被除数为2n位 则被除数的高n位的绝对值必须小于除数Divisor的绝对值 否则 将发生溢出 小数除法 只要满足 被除数 除数 就不会溢出 5 手工计算二进制除法的方法 0 1011被除数 除数0 1101 商0 先判断被除数与除数的大小 若被除数小 则上商0 并把被除数的下一位 若存在 移下来 或在余数最低位补0 再用余数与右移一位的除数比较 若够除则上商1 否则上商0 然后继续重复以上步骤 直至除尽 余数为0 或求得的商的位数满足要求为止 01101 部分余数010010 01101 PartialRemainder0010100 01101 001110 01101 1 1 0 1 1 6 计算机实现除法时 要把除数右移改为被除数 余数左移 要求计算机把求得的商直接写进商寄存器的每个对应位也是不可取的 通常是把商上到商寄存器的最低位 并把部分商左移一位 运算过程中 存放被除数 余数和商的寄存器一同移位 计算完成后 商寄存器中是商的尾数 原来存放被除数的寄存器中是余数 做减法时 对于n位的除数 也不要求2n位的加法器 只需用n位的加法器即可 7 原码除法运算 原码除法 商的符号位是除数和被除数的符号位的异或值 商的值是用被除数的绝对值除以除数的绝对值得出的 计算机不能象人那样用观察的方法决定是上商0还是上商1 1 比较法 用汇编语言编写除法运算程序 可以用比较指令比较除数和被除数 余数 的大小 以决定是上商0还是上商1 这就是比较法 计算机的比较指令实质上也是做减法 但摒弃减法的结果 不改变被减数 只影响状态标志寄存器的Cy 进位 借位 S 符号 Z 零 等标志位的状态 若Cy 1 表明有借位 被除数小于除数 应当上商0 不做被除数 余数减除数 只把被除数 余数左移一位 反之 上商1 做被除数 余数减除数 并把余数左移一位 比较法要多做一次比较 降低了速度 UnsignedBinaryDivision 8 2 恢复余数法 直接从被除数 余数中减去除数 若够减 余数为正 上商1 若不够减 余数为负 上商0 此时 必须将除数加回去 恢复成原来的余数 以便继续计算 因此称为恢复余数法 恢复余数法在不够减时要恢复余数 多做一次加法操作 运算速度因而受到影响 控制线路复杂 运算不规则 运算时间与数据有关 在计算机中实际采用的是不恢复余数法Non restoringdivision Restoringdivision 9 3 加减交替法 不恢复余数法Non restoringdivision 不恢复余数法的思想是当某一次减法的差为负时 不是把它恢复成原来的值 而是设法直接用这个负的差值求下一位商 设上次余数为Ri 当Ri 0时 然后将余数左移一位 成为2Ri 2Y 当Ri 0时 显然 若不恢复余数 而将余数Ri左移一位成为2Ri 再加除数 结果与恢复余数法一样 但却把加Y 左移 减Y三个步骤简化成左移 加Y两个步骤 商上1 继续求下次余数 将余数左移一位得2Ri 再减除数 即2Ri Y Ri 1 商上0 此时若恢复余数 应做Ri Y 即2Ri 2Y Y 再减除数 2Ri Y Ri 1 10 最后一次余数若为负值 还应加上除数以得到正确的余数 运算中共左移n次 相当于乘2n 最后的余数应为Rn 2 n 余数的符号与被除数一致 由于不恢复余数法要根据余数Ri的情况分别做加法或减法 所以又称为加减交替法 无符号数不恢复余数除法算法流程图 Y 计数器i 0X Y R 商1 商上0 Ri左移一位 2Ri Y Ri 1 商上1 Ri左移一位 2Ri Y Ri 1 i 1 i 商0Rn Y 开始 Ri 0 Y Y N i n N Rn 0 结束 N 除数 被除数符合规定允许进行除法运算 符号位单独运算 图中的X和Y实际是 X 和 Y 第一位商是小数点左边的0 总共求出N 1位商 11 12 例1 X 0 1001 Y 0 1011 用原码不恢复余数法计算X Y 解 X 原 1 1001 X 0 1001 商的符号位 Y 原 0 1011 Y 0 1011 Y 补 1 0101 减 Y 左移加 Y 左移减 Y 左移减 Y 左移加 Y 被除数 余数0 1001 1 01011 11101 1100 0 10110 01110 1110 1 01010 00110 0110 1 01011 10111 0110 0 10110 0001 商0000000000000000001000100011001100110011001101 减Y用加 Y 的补码实现余数为负 商上0余数为正 商上1余数为正 商上1余数为负 商上0余数为正 商上1 X Y 0 1101 X Y 原 1 1101 X Y 0 1101 余数 R 0 0001 2 4 R 0 00000001 13 14 补码除法运算Two scomplementDivision 补码运算是连同符号位一起进行的 所以 商的符号也可在求商的过程中象求商值那样获得 求第一位商时 是用被除数 X 补与除数 Y 补比较 求以后各位商时 则是用余数 R 补与除数 Y 补比较 补码加减交替除法的规则 若被除数与除数同号 做被除数减除数 若被除数与除数异号 做被除数加除数 实质上都是求差 若余数与除数同号 上商1 余数左移一位后做余数减除数 求得新余数 若余数与除数异号 上商0 余数左移一位后做余数加除数 重复步骤 n次 末位商恒置1法 或n 1次 校正法 补码除法的商也应是补码 第一次获得的商是商的符号位 在不发生溢出的情况下 X Y 得到的就是正确的符号位的值 15 当 X 补与 Y 补同号时 X 补 Y 补肯定不够减 余数 R 补与除数 Y 补异号 上商0 符合同号相除为正的规则 当 X 补与 Y 补异号时 R 补与 Y 补同号 应上商1 也符合异号相除为负的规则 当商为正时 上商规则与原码除法相同 余数与除数同号表明够减 上商1 余数与除数异号表明不够减 上商0 当商为负时 余数与除数异号表明够减 应上商0而非上商1 余数与除数同号表明不够减 应上商1而非上商0 即在上商时 负商的每位商的值与真值相反 实际上是反码 而补码和反码的区别仅在最低数值位差1 即2 n 这就需要对负商进行修正 以得到补码形式的商 在对商的精度要求不高时 可采用 末位商恒置1 法 即包括符号位在内只求n位的商 第n 1位则恒置1 末位商恒置1 法的操作简单 易于实现 其最大误差是 2 n 补码加减交替除法算法流程图 末位商恒置1 X 补 Y 补 R0 补 X 补 Y 补 R0 补 Y 计数器i N 商上1 Ri 补左移一位 2 Ri 补 Y 补 Ri 1 补 商上0 Ri 补左移一位 2 Ri 补 Y 补 Ri 1 补 i 1 i 末位商qn 1 末位商恒置1法 R0 Y0 Y Y N i 0 N X0 Y0 结束 N 16 17 例2 X 0 0100 Y 0 1000 用补码加减交替法计算X Y 解 X 补 Y 补 Y 补 0 0100 1 1000 0 1000 被除数 余数00 0100 商0 0000 做2R0 Y R1 商 Q 补 1 0111 Q 0 1001 余数不为0 实际上 此例是能除尽的 商应为 0 1000 X 补 0 0100 Y 补 1 1000 X Y异号 加 Y 补11 1000 R0 补与 Y 补同号 商上1 11 1100 左移 末位商置1 11 1000 加 Y 补00 1000 左移 11 0000 做2R3 Y R4 R3 补与 Y 补同号 商上1 11 1000 做2R2 Y R3 加 Y 补00 1000 左移 11 0000 R2 补与 Y 补同号 商上1 11 1000 0 0101 做2R1 Y R2 1 0111 0 1011 加 Y 补11 1000 左移 00 0000 0 0100 0 1010 1 0110 0 0010 R1 补与 Y 补异号 商上0 00 0000 加 Y 补00 1000 0 0010 11 1000 0 0001 18 19 若用校正法 再求一步商 商加2 4 11 1000 1 0111 R4 补与 Y 补同号 商上1 得到正确的商 Q 补 1 1000 正确余数R 0 恢复余数 正确的商 校正商 加 Y 补 00 0000 00 1000 1 1000 0 0001 Q 0 1000 20 Homework 6 21 3 4 22 Namedforitscreators Sweeney Robertson andTocher SRTdivisionisapopularmethodfordivisioninmanymicroprocessorimplementations SRTdivisionissimilartonon restoringdivision butitusesalookuptablebasedo