打开网站notfound,php源码下载网站,人才网招聘找工作,南通网站建设.通常情况下计算除法会使用div/idiv这两条指令#xff0c;该指令分别用于计算无符号和有符号除法运算#xff0c;但除法运算所需要耗费的时间非常多#xff0c;大概需要比乘法运算多消耗10倍的CPU时钟#xff0c;在Debug模式下#xff0c;除法运算不会被优化#xff0c;但…通常情况下计算除法会使用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寄存器然后累计除即可。
.datax DWORD ?y DWORD ?szFmt BYTE 计算结果: %d,0dh,0ah,0
.codemain PROCmov dword ptr ds:[x],1000mov dword ptr ds:[y],20; 计算 x / ymov eax,dword ptr ds:[x] ; eax 1000cdq ; 把eax的第31bit复制到edx的每个bit上idiv dword ptr ds:[y] ; eax x / yinvoke crt_printf,addr szFmt,eaxmain ENDP
END main8.2 除数为正2的次幂(无符号)
如果除数是正数被除数也是正数且除数的范围是正2的次幂那么我们就可以使用sar算数右移指令来替代div除法指令通过改变2的次幂的移位次数即可实现无符号除法的高速运算。
计算时我们需要参考次方表,这里我列举出几个常用的次方数值: 次方表: 12 24 38 416 532 664 7128次方表: 8256 9512 101024 112048 124096 138192 1416384
以下代码中分别演示了除数为2/4/8三种计算方式计算结果只需sar移位即可实现。
.datax DWORD ?szFmt BYTE 计算结果: %d,0dh,0ah,0
.codemain PROCmov dword ptr ds:[x],5; ----------------------------------------------------; 【除数为2】; 被除数为正数(无需扩展): eax 5 / 2 2mov eax,dword ptr ds:[x] ; 被除数sar eax,1 ; 算数右移1位invoke crt_printf,addr szFmt,eax; ----------------------------------------------------; 【除数为4】; 被除数为正数(无需扩展): eax 5 / 4 1mov eax,dword ptr ds:[x]sar eax,2 ; 算数右移2位invoke crt_printf,addr szFmt,eax; ----------------------------------------------------; 【除数为8】; 被除数为正数(无需扩展): eax 5 / 8 0mov eax,dword ptr ds:[x]sar eax,3 ; 算数右移3位invoke crt_printf,addr szFmt,eaxinvoke ExitProcess,0main ENDP
END main8.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 次幂的计算过程.
.datax DWORD ?szFmt BYTE 计算结果: %d,0dh,0ah,0
.codemain PROCmov dword ptr ds:[x],10; 除数为(有符号)负2的次幂的计算过程; 计算 10 / -2mov eax,dword ptr ds:[x] ; x 10cdq ; 符号扩展 [edx:eax]sub eax,edx ; 减去符号位sar eax,1 ; eax 10 / -2neg eax ; 将正数 eax 翻转为负数 -5invoke crt_printf,addr szFmt,eax; 计算 10 / -4mov eax,dword ptr ds:[x] ; x 10cdqand edx,3add eax,edxsar eax,2 ; eax 10 / -4neg eax ; eax -2invoke crt_printf,addr szFmt,eax; 计算 10 / -8mov eax,dword ptr ds:[x]cdqand edx,7add eax,edxsar eax,3neg eaxinvoke crt_printf,addr szFmt,eaxinvoke ExitProcess,0main ENDP
END main8.4 被除数为负数(有符号)
在有符号数的除法中如果被除数为负数而除数是正2的次幂那么可以使用neg取反操作来得到正确的计算结果。具体步骤如下
首先将被除数的绝对值与除数进行除法运算并得到正确的商。如果被除数为负数则对商进行取反操作。如果除数为负数则最终结果也要进行取反操作。
例如假设要计算-27除以8的值我们可以按照如下步骤进行计算
计算27除以8的值得到商3和余数3。因为被除数为负数所以对商取反得到-3。因为除数为正数所以最终结果为-3即-27/8的计算结果。
类似地如果除数为负数我们需要在得到正确的计算结果后再进行一次取反操作这样才能得到真正的结果。需要注意的是上述方法仅适用于除数为正2的次幂的情况下。对于其他情况需要使用更为复杂的算法来完成除法计算。
.datax DWORD ?y DWORD ?szFmt BYTE 计算结果: %d,0dh,0ah,0
.codemain PROCmov dword ptr ds:[x],-10mov dword ptr ds:[y],-5; 被除数为(有符号)的计算过程; 计算 -10 / 2mov eax,dword ptr ds:[x]cdqsub eax,edxsar eax,1 ; eax -10 / 2invoke crt_printf,addr szFmt,eax; 计算 -5 / 4mov eax,dword ptr ds:[y]cdqxor edx,edxadd eax,edxsar eax,2 ; eax -5 / 4invoke crt_printf,addr szFmt,eax; 计算 -10 / 8mov eax,dword ptr ds:[x]cdq ; 位扩展xor edx,edx ; 清空高位add eax,edxsar eax,3 ; eax -10 / 8invoke crt_printf,addr szFmt,eaxinvoke ExitProcess,0main ENDP
END main8.5 除数与被除数均为负数(有符号)
在有符号数的除法中如果除数和被除数均为负数且除数为负2的次幂可以使用算数右移指令sar来完成除法运算然后通过取反指令neg来翻转得到的计算结果的符号位。
具体来说一个有符号整数除以负2的次幂等价于这个有符号整数右移除数的位数作为移位数然后转为无符号数进行运算再将得到的无符号数转回符号位正确的有符号数即可。由于右移的操作是算数右移所以被移位的符号位会被保留。
例如将-16除以-8即计算-16/-8的结果因为8是2的3次幂所以我们可以通过算数右移指令来完成除法然后再取反获得正确的结果
将-16右移3位得到-2。对-2进行取反得到2。
因为-16和-8均为负数所以最终结果也要进行一次取反操作。因此得到的结果为-2。
需要注意的是上述方法仅适用于除数为负2的次幂如果除数不是负2的次幂则需要使用其他算法来计算除法运算。
.datax DWORD ?y DWORD ?z DWORD ?szFmt BYTE 计算结果: %d,0dh,0ah,0
.codemain PROCmov dword ptr ds:[x],-5mov dword ptr ds:[y],-24mov dword ptr ds:[z],-10; 如果同时为负数的情况; 计算 -5 / -2mov eax,dword ptr ds:[x]cdq ; 符号扩展xor edx,edx ; 清空高位add eax,edxsar eax,1 ; 算数右移动 -5 / -2neg eax ; eax 3 (负负得正)invoke crt_printf,addr szFmt,eax; 计算 -24 / -4mov eax,dword ptr ds:[y]cdq ; 符号扩展xor edx,edx ; 清空高位add eax,edxsar eax,2 ; 算数右移动 -24 / -4neg eax ; eax 6 (负负得正)invoke crt_printf,addr szFmt,eax; 计算 -10 / -8mov eax,dword ptr ds:[z] ; z -10 cdq ; 符号扩展xor edx,edx ; 清空高位add eax,edxsar eax,3 ; eax -10 / -8 neg eax ; eax 1 (负负得正)invoke crt_printf,addr szFmt,eaxinvoke ExitProcess,0main ENDP
END main如上我们所有的除法运算中无论是有符号还是无符号都在进行2的次幂运算通常针对2的次幂运算并不需要经过特殊的模M计算而对于非2次幂3/5/7的运算则需要通过一定的公式才能简化计算过程如下将开始介绍非2次幂除法运算该如何优化。
8.6 除数为正非2次幂(有符号)
对于除数为正非2次幂的有符号数我们需要使用其他的算法来完成除法运算。通常情况下可以使用恒等式转化法或移位除法来进行计算。
一种常用的移位除法算法是:
将被除数与除数分别取绝对值并记录下符号。如果除数大于被除数则直接返回0。通过不断将除数左移直到左移之后的除数大于等于被除数得到最高位的不为0的位数记为n。将除数左移n位然后不断依次将左移后的除数与被除数相减直到被除数小于除数。记录下相减的次数即为最终的商。
上述算法仅适用于除数为正数的情况。如果除数为负数则需要先取反然后使用移位除法的算法来计算除法运算并最终再取反以得到正确的计算结果。
关于求解公式2^(32n) / M的使用方法可以通过移位和除法结合的方法来计算具体可以按照以下步骤进行计算
将除数M保存在寄存器中将32n的值保存在寄存器中。执行左移指令将32n左移至最高位。将左移后的值保存在另一个寄存器中。执行除法指令将左移后的值除以M得到商和余数。如果余数不为0则重新计算32n1的值再次执行上述步骤。
这样不断重复这个过程就可以计算出2^(32n) / M的结果。
先来看一段汇编代码我们此时已知 M 055555556h 且 edx N 带入公式 2^(32N) / 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模值根据模值即可将对应的除法转换为乘法一般写法如下:
.datax DWORD ?szFmt BYTE 计算结果: %d,0dh,0ah,0
.codemain PROCmov dword ptr ds:[x],10; 除法(无符号)非2的幂转换为乘法; 计算 10 / 3mov ecx,dword ptr ds:[x] ; 被除数 ecx 10 / 3 3mov eax,055555556h ; eax M值 1431655766imul ecxmov eax,edx ; edx n 计算: 2^(32n) / Mshr eax,01fh ; 计算出除数为 2.9999 3add edx,eaxinvoke crt_printf,addr szFmt,edx; 计算 10 / 5mov ecx,dword ptr ds:[x] ; ecx 10 / 5 2mov eax,066666667h ; 此处的M模值是编译器计算后得到的imul ecxsar edx,1 ; 想要知道除数是多少,只需要mov eax,edx ; 2^(32 edx) / M 2^33 / 66666667 5shr eax,01fh ; 逻辑右移add edx,eaxinvoke crt_printf,addr szFmt,edx; 计算 10 / 6mov ecx,dword ptr ds:[x] ; ecx 10 / 6 1mov eax,02AAAAAABh ; eax 715827883imul ecxmov eax,edx ; 2^(32 edx) / M 2^32 / 2AAAAAAB 6shr eax,01fhadd edx,eaxinvoke crt_printf,addr szFmt,edxinvoke ExitProcess,0main ENDP
END main8.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表示取余数。
需要注意上述算法仅适用于除数为正数的情况。如果除数为负数则需要先将除数取反然后使用恒等式转化法的算法来计算除法运算并最终再取反以得到正确的计算结果。
.datax DWORD ?y DWORD ?z DWORD ?szFmt BYTE 计算结果: %d,0dh,0ah,0
.codemain PROCmov dword ptr ds:[x],-5mov dword ptr ds:[y],10mov dword ptr ds:[z],20; 除法(无符号)非2的次幂(正数)转换为乘法xor edx,edxmov ecx,dword ptr ds:[y] ; ecx 10mov eax,0AAAAAAABh ; ecx / 3 3mul ecxshr edx,1invoke crt_printf,addr szFmt,edx; 还原除数: 2 ^(32 n) / M 2 ^ (322) / 0CCCCCCCDh 5xor edx,edxmov ecx,dword ptr ds:[y] ; ecx 10 计算: 10/5mov eax,0CCCCCCCDh ; eax Mmul ecxshr edx,2 ; edx ninvoke crt_printf,addr szFmt,edx; 还原除数: 2 ^(32 n) / M 2 ^ (322) / 0AAAAAAABh 6xor edx,edxmov ecx,dword ptr ds:[y] ; ecx 10 计算:10/6mov eax,0AAAAAAABh ; eax Mmul ecxshr edx,2 ; edx ninvoke crt_printf,addr szFmt,edx;还原除数: 2 ^(32 n) / M 2 ^ 33 / 038E38E39h 9xor edx,edxmov ecx,dword ptr ds:[z] ; ecx 20 计算: 20/9mov eax,038E38E39h ; eax Mmul ecxshr edx,1 ; edx ninvoke crt_printf,addr szFmt,edxinvoke ExitProcess,0main ENDP
END main8.8 除数为负非2次幂(无符号)
如果我们的除数是一个负数且范围是非2的次幂那么当我们计算结束后只需要在原来基础上多增加一个neg将结果翻转以下即可。
采用与有符号整数的移位除法类似的方法分为两个阶段完成。
阶段1将除数和被除数分别取绝对值并计算出商的符号。由于除数为负数所以商的符号为负号。阶段2使用移位除法算法详见上述有符号数除法的算法计算出无符号整数的商。
最后因为商为负数所以需要将其翻转一下即执行一次取反指令neg以得到正确的计算结果。
.datax DWORD ?y DWORD ?szFmt BYTE 计算结果: %d,0dh,0ah,0
.codemain PROCmov dword ptr ds:[x],10mov dword ptr ds:[y],20; 还原除数: 2 ^(32 n) / M 2 ^ 33 / 0AAAAAAABh nge(3) -3xor edx,edxmov ecx,dword ptr ds:[y] ; ecx 20 计算: 20 / -3mov eax,0AAAAAAABh ; eax Mmul ecxshr edx,1 ; edx n neg edx ; edx6 结果neg取反invoke crt_printf,addr szFmt,edx; 还原除数: 2 ^(32 n) / M 2 ^ 62 / 040000001h 4294967292xor edx,edxmov ecx,dword ptr ds:[x] ; ecx 10 计算: 10 / -3mov eax,040000001h ; eax Mmul ecxshr edx,01eh ; edx ninvoke crt_printf,addr szFmt,edxinvoke ExitProcess,0main ENDP
END main而如果反过来被除数变成负数而除数则还是非2的次幂那么计算方式应该如下所示:
.datax DWORD ?szFmt BYTE 计算结果: %d,0dh,0ah,0
.codemain PROCmov dword ptr ds:[x],-10; 除法(有符号)非2的幂转换为乘法mov ecx,dword ptr ds:[x] ; ecx -10 / 9 -1mov eax,038E38E39h ; eax 954437177 imul ecxsar edx,1 ; 2^(32 edx) / M 2^33 / 38E38E39 9mov ecx,edxshr ecx,01fhadd edx,ecxinvoke crt_printf,addr szFmt,edxinvoke ExitProcess,0main ENDP
END main本文作者 王瑞 本文链接 https://www.lyshark.com/post/1f99ad3b.html 版权声明 本博客所有文章除特别声明外均采用 BY-NC-SA 许可协议。转载请注明出处
