我怎样才能将分裂强度降低2 ^ n + 1？

Question

我需要在代码的热路径中执行一些整数除法.我已经通过分析和循环计数确定了整数除法对我造成的损失.我希望我能做些什么来强化将分裂降低到更便宜的东西.

在这条路径中,我除以2 ^ n + 1,其中n是可变的.基本上我想优化此函数以删除除法运算符:

unsigned long compute(unsigned long a, unsigned int n)
{
    return a / ((1 << n) + 1);
}

如果我除以2 ^ n,我只需用右移n替换div.如果我用常数除法,我会让编译器强度减少那个特定的除法,可能会把它变成乘法和一些变化.

是否存在适用于2 ^ n + 1的类似优化？

编辑:这里可以是任意64位整数.n只取10和25之间的几个值.我当然可以为每个n预先计算一些值,但不能为a计算.

Answer 1

由于您只能移动int很多地方,因此可以通过常量将所有这些情况选择为多个部分中的一个:

unsigned long compute(unsigned long a, unsigned int n)
{
    // assuming a 32-bit architecture (making this work for 64-bits 
    // is left as an exercise for the reader):
    switch (n) {
        case  0: return a / ((1 << 0) + 1);
        case  1: return a / ((1 << 1) + 1);
        case  2: return a / ((1 << 2) + 1);

            // cases 3 through 30...

        case 31: return a / ((1 << 31) + 1);
    }
}

所以现在每个除法都是一个常数,编译器通常会减少到一系列乘法/移位/加法指令(如上所述).请参阅ac/c ++编译器是否将两次幂值的常量除法优化为班​​次？对于deatils.

Answer 2

你可以用一个常数替换整数除法,乘以一个幻数和一个移位乘以(模数词大小).

可以针对已知常数预先计算幻数.

由于n不能采用多个值,例如0..31,因此为所有n预先计算这些幻数并"存储"在具有32个元素的表中是"容易的".

用于计算幻数的Javascript页面

如果除数在编译时是常数,那么一个好的编译器可以计算幻数并通过乘法和移位替换整数除法.根据围绕性能关键代码构建其余代码的方式,您可以使用宏或内联技巧来展开n的所有可能值,并让编译器完成查找幻数的工作(类似于交换机的答案) ,但是我会把更多的代码放在常量区域,否则它可能是一个不值得的交易 - 分支也会花费你的性能)

详细描述以及用于计算幻数的代码可以在Henry S. Warren,Jr.的书"Hackers Delight"中获得资金(强烈推荐必须有书!)pp.180ff.

链接到相关章节的Google图书:

第10-9章除数的无符号除法> = 1