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

那个说"把它交给编译器"的人是对的,但我没有"声誉"来修改他或评论.我问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
$ 

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

1> Martin Dorey..：

---

那个说"把它交给编译器"的人是对的,但我没有"声誉"来修改他或评论.我问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
$ 

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

---

如果你把它称为"倒数,存储在定点",这更容易理解

2> KPexEA..：

---

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

int a;
int b;

a = some value;
b = a / 3;

---

事实证明，无论知道什么值，编译器都会将其优化为类似于n * 0x55555556 >> 32

---

如果`a`是有符号类型,但已知为正数,则`(无符号)a/3`可能会更快,因为在划分有符号类型时,编译器将添加额外代码以确保负值产生截断 - 朝向 - 零结果而不是自然计算的分层结果.

3> Aaron Murgat..：

---

如果您知道值的范围,有一种更快的方法,例如,如果您将有符号整数除以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.

4> Jay..：

---

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

也相关:

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

---

我知道在一个古老的帖子上戳一下有点烦人,但你给的链接是***DEAD****(Aaaaaargh!)*(我的意思是第一个).

5> Mecki..：

---

根据您的平台和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时间.在运行中计算它们(这将比硬件部分慢).但是,编译器很容易在编译期间计算它们(其中一秒或多或少的编译时间几乎不起作用).

---

请不要这样做,让编译器去做.使用单个32位乘法,编译器将结果存储在寄存器中.也就是说,它将在多路溢出寄存器EDX中.因此,您的优化不是,现在您已将单个32位乘法转换为64位乘法和64位移位.

---

@Mecki:实际上,后者倾向于生成调用未定义行为的代码,然后当有人告诉他们他们错了时,他们会将手指放在耳朵里.我并不是说尝试编写快速"即使你的编译器很糟糕"的代码也不值得,但是这样做的人需要全面掌握C标准,未定义的行为,实现定义的行为,以及什么是有效的和便携的.