用位移除以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.

推荐答案

编者注:实际上，这不是编译器所做的，而是

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抽象机相匹配要求.参见格兰伦&关于算法的蒙哥马利论文.

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屋！