C++快速除法/ mod乘10 ^ x

Question

在我的程序中,我使用了很多整数除以10 ^ x和整数mod函数10.

例如:

unsigned __int64 a = 12345;
a = a / 100;
....

要么:

unsigned __int64 a = 12345;
a = a % 1000;
....

如果我要使用正确的位移>>,那么我将获得模式2^x,这不是我想要的.

有什么办法可以加速整数除法和mod函数的程序吗？

Answer 1

简答:没有

答案:不.

说明:
编译器已经为您优化了这样的语句.
如果有一种技术可以比整数除法更快地实现它,那么编译器已经知道它并将应用它(假设你打开优化).

如果您提供适当的体系结构标志,那么编译器甚至可能知道特定的快速体系结构特定的组件,这将为执行操作提供一个很好的技巧,否则它将为其编译的通用体系结构应用最佳技巧.

简而言之,编译器将在任何优化技巧中击败人类99.9999999%的时间(尝试记住添加优化标志和体系结构标志).所以你通常做的最好的事情就是编译器.

如果通过一些奇迹,你会发现一个尚未找到的与后端编译器团队密切合作的程序集中的方法.然后请让他们知道,下一版本的热门编译器将通过10个优化技巧更新为'未知(谷歌)'部门.

Answer 2

来自http://www.hackersdelight.org/divcMore.pdf

unsigned divu10(unsigned n) {
unsigned q, r;
q = (n >> 1) + (n >> 2);
q = q + (q >> 4);
q = q + (q >> 8);
q = q + (q >> 16);
q = q >> 3;
r = n - q*10;
return q + ((r + 6) >> 4);

}

Answer 3

这对于缺少任何div操作的环境非常有用,并且它比我的i7上的原生分区慢2倍(自然优化).

这是一个稍微快一点的算法版本,尽管仍有一些令人讨厌的舍入错误与负数.

static signed Div10(signed n)
{
    n = (n >> 1) + (n >> 2);
    n += n < 0 ? 9 : 2;
    n = n + (n >> 4);
    n = n + (n >> 8);
    n = n + (n >> 16);
    n = n >> 3;
    return n;
}

由于此方法适用于32位整数精度,因此如果您在8位或16位环境中工作,则可以优化大多数这些移位.

Answer 4

换句话说,在汇编程序中编写正确版本的Div#n#可能更有意义.编译器不能总是有效地预测最终结果(尽管在大多数情况下,他们做得相当好).因此,如果您在低级微芯片环境中运行,请考虑手写asm例程.

#define BitWise_Div10(result, n) {      \
    /*;n = (n >> 1) + (n >> 2);*/           \
    __asm   mov     ecx,eax                 \
    __asm   mov     ecx, dword ptr[n]       \
    __asm   sar     eax,1                   \
    __asm   sar     ecx,2                   \
    __asm   add     ecx,eax                 \
    /*;n += n < 0 ? 9 : 2;*/                \
    __asm   xor     eax,eax                 \
    __asm   setns   al                      \
    __asm   dec     eax                     \
    __asm   and     eax,7                   \
    __asm   add     eax,2                   \
    __asm   add     ecx,eax                 \
    /*;n = n + (n >> 4);*/                  \
    __asm   mov     eax,ecx                 \
    __asm   sar     eax,4                   \
    __asm   add     ecx,eax                 \
    /*;n = n + (n >> 8);*/                  \
    __asm   mov     eax,ecx                 \
    __asm   sar     eax,8                   \
    __asm   add     ecx,eax                 \
    /*;n = n + (n >> 16);*/                 \
    __asm   mov     eax,ecx                 \
    __asm   sar     eax,10h                 \
    __asm   add     eax,ecx                 \
    /*;return n >> 3;}*/                    \
    __asm   sar     eax,3                   \
    __asm   mov     dword ptr[result], eax  \
}

用法:

int x = 12399;
int r;
BitWise_Div10(r, x); // r = x / 10
// r == 1239

再一次,只是一个注释.这更适用于确实存在严重分裂的芯片.在现代处理器和现代编译器上,部门通常以非常聪明的方式进行优化.

Answer 5

除非您的体系结构支持二进制编码的十进制，即使这样也只有大量的汇编混乱。