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

// for instance

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

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

12 回答 12

126

说“把它留给编译器”的人是对的，但我没有“声誉”来修改或评论他。我让 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
$

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

于 2008-10-05T02:27:33.287 回答
61

这是最快的，因为编译器会根据输出处理器对其进行优化。

int a;
int b;

a = some value;
b = a / 3;
于 2008-10-05T01:30:32.840 回答
25

如果您知道值的范围，有一种更快的方法可以做到这一点，例如，如果您将一个有符号整数除以 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）。红绿蓝。

起初我只是简单地使用：

平均值 = (r + g + b) / 3;

（所以 r + g + b 最大为 768，最小为 0，因为每个通道都是一个字节 0 - 255）

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

我将行更改为：

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

这将其缩短到 22 毫秒，这令人惊叹，只需一点点独创性就可以完成。

即使我打开了优化并且在没有调试信息并且没有通过 IDE 的情况下本机运行程序，这种加速也发生在 C# 中。

于 2011-04-19T01:20:52.810 回答
13

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

也相关：

于 2008-10-05T01:31:28.953 回答
10

根据您的平台和 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 位数字相乘需要 3 次乘法和 3 次 32 位值的加法） - 但是，它可能仍然比在 32 位机器上进行除法。

另一方面，如果您的编译器是一个非常好的编译器，并且知道如何优化整数除法的技巧（最新的 GCC 可以，我刚刚检查过），它无论如何都会生成上面的代码（GCC 将为"/3" 如果您至少启用优化级别 1)。对于其他编译器......你不能依赖或期望它会使用这样的技巧，即使这种方法在互联网上到处都有很好的记录和提及。

问题是它只适用于常数，而不适用于变量。您总是需要知道幻数（此处为 0xAAAAAAAB）和乘法后的正确操作（在大多数情况下是移位和/或加法），两者都不同，具体取决于您要除以的数字，并且都需要太多 CPU 时间即时计算它们（这将比硬件除法慢）。但是，编译器很容易在编译期间计算这些（其中一秒钟或多或少的编译时间几乎没有作用）。

于 2009-01-12T18:47:48.717 回答
5

对于 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使用扩展欧几里得算法求解方程来获得。

于 2018-01-28T01:31:37.753 回答
4

如果你真的不想乘法或除法怎么办？这是我刚刚发明的一个近似值。它之所以有效，是因为 (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。

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

于 2009-05-13T17:57:40.387 回答
2

我不知道它是否更快，但如果您想使用按位运算符执行二进制除法，您可以使用本页描述的移位和减法方法：

  • 将商设置为 0
  • 对齐被除数和除数中的最左边的数字
  • 重复：
    • 如果除数之上的那部分被除数大于或等于除数：
      • 然后从那部分被除数中减去除数，然后
      • 将 1 连接到商的右手端
      • 否则将 0 连接到商的右手端
    • 将除数右移一位
  • 直到股息小于除数：
  • 商是正确的，被除数是余数
  • 停止
于 2008-10-05T01:19:31.457 回答
1

如果你真的想看这篇关于整数除法的文章，但它只具有学术价值……这将是一个有趣的应用程序，它实际上需要从这种技巧中受益。

于 2008-10-05T01:21:50.657 回答
1

对于非常大的整数除法（例如大于 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;
}
于 2012-05-20T13:30:51.670 回答
0

易于计算...最多 n 次迭代，其中 n 是您的位数：

uint8_t divideby3(uint8_t x)
{
  uint8_t answer =0;
  do
  {
    x>>=1;
    answer+=x;
    x=-x;
  }while(x);
  return answer;
}
于 2013-05-09T15:30:05.843 回答
0

在某些架构中，查找表方法也会更快。

uint8_t DivBy3LU(uint8_t u8Operand)
{
   uint8_t ai8Div3 = [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ....];

   return ai8Div3[u8Operand];
}
于 2013-07-17T06:55:33.880 回答