什么是将整数除以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

- Greg Dean

Answer 1

那个说“交给编译器”的人是正确的，但我没有足够的“声望”来赞同他或发表评论。我让gcc为ix86编译int test(int a) { return a / 3; }，然后反汇编输出。仅出于学术兴趣，它所做的是大致乘以0x55555556，然后取该结果的64位结果的前32位。您可以使用以下示例演示此操作：

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

维基百科上的蒙哥马利除法页面很难阅读，但幸运的是，编译器开发人员已经为您完成了这项工作。

- Martin Dorey

---

如果你把它称为“固定点存储的倒数”，那么这个概念会更容易理解。 - Ben Voigt

这不是蒙哥马利除法，更像是巴雷特约简背后的思想。 - Kyle Butt

在我看来，这绝对是最好的答案。而且我喜欢它选择精度的简单易用性。例如，我需要一个适用于8位输入的解决方案。很简单：(x * 0x56) >> 8; - All The Rage

@AlltheRage (x * 0x56) >> 8 不适用于8位输入。例如，251*86/256 = 84，这听起来不太对。 - jpalecek

我想我说错了，因为我的数字范围实际上只有6位，但是它们存储在8位中。要使其适用于所有8位数字，只需选择更多的精度即可。例如，这样可以运行：（x * 0x556）>> 12 - All The Rage

Answer 2

如果编译器可以，它会进行优化，这是最快的方法。

int a;
int b;

a = some value;
b = a / 3;

- KPexEA

---

这恐怕也是我所想的。 - Greg Dean

转念一想，我认为你想说的是以下内容。如果“某个值”事先已知，编译器将优化对某个值/3的评估。然而，我对在运行时确定某个值的情况感兴趣。 - Greg Dean

事实证明，即使某个值已知，编译器也会将其优化为类似于“n * 0x55555556 >> 32”的形式。 - Greg Dean

通常来说，最直接的方式往往是最好的，不是吗？ - mxg

如果a是有符号类型，但已知为正数，则(unsigned)a/3可能更快，因为在除以有符号类型时，编译器会添加额外的代码以确保负值产生截断向零结果，而不是自然计算的向下取整除法结果。 - supercat

我认为像“让编译器自己处理”这样的回答太轻率了，因为在现代，大多数会问这种问题的人是编译器编写者、硬件设计师或发现编译器做得很糟糕的人。基本上，我们应该尊重在这里发帖提问的人。他们通常需要一个经过深思熟虑的答案。（尽管我承认提供所有可能的好答案，包括轻率的回答，可能更有帮助。） - All The Rage

Answer 3

如果您知道数值的范围，例如，如果您正在将有符号整数除以3，并且您知道要除以的值的范围为0到768，则可以通过乘以一个因子并将其左移2的该因子除以3的幂次方来加快速度。

例如：

范围为0 -> 768

您可以使用10位移位，即乘以1024，您想要除以3，因此您的乘数应为1024/3 = 341，

因此，您现在可以使用(x * 341)>> 10
（如果使用有符号整数，请确保移位是有符号移位），还请确保移位实际上是移位而不是位ROLL。

这将有效地将值除以3，并且在标准x86 / x64 CPU上运行的速度约为自然除以3的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毫秒，简直令人惊叹。

尽管我已经打开了优化并在本地环境中运行程序，而非通过IDE进行调试且不加载调试信息，但是这种加速仍然出现在C#中。

- Aaron Murgatroyd

---

感谢您的详细解释。直到现在我才明白了重点。 - Timo

不错！我有一个除以5的问题，我对此非常挑剔——平均像素及其北、南、西、东邻居的rgba值（穷人版的快速模糊）。我采用了一个好的近似值，使用比例50/256，约为0.195。它很漂亮，你可以计算时钟周期。p[i] = ((a << 5) + (a << 4) + (a << 1) + a) >> 8; - Nolo

这个不行。将3乘以341得到1023。将其向右移动10位会得到零，而不是你从“3/3”中期望的那个一。实际上，它会导致所有三的整数倍的问题。 - paxdiablo

