用3除整数最快的方法是什么?

粗略地

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

上的维基百科页面 Montgomery division 很难阅读,但幸运的是编译人员已经做到了,所以你不必这么做。

int a;
int b;

a = some value;
b = a / 3;

如果您知道值的范围,有一种更快的方法,例如,如果您将一个有符号整数除以3,并且您知道要除以的值的范围是0到768,那么您可以将其乘以一个因子,然后将其向左移动2的幂,以该因子除以3。

范围0->768

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

(如果使用有符号整数,请确保移位是有符号移位),同时确保移位是实际移位而不是位滚动

当然,当编译器无法运行时,您可以进行此优化的唯一原因是编译器不知道X的最大范围,因此无法进行此确定,但作为程序员,您可以这样做。

有时,将值移到更大的值中,然后做同样的事情可能会更有益,例如,如果你有一个满量程的int,你可以将它设为64位值,然后进行乘法和移位,而不是除以3。

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

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

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

我把线路改成:

平均值=(r+g+b)*341>&燃气轮机;10;

这使它下降到22毫秒,这是一个惊人的事情,可以做一个小聪明。

这种速度出现在C#中,尽管我打开了优化功能,并且在没有调试信息的情况下本机运行程序,而不是通过IDE。

看见 How To Divide By 3 对于更有效地除以3的扩展讨论,重点是进行FPGA算术运算。

同样相关的还有:

• Optimizing integer divisions with Multiply Shift in C#

根据您的平台和您的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知道,我刚刚检查过),那么无论如何它都会生成上面的代码(如果您至少启用优化级别1,GCC将为“/3”创建此代码)。对于其他编译器。。。你不能依赖或期望它会使用这样的技巧,即使这种方法在互联网上到处都有很好的文档记录和提及。

对于64位数字:

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

如果这个数字已经可以被3整除,那么它可以正常工作,但是如果它不能被3整除,那么它将返回一个巨大的数字。

例如,如果在示例11上运行它,它将返回6148914691236517209。这看起来像垃圾,但事实上这是正确的答案:乘以3,你就得到了11!

理论:

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

如果你 真正地

#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.

这项技术在实际应用中非常有用 Indiana.

我不知道它是否更快,但如果您想使用位运算符执行二进制除法,您可以使用中描述的移位和减法 this page :

• 重复:
  • • 然后从那部分股息中减去除数,然后
  • 将除数右移一位
• 直到股息小于除数:
• 商是正确的,被除数是余数
• 停止

对于真正大的整数除法(例如大于64位的数字),您可以将数字表示为int[],并通过一次取两位数字并将其除以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;
}

如果你真的想看这篇文章 integer division ,但它只有学术价值。。。这将是一个有趣的应用程序,实际上需要执行从这种技巧中受益的操作。

简单的计算。。。最多n次迭代,其中n是位数:

uint8_t divideby3(uint8_t x)
{
  uint8_t answer =0;
  do
  {
    x>>=1;
    answer+=x;
    x=-x;
  }while(x);
  return answer;
}

在某些体系结构中,查找表方法也会更快。

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