math - 使用位移位除以 10？

Question

是否可以通过使用纯位移位、加法、减法和乘法来将无符号整数除以 10？使用资源非常有限且划分缓慢的处理器。

Answer 1

编者注:这实际上不是编译器所做的，并且对于以 9 结尾、以 div10(1073741829) = 107374183 开头的大正整数给出了错误的答案。 107374182(Godbolt)。不过，对于小于 0x40000005 的输入来说，它是准确的，这对于某些用途来说可能就足够了。

编译器(包括 MSVC)确实使用常量除数的定点乘法逆元，但它们使用不同的魔术常数并在高半结果上移位以获得所有可能输入的精确结果，与 C 抽象机的结果相匹配需要。请参阅Granlund & Montgomery's paper关于算法。

参见Why does GCC use multiplication by a strange number in implementing integer division?有关实际 x86 asm gcc、clang、MSVC、ICC 和其他现代编译器 make 的示例。

<小时/>

这是一种快速近似，对于大输入来说并不精确

它甚至比编译器使用的通过乘法 + 右移进行的精确除法还要快。

您可以使用乘法结果的高半部分除以小整数常量。假设是32位机器(代码可以相应调整):

int32_t div10(int32_t dividend)
{
    int64_t invDivisor = 0x1999999A;
    return (int32_t) ((invDivisor * dividend) >> 32);
}

这里我们乘以 1/10 * 2^32 的近似值，然后删除 2^32。这种方法可以适应不同的除数和不同的位宽度。

这对于 ia32 架构非常有用，因为它的 IMUL 指令会将 64 位乘积放入 edx:eax 中，而 edx 值将是所需的值。 Viz(假设被除数在 ecx(fastcall)中传递，商在 eax 中返回)

div10 proc 
    mov    eax,1999999Ah    ; 1/10 * 2^32
    imul   ecx              ; edx:eax = dividend / 10 * 2 ^32
    mov    eax,edx          ; eax = dividend / 10
    ret
endp

即使在具有缓慢乘法指令的机器上，这也会比软件甚至硬件除法更快。