@paxdiablo，你发现得好，看起来这个问题没有经过彻底的测试。对于小于2048的数字，实际上需要执行x * 683 >> 11。乘以342并移位10可能更接近341，但也只适用于小于512的值。 - Jeff Brower

已经过去了十二年，我仍然在这里着陆。这是一个很好的答案，适用于那些极少数需要的情况，比如在没有整数除法的微控制器上计算微秒。 - undefined

Answer 4

请参阅《如何更高效地进行FPGA算术运算——除以3篇》，其中讨论了如何更高效地进行除以3操作。

另外，以下内容也与此相关：

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

- Jay

---

相当酷的东西，不过我应该指定我被限制在 x86-ish 的东西上。 - Greg Dean

我知道翻看古老的帖子有点让人心烦，但是你给的链接已经挂了（啊啊啊！）（我指的是第一个链接）。 - Hungry Blue Dev

Answer 5

根据您的平台和C编译器不同，像只使用本地解决方案这样的方法可能会有所不同。

y = x / 3

可以快速或者非常慢（即使在硬件上进行除法运算，如果使用DIV指令，该指令在现代CPU上的速度大约比乘法慢3到4倍）。非常好的带有优化标志的C编译器可能会优化此操作，但是如果想确保，最好自己进行优化。

对于优化，重要的是具有已知大小的整数。在C中，int没有已知的大小（它可以因平台和编译器而异！），因此最好使用C99固定大小的整数。下面的代码假设您想将一个无符号32位整数除以三，并且您的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就是这样，我刚刚检查过），那么它将自动生成上述代码（如果您至少启用了优化级别1，则GCC将为“/3”创建完全相同的代码）。对于其他编译器...即使这种方法已经在互联网上得到广泛记录和提及，您也不能依赖或期望它将使用这样的技巧。

问题在于它只适用于常量，而不适用于变量。您始终需要知道魔法数字（这里是0xAAAAAAAB）和乘法后的正确操作（在大多数情况下是移位和/或加法），并且两者取决于您要除以的数字而不同。计算它们需要太多的CPU时间，无法即时计算（这比硬件除法还要慢）。但是，编译器在编译时很容易计算这些值（一秒钟的编译时间或多或少都没有什么影响）。

- Mecki

---

请不要这样做，让编译器去处理。通过一次32位乘法，编译器会在一个寄存器中得到结果。也就是说，结果会在mul溢出寄存器EDX中。所以你的优化是错误的，你现在把一次32位乘法转化为了一次64位乘法和一次64位移位操作。 - Chris Hopman

@Chris：有些人依赖于编译器使他们原本缓慢的代码变快，而有些人则试图让代码变快，不管编译器如何。第一种人会产生在某些编译器和平台上可能会严重失败的代码，而第二种人则会产生始终表现良好甚至非常好的代码，无论平台如何。我上面发布的代码在使用x86上的GCC时不会产生64位乘法，实际上只会产生32位乘法（因为在x86上的32位乘法具有64位结果，而GCC知道这一点）。 - Mecki

@Mecki:实际上，后者往往会生成调用未定义行为的代码，当有人告诉他们是错误时，他们就会捂住耳朵不听。我并不是说尝试编写“即使你的编译器很差也可以快速运行”的代码有时不值得，但任何这样做的人都需要对C标准、未定义行为、实现定义行为以及什么是有效和可移植性有透彻的了解。 - R.. GitHub STOP HELPING ICE

@R..：它在哪里产生未定义的行为？将64位uint乘以32位uint是有定义的，对64位uint进行位移也是有定义的，从uint64转换为uint32也是有定义的，至少在ISO-C中是这样。难道是因为unsigned long long没有被定义为恰好64位吗？好吧，我会为你修复这个问题。除此之外，请向我展示一个、仅有一个ISO-C编译器，在其中上述代码不会产生期望的结果或者简单的/3会产生显著更快的代码（任何架构和平台都可以）。 - Mecki

