将整数除以3的最快方法是什么？

Question

int x = n / 3;  // <-- make this faster

// for instance

int a = n * 3; // <-- normal integer multiplication

int b = (n << 1) + n; // <-- potentially faster multiplication

Answer 1

那个说"把它交给编译器"的人是对的,但我没有"声誉"来修改他或评论.我问gcc编译int test(int a){return a/3; 对于ix86然后反汇编输出.仅仅为了学术兴趣,它正在做的是大致乘以0x55555556,然后取64位结果的前32位.您可以通过以下方式证明这一点:

$ ruby -e 'puts(60000 * 0x55555556 >> 32)'
20000
$ ruby -e 'puts(72 * 0x55555556 >> 32)'
24
$ 

关于蒙哥马利分部的维基百科页面很难阅读,但幸运的是,编译人员已经完成了这一点,所以你不必这样做.

Answer 2

这是最快的,因为编译器可以根据输出处理器进行优化.

int a;
int b;

a = some value;
b = a / 3;

Answer 3

如果您知道值的范围,有一种更快的方法,例如,如果您将有符号整数除以3并且您知道要分割的值的范围是0到768,那么您可以将它相乘通过一个因子并将其向左移动2倍,该因子除以3.

例如.

范围0 - > 768

你可以使用10位的乘法,乘以1024,你想要除以3,所以你的乘数应该是1024/3 = 341,

所以你现在可以使用(x*341)>> 10
(如果使用有符号整数,确保移位是有符号的移位),同时确保移位实际上是移位而不是ROLL

这将有效地划分值3,并且在标准x86/x64 CPU上将以约为自然除法的速度的1.6倍运行.

当然,当编译器不能进行这种优化的唯一原因是因为编译器不知道X的最大范围因此无法做出这个决定,但是你作为程序员可以.

有时甚至可能更有利的是将值移动到更大的值然后执行相同的操作,即.如果你有一个全范围的int你可以使它成为一个64位的值,然后进行乘法和移位而不是除以3.

最近我不得不这样做以加速图像处理,我需要找到3个颜色通道的平均值,每个颜色通道都有一个字节范围(0 - 255).红绿蓝.

起初我只是简单地使用:

avg =(r + g + b)/ 3;

(因此r + g + b的最大值为768,最小值为0,因为每个通道的字节数为0 - 255)

经过数百万次迭代后,整个操作耗时36毫秒.

我把线改为:

avg =(r + g + b)*341 >> 10;

而这一点将它降低到了22毫秒,这可以通过一点巧思来实现.

这种加速发生在C#中,即使我已经启用了优化并且本机运行该程序而没有调试信息而不是通过IDE.

Answer 4

有关如何更有效地除以3的扩展讨论,请参见如何除以3,重点是进行FPGA算术运算.

也相关:

• 使用C#中的乘法移位优化整数除法

Answer 5

根据您的平台和C编译器的不同,本机解决方案就像使用一样

y = x / 3

可以很快或者速度非常慢(即使除法完全在硬件中完成,如果使用DIV指令完成,该指令比现代CPU上的乘法慢大约3到4倍).打开优化标志的非常好的C编译器可以优化此操作,但如果您想确定,最好自己优化它.

为了优化,重要的是具有已知大小的整数.在C int中没有已知的大小(它可能因平台和编译器而异!),因此您最好使用C99固定大小的整数.下面的代码假设您要将无符号的32位整数除以3,并且C编译器知道64位整数(注意:即使在32位CPU架构上,大多数C编译器也可以处理64位整数):

static inline uint32_t divby3 (
    uint32_t divideMe
) {
    return (uint32_t)(((uint64_t)0xAAAAAAABULL * divideMe) >> 33);
}

虽然这听起来很疯狂,但上面的方法确实除以3.它所需要的只是一个64位乘法和一个移位(就像我说的,乘法可能比CPU上的除法快3到4倍) ).在64位应用程序中,此代码将比32位应用程序快得多(在32位应用程序中,将两个64位数字相乘,在32位值上进行3次乘法和3次加法) - 但是,它可能仍然比在32位机器上划分.

另一方面,如果您的编译器非常好并且知道如何通过常量优化整数除法(最新的GCC,我刚刚检查过),它将生成上面的代码(GCC将为此创建完整的代码)如果您至少启用优化级别1,则为"/ 3".对于其他编译器......你不能依赖或期望它会使用这样的技巧,即使这种方法有很好的记录并且在因特网上随处可见.

问题是它只适用于常数,而不适用于变量.你总是需要知道幻数(这里是0xAAAAAAA)和乘法后的正确操作(大多数情况下是移位和/或加法),两者都有所不同,具体取决于你想要除以的数字,两者都占用了太多的CPU时间.在运行中计算它们(这将比硬件部分慢).但是,编译器很容易在编译期间计算它们(其中一秒或多或少的编译时间几乎不起作用).

Answer 6

对于 64 位数字：

uint64_t divBy3(uint64_t x)
{
    return x*12297829382473034411ULL;
}

然而，这不是您可能期望的截断整数除法。如果数字已经可以被 3 整除，它可以正常工作，但如果不是，它会返回一个巨大的数字。

例如，如果你在 11 上运行它，它返回 6148914691236517209。这看起来像一个垃圾，但实际上是正确的答案：乘以 3，你得到 11！

如果您正在寻找截断除法，则只需使用 / 运算符。我非常怀疑你能得到比这快得多的速度。

理论：

64 位无符号算术是模 2^64 算术。这意味着对于每个与 ​​2^64 模数（基本上都是奇数）互质的整数，存在一个乘法逆，您可以用它来乘以而不是除法。这个幻数可以通过3*x + 2^64*y = 1使用扩展欧几里得算法求解方程来获得。