如何降低2^n + 1除法的复杂度？

Question

我需要在代码的热路径中执行一些整数除法。通过分析和计数周期，我已经确定了整数除法的成本。我希望有办法将这些除法强化以降低成本。

在这个路径中，我正在除以2^n+1，其中n是可变的。本质上，我想优化此函数以消除除法运算符：

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

如果我要进行2^n的除法，我可以将div更换为右移n位的操作。如果我要进行常量除法，我会让编译器对该特定除法进行强化优化，很可能会将其转化为一个乘法和一些移位操作。

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

编辑：这里的a可以是任意64位整数，n只取介于10到25之间的几个值。我当然可以为每个n预先计算一些值，但对于a则无能为力。

- J.S.

---

a和n的值有任何限制吗？ - The Archetypal Paul

你调用这个函数的上下文是什么？ - GManNickG

@JR，我认为移位不是问题所在——只有一条指令。而除法才是需要时间的操作。 - The Archetypal Paul

如果a是一个64位整数，你应该声明它为这样。unsigned long只保证有32位。使用uint64_t或uint_least64_t来表示它。对于1 << n，如果你的n可能会到达31，那么你可能会有未定义的行为。请改用UINT64_C(1) << n。 - Jens Gustedt

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);
    }
}

现在每个除法都是通过一个常数进行的，编译器通常会将其简化为一系列乘/移位/加操作（如问题所述）。有关详细信息，请参见C/C++编译器是否将常数除以2的幂的优化转换为移位操作？

- Michael Burr

---

值得一试，但你要权衡的是不可预测的跳转和移位+除法指令与等效强度降低除法之间的差异。有什么好的平衡点吗？ - Steve Jessop

+1，有道理；尽管您可能希望进行基准测试以确认实现switch()所需的间接引用和/或条件分支实际上比整数除法更快... - David Gelhar

你甚至可以设置一个默认值来处理一般情况。 - GManNickG

你正在对 int 执行 << 操作。这是不好的，因为在一个具有 32 位 int 的平台上，这将导致未定义的行为。请改用 1UL << something 而不是 1 << something。 - Jens Gustedt

此外，一个小帮助是将(1 << n) + 1写成(1ul << n) | 1ul，因为表达式的所有值都以1结尾。 - Ed.C

Answer 2

您可以通过使用魔术数和移位的乘法（模wordsize）来替换整数除法。已知常量的魔术数可以预先计算。由于n的取值范围有限，例如0..31，因此很容易为所有n预先计算这些魔术数，并将其存储在一个包含32个元素的表中。Javascript Page for calculating the magic numbers。如果除数在编译时是常量，则良好的编译器可以计算魔术数并将整数除法替换为乘法和移位。根据代码在性能关键代码周围的结构如何，您可以使用宏或内联技巧展开所有可能的n值，并让编译器完成查找魔术数字的工作（类似于带有switch的答案，但我会将更多代码放在常量区域中，否则可能是一种不值得的权衡-分支也可能会影响性能）。详细描述以及用于计算魔术数的代码可以在Henry S. Warren, Jr.的书籍“Hackers Delight”中找到（强烈推荐必备书籍！）第180页及以下。

相关章节的谷歌图书链接：

第10-9章 除数大于等于1的无符号除法

- Peer Stritzinger