抱歉，我的意图并不是要暗示你的答案会产生未定义行为。它是完全正确的。我的评论只是许多“认为自己比编译器更懂”的人可能知道他们想要编译器生成的汇编代码，但通常他们不太了解C语言的规则，无法避免未定义行为和不可移植的代码。 - R.. GitHub STOP HELPING ICE

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方程而获得。

- Calmarius

---

你从哪里得到 3*x + 2^64*y = 1，它的广义形式是什么？ - AMDG

@AMDG 如果A和B的最大公约数是1，方程式A*x + B*y = 1就有一个唯一的整数解。 - Calmarius

在将两个整数相除的一般情况下，这里的变量与被除数和除数之间有什么关系？ - AMDG

Answer 7

如果你真的不想进行乘除运算怎么办？这里有一个我刚刚发明的近似方法。它能够起作用是因为(x/3) = (x/4) + (x/12)。但由于(x/12) = (x/4) / 3，我们只需要重复这个过程直到足够精确。

#include <stdio.h>

void main()
{
    int n = 1000;
    int a,b;
    a = n >> 2;
    b = (a >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    printf("a=%d\n", a);
}

结果为330。可以使用b = ((b+2)>>2);进行四舍五入来提高精度。

如果允许乘法，只需选择1/3的适当近似值，用2的幂次作为除数。例如，n * (1/3) ~= n * 43 / 128 = (n * 43) >> 7。

此技术在印第安纳州最有用。

- Steve Hanov

---

选择2^33作为除数，你就得到了Mecki的答案。 - Raniz

不幸的是，它对于3的倍数不起作用（对于n = 3将返回0，对于n = 6将返回1）。您需要进行一些更特殊的检查。 - phuclv

黑客的乐趣在移位步骤后进行一些舍入。不幸的是，我无法理解它是如何工作的。 - phuclv

Answer 8

我不知道是否更快，但如果你想使用位运算符进行二进制除法，可以使用在这个页面描述的移位减法方法:

- 将商设置为0 - 对齐被除数和除数最左边的数字 - 重复：

- 如果被除数上方的那一部分大于等于除数： - 则从被除数的那一部分中减去除数 - 在商的右端连接1 - 否则，在商的右端连接0 - 将除数向右移动一位

- 直到被除数小于除数： - 商是正确的，余数是被除数 - 停止

- marxidad

---

我怀疑这并不更快。这更像是一种执行二进制除法的算法。 - Greg Dean

我终于找到了它！多年以前，我发现一个用于6502汇编程序除法的例程，但随着时间的流逝它不知去向了。由于6502没有乘除指令，所以这是唯一的方法。现在我知道了！谢谢。 - spoulson

Answer 9

对于非常大的整数除法（例如大于64位的数字），您可以将数字表示为int []，通过一次取两个数字并将它们除以3来执行快速除法。余数将成为下一个两个数字的一部分，依此类推。

例如，11004 / 3，您可以这样说

11/3 = 3，余数=2（从11-3*3）

20/3 = 6，余数=2（从20-6*3）

20/3 = 6，余数=2（从20-6*3）

24/3 = 8，余数=0

因此结果为3668

internal static List<int> Div3(int[] a)
{
  int remainder = 0;
  var res = new List<int>();
  for (int i = 0; i < a.Length; i++)
  {
    var val = remainder + a[i];
    var div = val/3;

    remainder = 10*(val%3);
    if (div > 9)
    {
      res.Add(div/10);
      res.Add(div%10);
    }
    else
      res.Add(div);
  }
  if (res[0] == 0) res.RemoveAt(0);
  return res;
}

- Carlo V. Dango

Answer 10

如果你真的想看关于整数除法的文章，但它只有学术价值...那么一个真正需要执行这种技巧并从中受益的有趣应用程序将是一个有趣的案例。

- Rob Walker

---

不确定这里应该是什么“学术”内容。几乎每个编译器都使用此类或非常相似的技术来优化除以常数的操作。 - soc