| 5.8 汇编语言：汇编高效除法运算 | 您所在的位置：网站首页 › python整除运算-2除以8等 › 5.8 汇编语言：汇编高效除法运算 |
|
通常情况下计算除法会使用div/idiv这两条指令，该指令分别用于计算无符号和有符号除法运算，但除法运算所需要耗费的时间非常多，大概需要比乘法运算多消耗10倍的CPU时钟，在Debug模式下，除法运算不会被优化，但Release模式下，除法运算指令会被特定的算法经过优化后转化为为乘法，这样就可以提高除法运算的效率。 1.如果被除数是一个未知数，那么编译器无法确定数值，则编译器会使用原始的div指令计算，程序的执行效率会变低。2.如果除数是2的次幂，那么可以将其转化为处理速度快的shr逻辑右移指令指令，该指令的执行只需要1个时钟周期，效率最高。3.如果要进行2的次幂，并且该数是有符号数，则只需要使用sar算数右移指令，即可进行快速除法运算。 8.1 使用IDIV指令完成除法与乘法运算相同，在不考虑效率前提下，完全可以使用IDIV指令完成除法运算，该指令比乘法还慢。 计算除法时应遵循:如果除数为8位被除数为16位,则结果的商存放在AL中,余数存放AH中如果除数为16位被除数为32位,则结果的商存放与AX中,余数存放DX中如果除数为32位被除数为64位,则结果的商存放与EAX中,余数存放EDX中指令CDQ用于扩展寄存器,扩展后EDX存储高位而EAX存储低位除法指令计算很简单，只需要扩展CDQ寄存器，然后累计除即可。 .data x DWORD ? y DWORD ? szFmt BYTE '计算结果: %d',0dh,0ah,0 .code main PROC mov dword ptr ds:[x],1000 mov dword ptr ds:[y],20 ; 计算 x / y mov eax,dword ptr ds:[x] ; eax = 1000 cdq ; 把eax的第31bit复制到edx的每个bit上 idiv dword ptr ds:[y] ; eax = x / y invoke crt_printf,addr szFmt,eax main ENDP END main 8.2 除数为正2的次幂(无符号)如果除数是正数被除数也是正数，且除数的范围是正2的次幂，那么我们就可以使用sar算数右移指令来替代div除法指令，通过改变2的次幂的移位次数即可实现无符号除法的高速运算。 计算时我们需要参考次方表,这里我列举出几个常用的次方数值: 次方表: 1=>2 2=>4 3=>8 4=>16 5=>32 6=>64 7=>128次方表: 8=>256 9=>512 10=>1024 11=>2048 12=>4096 13=>8192 14=>16384以下代码中分别演示了除数为2/4/8三种计算方式，计算结果只需sar移位即可实现。 .data x DWORD ? szFmt BYTE '计算结果: %d',0dh,0ah,0 .code main PROC mov dword ptr ds:[x],5 ; ---------------------------------------------------- ; 【除数为2】 ; 被除数为正数(无需扩展): eax => 5 / 2 = 2 mov eax,dword ptr ds:[x] ; 被除数 sar eax,1 ; 算数右移1位 invoke crt_printf,addr szFmt,eax ; ---------------------------------------------------- ; 【除数为4】 ; 被除数为正数(无需扩展): eax => 5 / 4 = 1 mov eax,dword ptr ds:[x] sar eax,2 ; 算数右移2位 invoke crt_printf,addr szFmt,eax ; ---------------------------------------------------- ; 【除数为8】 ; 被除数为正数(无需扩展): eax => 5 / 8 = 0 mov eax,dword ptr ds:[x] sar eax,3 ; 算数右移3位 invoke crt_printf,addr szFmt,eax invoke ExitProcess,0 main ENDP END main 8.3 除数为负2的次幂(有符号)如果除数是负数，且除数范围在负2的次幂内，那么在计算时应使用cdq指令将被除数EAX扩展为64位，并将扩展后的结果放入EDX:EAX寄存器内，然后使用sub eax,edx减去高位符号位，接着通过sar算数右移指令完成除法运算，最终通过neg指令将结果翻转即可。 总结计算过程如下:1.使用 cdq 指令将 eax 扩展为64位,结果分别存入 EDX:EAX 寄存器内.2.使用 sub eax,edx 指令将高位符号位通过减法减掉.3.使用 sar eax,x 指令完成算数右移除法运算.4.使用 neg eax 将计算后的正数反转为负数.这个过程通过汇编语言实现代码很简单,如下代码演示了除数为正数且被除数为 -2/-4/-8 次幂的计算过程. .data x DWORD ? szFmt BYTE '计算结果: %d',0dh,0ah,0 .code main PROC mov dword ptr ds:[x],10 ; 除数为(有符号)负2的次幂的计算过程 ; 计算 10 / -2 mov eax,dword ptr ds:[x] ; x = 10 cdq ; 符号扩展 [edx:eax] sub eax,edx ; 减去符号位 sar eax,1 ; eax = 10 / -2 neg eax ; 将正数 eax 翻转为负数 = -5 invoke crt_printf,addr szFmt,eax ; 计算 10 / -4 mov eax,dword ptr ds:[x] ; x = 10 cdq and edx,3 add eax,edx sar eax,2 ; eax = 10 / -4 neg eax ; eax = -2 invoke crt_printf,addr szFmt,eax ; 计算 10 / -8 mov eax,dword ptr ds:[x] cdq and edx,7 add eax,edx sar eax,3 neg eax invoke crt_printf,addr szFmt,eax invoke ExitProcess,0 main ENDP END main 8.4 被除数为负数(有符号)在有符号数的除法中，如果被除数为负数，而除数是正2的次幂，那么可以使用neg取反操作来得到正确的计算结果。具体步骤如下： 首先，将被除数的绝对值与除数进行除法运算，并得到正确的商。如果被除数为负数，则对商进行取反操作。如果除数为负数，则最终结果也要进行取反操作。例如，假设要计算-27除以8的值，我们可以按照如下步骤进行计算： 计算27除以8的值，得到商3和余数3。因为被除数为负数，所以对商取反，得到-3。因为除数为正数，所以最终结果为-3，即-27/8的计算结果。类似地，如果除数为负数，我们需要在得到正确的计算结果后再进行一次取反操作，这样才能得到真正的结果。需要注意的是，上述方法仅适用于除数为正2的次幂的情况下。对于其他情况，需要使用更为复杂的算法来完成除法计算。 .data x DWORD ? y DWORD ? szFmt BYTE '计算结果: %d',0dh,0ah,0 .code main PROC mov dword ptr ds:[x],-10 mov dword ptr ds:[y],-5 ; 被除数为(有符号)的计算过程 ; 计算 -10 / 2 mov eax,dword ptr ds:[x] cdq sub eax,edx sar eax,1 ; eax = -10 / 2 invoke crt_printf,addr szFmt,eax ; 计算 -5 / 4 mov eax,dword ptr ds:[y] cdq xor edx,edx add eax,edx sar eax,2 ; eax = -5 / 4 invoke crt_printf,addr szFmt,eax ; 计算 -10 / 8 mov eax,dword ptr ds:[x] cdq ; 位扩展 xor edx,edx ; 清空高位 add eax,edx sar eax,3 ; eax = -10 / 8 invoke crt_printf,addr szFmt,eax invoke ExitProcess,0 main ENDP END main 8.5 除数与被除数均为负数(有符号)在有符号数的除法中，如果除数和被除数均为负数，且除数为负2的次幂，可以使用算数右移指令sar来完成除法运算，然后通过取反指令neg来翻转得到的计算结果的符号位。 具体来说，一个有符号整数除以负2的次幂，等价于这个有符号整数右移除数的位数作为移位数，然后转为无符号数进行运算，再将得到的无符号数转回符号位正确的有符号数即可。由于右移的操作是算数右移，所以被移位的符号位会被保留。 例如，将-16除以-8，即计算-16/-8的结果，因为8是2的3次幂，所以我们可以通过算数右移指令来完成除法，然后再取反获得正确的结果： 将-16右移3位，得到-2。对-2进行取反，得到2。因为-16和-8均为负数，所以最终结果也要进行一次取反操作。因此，得到的结果为-2。 需要注意的是，上述方法仅适用于除数为负2的次幂，如果除数不是负2的次幂，则需要使用其他算法来计算除法运算。 .data x DWORD ? y DWORD ? z DWORD ? szFmt BYTE '计算结果: %d',0dh,0ah,0 .code main PROC mov dword ptr ds:[x],-5 mov dword ptr ds:[y],-24 mov dword ptr ds:[z],-10 ; 如果同时为负数的情况 ; 计算 -5 / -2 mov eax,dword ptr ds:[x] cdq ; 符号扩展 xor edx,edx ; 清空高位 add eax,edx sar eax,1 ; 算数右移动 -5 / -2 neg eax ; eax = 3 (负负得正) invoke crt_printf,addr szFmt,eax ; 计算 -24 / -4 mov eax,dword ptr ds:[y] cdq ; 符号扩展 xor edx,edx ; 清空高位 add eax,edx sar eax,2 ; 算数右移动 -24 / -4 neg eax ; eax = 6 (负负得正) invoke crt_printf,addr szFmt,eax ; 计算 -10 / -8 mov eax,dword ptr ds:[z] ; z = -10 cdq ; 符号扩展 xor edx,edx ; 清空高位 add eax,edx sar eax,3 ; eax = -10 / -8 neg eax ; eax = 1 (负负得正) invoke crt_printf,addr szFmt,eax invoke ExitProcess,0 main ENDP END main如上我们所有的除法运算中，无论是有符号还是无符号都在进行2的次幂运算，通常针对2的次幂运算并不需要经过特殊的模M计算，而对于非2次幂3/5/7的运算，则需要通过一定的公式才能简化计算过程，如下将开始介绍非2次幂除法运算该如何优化。 8.6 除数为正非2次幂(有符号)对于除数为正非2次幂的有符号数，我们需要使用其他的算法来完成除法运算。通常情况下，可以使用恒等式转化法或移位除法来进行计算。 一种常用的移位除法算法是: 将被除数与除数分别取绝对值，并记录下符号。如果除数大于被除数，则直接返回0。通过不断将除数左移，直到左移之后的除数大于等于被除数，得到最高位的不为0的位数，记为n。将除数左移n位，然后不断依次将左移后的除数与被除数相减，直到被除数小于除数。记录下相减的次数，即为最终的商。上述算法仅适用于除数为正数的情况。如果除数为负数，则需要先取反，然后使用移位除法的算法来计算除法运算，并最终再取反，以得到正确的计算结果。 关于求解公式2^(32+n) / M的使用方法：可以通过移位和除法结合的方法来计算，具体可以按照以下步骤进行计算： 将除数M保存在寄存器中，将32+n的值保存在寄存器中。执行左移指令，将32+n左移至最高位。将左移后的值保存在另一个寄存器中。执行除法指令，将左移后的值除以M，得到商和余数。如果余数不为0，则重新计算32+n+1的值，再次执行上述步骤。这样，不断重复这个过程，就可以计算出2^(32+n) / M的结果。 先来看一段汇编代码，我们此时已知 M = 055555556h 且 edx = N 带入公式 2^(32+N) / M 由于edx没有变化所以此处应计算 2^32 / 055555556h = 2.9999 即可计算出此处的除数是3，而被除数则是ecx寄存器内的值，我们即可得知该段汇编指令在进行 ecx / 3 的计算流程。 mov ecx,dword ptr ds:[y] ; 被除数 mov eax,055555556h ; M值 => 此处的M模值是编译器计算后得到的(我们无需深入理解) imul ecx mov eax,edx ; edx = N shr eax,01fh add edx,eax invoke crt_printf,addr szFmt,edx再来看另一段，这段代码中 sar edx,1 此时edx的值发生过一次变化变换了1次，所以公式中应该加上变化的一次计算得到 2^33 / 66666667 = 5 所以可得到当前除数是5 mov ecx,dword ptr ds:[y] ; ecx = 10 / 5 = 2 mov eax,066666667h ; 此处的M模值是编译器计算后得到的 imul ecx sar edx,1 ; 想要知道除数是多少,只需要执行以下计算 mov eax,edx ; 2^(32 + edx) / M = 2^33 / 66666667 = 5 shr eax,01fh ; 33次方的由来,其实是默认的32次方加上 sar edx,1 中的1次方得到的 add edx,eax invoke crt_printf,addr szFmt,edx针对除数为非2的次幂且为有符号数，只需要提供对应的M模值，根据模值即可将对应的除法转换为乘法，一般写法如下: .data x DWORD ? szFmt BYTE '计算结果: %d',0dh,0ah,0 .code main PROC mov dword ptr ds:[x],10 ; 除法(无符号)非2的幂转换为乘法 ; 计算 10 / 3 mov ecx,dword ptr ds:[x] ; 被除数 ecx = 10 / 3 = 3 mov eax,055555556h ; eax = M值 1431655766 imul ecx mov eax,edx ; edx = n 计算: 2^(32+n) / M shr eax,01fh ; 计算出除数为 2.9999 => 3 add edx,eax invoke crt_printf,addr szFmt,edx ; 计算 10 / 5 mov ecx,dword ptr ds:[x] ; ecx = 10 / 5 = 2 mov eax,066666667h ; 此处的M模值是编译器计算后得到的 imul ecx sar edx,1 ; 想要知道除数是多少,只需要 mov eax,edx ; 2^(32 + edx) / M = 2^33 / 66666667 = 5 shr eax,01fh ; 逻辑右移 add edx,eax invoke crt_printf,addr szFmt,edx ; 计算 10 / 6 mov ecx,dword ptr ds:[x] ; ecx = 10 / 6 = 1 mov eax,02AAAAAABh ; eax = 715827883 imul ecx mov eax,edx ; 2^(32 + edx) / M = 2^32 / 2AAAAAAB = 6 shr eax,01fh add edx,eax invoke crt_printf,addr szFmt,edx invoke ExitProcess,0 main ENDP END main 8.7 除数为正非2次幂(无符号)在上方代码中的除法计算是针对有符号数进行的，如果是针对无符号数则需要另一种计算方式，对于除数为正非2次幂的无符号数，这里介绍一种常用的算法，恒等式转化法。 假设我们需要计算一个64位无符号整数x除以一个32位无符号整数y的值，我们可以按照以下步骤进行计算： 计算2^32/y的低32位，假设得到的结果为k，即k = floor(2^32/y) 。将x的高32位和低32位分别除以y，并将商的高32位保存下来，记为q1，即q1 = floor(high_32_bits(x) / y) 。将q1乘以k，并将结果右移32位，得到kq1的高32位，记为q2，即q2 = floor( k * q1 / 2^32 ) 。将x的低32位与被除数的乘积减去 q2 乘以y的值就是x除以y的值，即(floor(x * k / 2^32) - q2) * y + x mod y。以上步骤可以用以下公式来表示： x / y = [(floor(high_32_bits(x) / y) * floor(2^32 / y) + floor(k * floor(high_32_bits(x) / y) / 2^32) * 2^32) * y + x mod y] / y其中，high_32_bits(x)表示x的高32位，floor()表示向下取整，mod表示取余数。 需要注意，上述算法仅适用于除数为正数的情况。如果除数为负数，则需要先将除数取反，然后使用恒等式转化法的算法来计算除法运算，并最终再取反，以得到正确的计算结果。 .data x DWORD ? y DWORD ? z DWORD ? szFmt BYTE '计算结果: %d',0dh,0ah,0 .code main PROC mov dword ptr ds:[x],-5 mov dword ptr ds:[y],10 mov dword ptr ds:[z],20 ; 除法(无符号)非2的次幂(正数)转换为乘法 xor edx,edx mov ecx,dword ptr ds:[y] ; ecx = 10 mov eax,0AAAAAAABh ; ecx / 3 = 3 mul ecx shr edx,1 invoke crt_printf,addr szFmt,edx ; 还原除数: 2 ^(32 + n) / M => 2 ^ (32+2) / 0CCCCCCCDh = 5 xor edx,edx mov ecx,dword ptr ds:[y] ; ecx = 10 => 计算: 10/5 mov eax,0CCCCCCCDh ; eax = M mul ecx shr edx,2 ; edx= n invoke crt_printf,addr szFmt,edx ; 还原除数: 2 ^(32 + n) / M => 2 ^ (32+2) / 0AAAAAAABh = 6 xor edx,edx mov ecx,dword ptr ds:[y] ; ecx = 10 => 计算:10/6 mov eax,0AAAAAAABh ; eax = M mul ecx shr edx,2 ; edx = n invoke crt_printf,addr szFmt,edx ;还原除数: 2 ^(32 + n) / M => 2 ^ 33 / 038E38E39h = 9 xor edx,edx mov ecx,dword ptr ds:[z] ; ecx = 20 => 计算: 20/9 mov eax,038E38E39h ; eax = M mul ecx shr edx,1 ; edx = n invoke crt_printf,addr szFmt,edx invoke ExitProcess,0 main ENDP END main 8.8 除数为负非2次幂(无符号)如果我们的除数是一个负数，且范围是非2的次幂，那么当我们计算结束后，只需要在原来基础上多增加一个neg将结果翻转以下即可。 采用与有符号整数的移位除法类似的方法，分为两个阶段完成。 阶段1：将除数和被除数分别取绝对值，并计算出商的符号。由于除数为负数，所以商的符号为负号。阶段2：使用移位除法算法（详见上述有符号数除法的算法），计算出无符号整数的商。最后，因为商为负数，所以需要将其翻转一下，即执行一次取反指令neg，以得到正确的计算结果。 .data x DWORD ? y DWORD ? szFmt BYTE '计算结果: %d',0dh,0ah,0 .code main PROC mov dword ptr ds:[x],10 mov dword ptr ds:[y],20 ; 还原除数: 2 ^(32 + n) / M => 2 ^ 33 / 0AAAAAAABh = nge(3) => -3 xor edx,edx mov ecx,dword ptr ds:[y] ; ecx = 20 => 计算: 20 / -3 mov eax,0AAAAAAABh ; eax = M mul ecx shr edx,1 ; edx = n neg edx ; edx=6 结果neg取反 invoke crt_printf,addr szFmt,edx ; 还原除数: 2 ^(32 + n) / M => 2 ^ 62 / 040000001h = 4294967292 xor edx,edx mov ecx,dword ptr ds:[x] ; ecx = 10 => 计算: 10 / -3 mov eax,040000001h ; eax = M mul ecx shr edx,01eh ; edx = n invoke crt_printf,addr szFmt,edx invoke ExitProcess,0 main ENDP END main而如果反过来，被除数变成负数，而除数则还是非2的次幂，那么计算方式应该如下所示: .data x DWORD ? szFmt BYTE '计算结果: %d',0dh,0ah,0 .code main PROC mov dword ptr ds:[x],-10 ; 除法(有符号)非2的幂转换为乘法 mov ecx,dword ptr ds:[x] ; ecx = -10 / 9 = -1 mov eax,038E38E39h ; eax = 954437177 imul ecx sar edx,1 ; 2^(32 + edx) / M = 2^33 / 38E38E39 = 9 mov ecx,edx shr ecx,01fh add edx,ecx invoke crt_printf,addr szFmt,edx invoke ExitProcess,0 main ENDP END main |
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 |