5.8 汇编语言:汇编高效除法运算

2023-10-11 14:55:07 浏览数 (1)

通常情况下计算除法会使用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寄存器,然后累计除即可。

代码语言:javascript复制
.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移位即可实现。

代码语言:javascript复制
.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 次幂的计算过程.

代码语言:javascript复制
.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的次幂的情况下。对于其他情况,需要使用更为复杂的算法来完成除法计算。

代码语言:javascript复制
.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的结果,因为823次幂,所以我们可以通过算数右移指令来完成除法,然后再取反获得正确的结果:

  • 将-16右移3位,得到-2。
  • 对-2进行取反,得到2。

因为-16-8均为负数,所以最终结果也要进行一次取反操作。因此,得到的结果为-2。

需要注意的是,上述方法仅适用于除数为负2的次幂,如果除数不是负2的次幂,则需要使用其他算法来计算除法运算。

代码语言:javascript复制
.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 的计算流程。

代码语言:javascript复制
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

代码语言:javascript复制
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模值,根据模值即可将对应的除法转换为乘法,一般写法如下:

代码语言:javascript复制
.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

以上步骤可以用以下公式来表示:

代码语言:javascript复制
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表示取余数。

需要注意,上述算法仅适用于除数为正数的情况。如果除数为负数,则需要先将除数取反,然后使用恒等式转化法的算法来计算除法运算,并最终再取反,以得到正确的计算结果。

代码语言:javascript复制
.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,以得到正确的计算结果。

代码语言:javascript复制
.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的次幂,那么计算方式应该如下所示:

代码语言:javascript复制
.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

本文作者: 王瑞 本文链接: https://www.lyshark.com/post/1f99ad3b.html 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!

0 人点赞