汇编语言中关于32bit整数除法的快速实现

众所周知在Intel80x86指令集中有div这么一条指令,在32bit下,其功能是把edx,eax组成的64bit无符号整数(edx高32bit,eax低32bit)除以原32bit操作数,商放入eax中,余数放入edx中,但是在很多情况下我们的被除数只有32bit,除数是一个固定的值,此时如果还使用div指令,会使程序运行效率下降,我为此想到一种方法,可以比通常的div指令在时间上快很多,具体的实现原理很简单,我们可以使用mul指令来代替div指令,要知道mul的执行所消耗的cpu周期大大低于div指令所消耗的,那如何做呢?

我们回想我们上小学的时候,老师们就讲过除以一个数等于乘以这个数的倒数,对,就是这个简单的法则!但一个问题又来了,一个大于1的整数的倒数小于1啊,是小数啊,而mul指令只能做无符号整数乘法啊.这的确是个问题,但我有很好的解决方法,我一切的思想都是从二进制出发的,但为此我们最多只能完成32bit除以32bit了.

现在我们假设235/10,对应的二进制表达就是11101011b/1010b,此时我们用mul来实现,我们先求出10的倒数1/10,1/10=0.000110011001100110011001100......b,是小数怎么办呢?我们可以把她变成整数,为了得到更精确的结果,我们取精度最高的32bit整数110011001100...1101(0xCCCCCCCD),相当于左移了35位,这样结果很明显也左移的35位,我们发现本来左移35位后0位应该是0啊?怎么是1呢,这主要是从精度上考虑,我们可以忍受结构比实际的大这么一点点,因为可以使用and指令来屏蔽掉,得到正确的商,但如果结果小于了,那就没办法了.

说这么多我们来看看具体的程序,我采用把32bit无符号数转换为10进制字符串输出的函数为例子来说明这个方法的优越性.

这是通常的方法:

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;此时eax为转换后的字符串首地址

ret

printfd endp

下面是改进的方法:

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;此时eax为转换后的字符串首地址

ret

printfd endp

经过我的测试,第二个的处理时间大约为第一个的1/3,当然是在处理同一个数的情况下.