使用位移位除以 10? [英] Divide by 10 using bit shifts?

问题描述

是否可以使用纯位移、加法、减法和也许乘法将一个无符号整数除以 10?使用资源非常有限且划分缓慢的处理器.

Is it possible to divide an unsigned integer by 10 by using pure bit shifts, addition, subtraction and maybe multiply? Using a processor with very limited resources and slow divide.

推荐答案

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

Editor's note: this is not actually what compilers do, and gives the wrong answer for large positive integers ending with 9, starting with div10(1073741829) = 107374183 not 107374182. It is exact for smaller inputs, though, which may be sufficient for some uses.

编译器(包括 MSVC)确实对常数除数使用定点乘法逆运算，但它们使用不同的魔法常数并移动高半结果以获得所有可能输入的精确结果，匹配 C 抽象机需要.参见 Granlund &蒙哥马利关于算法的论文.

Compilers (including MSVC) do use fixed-point multiplicative inverses for constant divisors, but they use a different magic constant and shift on the high-half result to get an exact result for all possible inputs, matching what the C abstract machine requires. See Granlund & Montgomery's paper on the algorithm.

参见 为什么GCC 在实现整数除法时使用乘以奇怪的数? 以实际 x86 asm gcc、clang、MSVC、ICC 和其他现代编译器制作的示例.

See Why does GCC use multiplication by a strange number in implementing integer division? for examples of the actual x86 asm gcc, clang, MSVC, ICC, and other modern compilers make.

它比编译器使用的乘法+右移的精确除法还要快.

It's even faster than the exact division via multiply + right-shift that compilers use.

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

You can use the high half of a multiply result for divisions by small integral constants. Assume a 32-bit machine (code can be adjusted accordingly):

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

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

What's going here is that we're multiplying by a close approximation of 1/10 * 2^32 and then removing the 2^32. This approach can be adapted to different divisors and different bit widths.

这对 ia32 架构非常有效，因为它的 IMUL 指令会将 64 位产品放入 edx:eax，并且 edx 值将是想要的值.Viz(假设红利在 eax 中传递，商在 eax 中返回)

This works great for the ia32 architecture, since its IMUL instruction will put the 64-bit product into edx:eax, and the edx value will be the wanted value. Viz (assuming dividend is passed in eax and quotient returned in eax)

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

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

Even on a machine with a slow multiply instruction, this will be faster than a software or even hardware divide.

这篇关于使用位移位除以 10?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！