2_5除法算法

除法算法位数循环算法10进制除法:102413(1)1-130(2)10-130(3)10213x7=91(4)11413x80102413001024131010411491007810241310进制二进制更简单商只有0,1两种可能余数大于除数商=1余数小于除数商=0恢复余数算法BPA减法器左移被除数=商X除数+余数首先把被除数放进移位寄存器A,再把除数放进移位寄存器B，把寄存器P置0,然后进行N个步骤（N是商的二进制位数）1.把P、A寄存器整体左移一位2.在P中减去B，然后把结果再放回P恢复余数算法恢复余数算法3.如果结果是负数，把A的最后一位置0，而且让P再加上B来实现恢复上一个P的值4.如果结果是正数，则直接向左移位5.通过N次循环之后，A中内容是商，而P中内容是余数（如下图所示）PA注释000001110被除数是14=1110，除数是3=0011B寄存器永远是001100001110_第一步，P、A寄存器全体左移一位-00011第二步，两数相减------------------111101100第一步，相减之后是负数，所以把寄存器A末位置0000011100第二步，因为结果是负数，恢复（恢复红字P的内容）00011100_第三步，左移一位-00011第四步，相减-------------------000001001第一步，相减之后是正数，所以把寄存器A末位置100001001_第二步，因为相减之后是正数，所以不需要恢复原数-00011第三步，相减---------------------111100010第一步，相减之后是负数，所以把寄存器A末位置0000010010第二步，因为结果是负数，恢复（恢复紫色P的内容）00010010_第三步，左移一位-00011---------------------111110100第一步，相减之后是负数，所以把寄存器A末位置0000100100第二步，因为结果是负数，恢复（恢复绿色时P的值）以十进制除法来说明以上的二进制除法算法以102除以9为例说明除法其实就是循环移位减法PA注释0000102把102放进A，把9放进B000102_左移一位-0009相减-------------------0008020因为相减之后是负数，所以末位置00001020因为结果是负数，恢复（恢复P中显示紫色数的内容）001020_左移一位-0009相减-------------------0001201因为相减之后是正数，所以末位置1001201_因为相减之后是正数，所以不需要恢复，直接移位-0009-------------------0003011因为相减之后是正数，所以末位置1经过3次循环，寄存器A中的内容是商11，寄存器P中的内容3是余数，102除以9商11余3即为所求不恢复余数算法恢复余数算法中需要恢复余数的环节为:设某次余数为ri,则下一步的余数ri+1=2×ri-y,当ri+10时表明不够减,商上0并且余数加y恢复原来的余数,即(2×ri-y)+y=2×ri。若继续下面的求商,则再下一步的余数ri+2=2×(2×ri)-y=4×ri-y。当ri+10时,若商仍上0但不进行加y恢复余数操作,而是把(2ri-y)左移一位,然后加上除数y,即2×(2×ri-y)+y=4ri-y,所得效果相同。所以,当比较结果小于0时,求下面的商时仍将未修正的余数左移一位,然后加y进行比较就是所谓的不恢复余数法又称为加减交替法。不恢复余数算法由此得出不恢复余数除法得法则为：当余数为正时，商“1”，做ri-|y|的运算当余数为负时，商“0”，做ri+|y|的运算这里已经没有回复于数的问题，只是将余数左移一位加上或者减去除数，因此又称为加减交替法。不恢复余数算法区别如果P是负数1、把P、A寄存器同时左移一位2、把寄存器B的内容加到P中如果P是正数1、把P、A寄存器同时左移一位2、从P中减去B寄存器中的内容如果P是负数，则把A最低位的内容置0如果P是正数，则把A最低位的内容置1在N次循环之后从寄存器A中取商如果P是正数，则寄存器P中的内容就是余数，否则他则应该加上B的内容得到余数(过程如下图)PA注释000001110被除数是14=1110，除数是3=0011B寄存器永远是001100001110_第一步，P、A寄存器全体左移一位-00011第二步，因为是移位结果是正数，所以相减-----------------111101100第一步，相减之后是负数，所以把寄存器A末位置011101100_第二步，左移一位+00011第三步，因为是上一步结果是负数，所以相加-------------------000001001第一步，相减之后是正数，所以把寄存器A末位置100001001_第二步，左移一位-00011第三步，因为是上一步结果是正数，所以相减--------------------111100010第一步，相减之后是负数，所以把寄存器A末位置011100010_第二步，左移一位+00011第三步，因为是上一步结果是负数，所以相加--------------------111110100第一步，相减之后是负数，所以把寄存器A末位置0000100100第二步，因为结果是负数，寄存器P加上寄存器B的内容得00010以上就是两种位数循环算法的除法算法THEEND以14除3为例子14的二进制表示为1110，3的二进制表示为00110011000001110减法器以14除3为例14的二进制表示是1110，3的二进制表示是00110011000001110运算器不恢复余数算法0011000001110运算器左移00001因为最高位是0，是正数，所以运算器执行减法相减的结果是：11110并将结果放进寄存器P11110因为相减之后最高位是1，是负数，所以A寄存器最低位置0110_1110第一次循环恢复余数算法00011000001110减法器左移结果是-11110110_00001110011110结果是负数，所以末位置0第一次循环不恢复余数算法BPA运算器左移不恢复余数算法0011111101100运算器左移11101因为最高位是1，是负数，所以运算器执行加法相减的结果是：00000并将结果放进寄存器P00000因为相减之后最高位是0，是正数，所以A寄存器最低位置1100_1001第二次循环不恢复余数算法0011000001001运算器左移00001因为最高位是0，是正数，所以运算器执行借位减法相减的结果是：11110并将结果放进寄存器P11110因为相减之后最高位是1，是负数，所以A寄存器最低位置0001_0010第三次循环不恢复余数算法0011111100010运算器左移11100因为最高位是1，是负数，所以运算器执行进位加法相减的结果是：11111并将结果放进寄存器P11111因为相减之后最高位是1，是负数，所以A寄存器最低位置0010_0100第四次循环因为结果的最高位是1，是负数，所以不能直接取作余数，应与B的内容相加后取数得00010，即余2而A寄存器中的内容的内容可以直接取商，商是0100，即414除以3的结果是商4余3，结果即为所求以14除3为例子14的二进制表示为1110，3的二进制表示为00110011000010100减法器恢复原所存值（通过加上B的内容）00010经过四个循环后，取A的内容为余数，余数为00010，即余2取P的内容为商，商为0100，即商4最终14除以3，结果是商4余2恢复余数算法00011111101100减法器左移结果是00000(是正数)00001100_00011000001001恢复原所存值（通过加上B的内容）结果是正数，所以末位置1第二次循环恢复余数算法00011000001001减法器左移结果是-11110001_00001111100010因为减得的是正数，所以不需要恢复原数结果是负数，所以末位置0第三次循环恢复余数算法00011111100010减法器左移结果是-1111100001010_00010111110100恢复原所存值（通过加上B的内容）结果是负数，所以末位置0第四次循环