是的,还有另一种方法,最初由Terje Mathiesen发明(至少我所知道的)。它不是通过除以10来实现的,而是通过(某种程度上)乘以倒数。当然,诀窍在于,在整数中无法直接表示倒数。为了弥补这一点,我们使用缩放整数进行计算。如果我们有浮点数,我们可以使用类似以下的方式提取数字:
input = 123
first digit = integer(10 * (fraction(input * .1))
second digit = integer(100 * (fraction(input * .01))
对于需要的位数,我们可以使用整数来实现,基本上只需将其乘以232(并向上取整,因为我们将使用截断数学)。在C语言中,该算法如下:
#include <stdio.h>
static const unsigned long long factors[] = {
3435973837,
2748779070,
2199023256,
3518437209,
2814749768,
2251799814,
3602879702,
2882303762,
2305843010
};
static const char shifts[] = {
3,
6,
9,
13,
16,
19,
23,
26,
29
};
int main() {
unsigned input = 13754;
for (int i=8; i!=-1; i--) {
unsigned long long inter = input * factors[i];
inter >>= shifts[i];
inter &= (unsigned)-1;
inter *= 10;
inter >>= 32;
printf("%u", inter);
}
return 0;
}
循环中的操作将直接映射到大多数32位处理器上的指令。您通常的乘法指令将使用2个32位输入,并产生一个64位结果,这正是我们需要的。它通常比除法指令快得多。在典型情况下,一些操作将(或至少可以通过一些小心)在汇编语言中消失。例如,在我执行
inter &= (unsigned)-1;
时,在汇编语言中,您通常只能使用存储结果的低32位寄存器,并忽略其余的上32位寄存器。同样,
inter >>= 32;
只是意味着我们使用上32位寄存器中的值,并忽略下32位寄存器中的值。
例如,在x86汇编语言中,这类似于:
mov ebx, 9
mov esi, offset output_buffer
next_digit:
mov eax, input
mul factors[ebx*4]
mov cl, shifts[ebx]
shrd eax, edx, cl
mov edx, 10
mul edx
add dl, '0'
mov [esi], dl
inc esi
dec ebx
jnz next_digit
mov [esi], bl
目前,我有点作弊,编写代码时假设每个表格(
factors
和
shifts
)的开头都有一个额外的项目。这并非绝对必要,但简化了代码,代价是浪费了8字节的数据。消除这种情况也很容易,但我暂时没有费心去做。
无论如何,消除除法使得许多缺乏专用除法硬件的低中档处理器速度明显加快。