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寄存器，然后累计除即可。
```ASM
.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`移位即可实现。
```ASM
.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` 次幂的计算过程.
```ASM
.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的次幂的情况下。对于其他情况，需要使用更为复杂的算法来完成除法计算。
```ASM
.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的次幂，则需要使用其他算法来计算除法运算。
```ASM
.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` 的计算流程。
```ASM
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`
```ASM
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模值，根据模值即可将对应的除法转换为乘法，一般写法如下:
```ASM
.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`。
以上步骤可以用以下公式来表示：
```c
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表示取余数。
需要注意，上述算法仅适用于除数为正数的情况。如果除数为负数，则需要先将除数取反，然后使用恒等式转化法的算法来计算除法运算，并最终再取反，以得到正确的计算结果。
```ASM
.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`，以得到正确的计算结果。
```ASM
.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的次幂，那么计算方式应该如下所示:
```ASM
.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 许可协议。转载请注明出处！
