匯編語(yǔ)言中關(guān)于32bit整數(shù)除法的快速實(shí)現(xiàn)

眾所周知在Intel80x86指令集中有div這么一條指令,在32bit下,其功能是把edx,eax組成的64bit無(wú)符號(hào)整數(shù)(edx高32bit,eax低32bit)除以原32bit操作數(shù),商放入eax中,余數(shù)放入edx中,但是在很多情況下我們的被除數(shù)只有32bit,除數(shù)是一個(gè)固定的值,此時(shí)如果還使用div指令,會(huì)使程序運(yùn)行效率下降,我為此想到一種方法,可以比通常的div指令在時(shí)間上快很多,具體的實(shí)現(xiàn)原理很簡(jiǎn)單,我們可以使用mul指令來(lái)代替div指令,要知道m(xù)ul的執(zhí)行所消耗的cpu周期大大低于div指令所消耗的,那如何做呢?

我們回想我們上小學(xué)的時(shí)候,老師們就講過(guò)除以一個(gè)數(shù)等于乘以這個(gè)數(shù)的倒數(shù),對(duì),就是這個(gè)簡(jiǎn)單的法則!但一個(gè)問(wèn)題又來(lái)了,一個(gè)大于1的整數(shù)的倒數(shù)小于1啊,是小數(shù)啊,而mul指令只能做無(wú)符號(hào)整數(shù)乘法啊.這的確是個(gè)問(wèn)題,但我有很好的解決方法,我一切的思想都是從二進(jìn)制出發(fā)的,但為此我們最多只能完成32bit除以32bit了.

現(xiàn)在我們假設(shè)235/10,對(duì)應(yīng)的二進(jìn)制表達(dá)就是11101011b/1010b,此時(shí)我們用mul來(lái)實(shí)現(xiàn),我們先求出10的倒數(shù)1/10,1/10=0.000110011001100110011001100......b,是小數(shù)怎么辦呢?我們可以把她變成整數(shù),為了得到更精確的結(jié)果,我們?nèi)【�度最高�?2bit整數(shù)110011001100...1101(0xCCCCCCCD),相當(dāng)于左移了35位,這樣結(jié)果很明顯也左移的35位,我們發(fā)現(xiàn)本來(lái)左移35位后0位應(yīng)該是0啊?怎么是1呢,這主要是從精度上考慮,我們可以忍受結(jié)構(gòu)比實(shí)際的大這么一點(diǎn)點(diǎn),因?yàn)榭梢允褂胊nd指令來(lái)屏蔽掉,得到正確的商,但如果結(jié)果小于了,那就沒(méi)辦法了.

說(shuō)這么多我們來(lái)看看具體的程序,我采用把32bit無(wú)符號(hào)數(shù)轉(zhuǎn)換為10進(jìn)制字符串輸出的函數(shù)為例子來(lái)說(shuō)明這個(gè)方法的優(yōu)越性.

這是通常的方法:

printfd proc UnInteger,lpBuff

xor edx,edx

mov ecx,10

mov edi,lpBuff

mov eax,UnInteger

add edi,10

mov byte ptr[edi],dl

@@:

div ecx

dec edi

or edx,30h

mov [edi],dl

xor edx,edx

test eax,eax

jnz @b

mov eax,edi;此時(shí)eax為轉(zhuǎn)換后的字符串首地址

ret

printfd endp

下面是改進(jìn)的方法:

printfd proc UnInteger,lpBuff

mov esi,lpBuff

mov eax,UnInteger

add esi,10

mov ecx,0CCCCCCCDh

mov byte ptr[esi],0

@@:

mov ebx,eax

mul ecx

mov eax,edx

and edx,-8;屏蔽誤差

shr eax,3

sub ebx,eax

sub ebx,eax

sub ebx,edx

or ebx,30h

dec esi

mov [esi],bl

test eax,eax

jnz @b

mov eax,esi;此時(shí)eax為轉(zhuǎn)換后的字符串首地址

ret

printfd endp

經(jīng)過(guò)我的測(cè)試,第二個(gè)的處理時(shí)間大約為第一個(gè)的1/3,當(dāng)然是在處理同一個(gè)數(shù)的情況下.