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にinttest（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 であることがわかっている場合は、それを掛けることができます。係数で左にシフトし、その係数を 3 で割った値に 2 のべき乗でシフトします。

例えば。

範囲 0 -> 768

1024 を掛ける 10 ビットのシフトを使用できます。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

FPGA 算術演算の実行に焦点を当てた、より効率的な 3 での除算に関する詳細な説明については、「3 で除算する方法」を参照してください。

また関連:

于 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ビットアプリケーションでは、2つの64ビット数を乗算すると32ビット値で3回の乗算と3回の加算が必要になります）-ただし、 32ビットマシンでの分割。

一方、コンパイラが非常に優れていて、定数による整数除算を最適化する方法を知っている場合（最新のGCCはそうですが、チェックしたばかりです）、とにかく上記のコードを生成します（GCCはこのコードを正確に作成します）少なくとも最適化レベルを有効にした場合は「/3」1）。他のコンパイラの場合...この方法はインターネット上のあらゆる場所で非常によく文書化され、言及されていますが、そのようなトリックが使用されることを信頼したり期待したりすることはできません。

問題は、可変数ではなく、定数に対してのみ機能することです。常に魔法の数（ここでは0xAAAAAAAB）と乗算後の正しい演算（ほとんどの場合、シフトおよび/または加算）を知る必要があり、どちらも除算する数によって異なり、どちらもCPU時間がかかりすぎます。それらをその場で計算します（ハードウェアの除算よりも遅くなります）。ただし、コンパイラがコンパイル時にこれらを計算するのは簡単です（1秒程度のコンパイル時間はほとんど影響しません）。

于 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); を使用してより正確にすることができます。丸めを考慮します。

乗算が許可されている場合は、2 の累乗の除数を使用して、(1/3) の適切な近似値を選択してください。たとえば、n * (1/3) ~= n * 43 / 128 = (n * 43) >> 7 です。

この手法は、インディアナ州で最も役立ちます。

于 2009-05-13T17:57:40.387 に答える
2

それがより速いかどうかはわかりませんが、ビットごとの演算子を使用してバイナリ除算を実行する場合は、このページで説明されているシフトと減算の方法を使用できます。

  • 商を 0 に設定
  • 被除数と除数の左端の桁を揃える
  • 繰り返す：
    • 除数の上の被除数の部分が除数以上の場合:
      • 次に、被除数のその部分から除数を減算し、
      • 商の右端に 1 を連結します。
      • それ以外の場合は、商の右端に 0 を連結します。
    • 除数を右に 1 桁シフトする
  • 被除数が除数より小さくなるまで:
  • 商は正しい、被除数は剰余
  • 止まる
于 2008-10-05T01:19:31.457 に答える
1

非常に大きな整数除算（たとえば、64ビットより大きい数値）の場合、数値をint []として表し、一度に2桁を取り、3で除算することにより、非常に高速に除算を実行できます。残りは次の2桁の一部になります。など。

例えば。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 に答える
1

整数除算に関するこの記事を本当に見たいが、学術的なメリットしかない場合...その種のトリックの恩恵を受けて実際に実行する必要がある興味深いアプリケーションになるでしょう。

于 2008-10-05T01:21:50.657 に答える
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 に答える
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 に答える