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