412

整数を2で割るのに最適なオプションは、次のうちどれですか。その理由は何ですか。

テクニック1：

x = x >> 1;

テクニック2：

x = x / 2;

これxが整数です。

4

23 に答える 23

853

実行しようとしていることを最もよく表す操作を使用してください。

  • 数値をビットのシーケンスとして扱う場合は、ビットシフトを使用します。
  • 数値として扱う場合は、除算を使用してください。

それらは完全に同等ではないことに注意してください。それらは、負の整数に対して異なる結果を与える可能性があります。例えば：

-5 / 2  = -2
-5 >> 1 = -3

（イデオネ）

于 2012-05-21T07:57:52.080 に答える
227

最初のものは分裂しているように見えますか？いいえ。分割する場合は、を使用しますx / 2。コンパイラーは、可能であればビットシフトを使用するように最適化できます（これは強度低減と呼ばれます）。これにより、自分で行う場合は、役に立たないマイクロ最適化になります。

于 2012-05-21T07:56:38.147 に答える
191

積み重ねる：使用することを好む理由はたくさんありますx = x / 2; ここにいくつかあります：

  • それはあなたの意図をより明確に表現します（あなたがレジスタビットなどをいじるビットを扱っていないことを前提としています）

  • コンパイラはとにかくこれをシフト操作に減らします

  • コンパイラがそれを減らしず、シフトよりも遅い操作を選択したとしても、これがプログラムのパフォーマンスに測定可能な方法で影響を与える可能性は、それ自体がほとんどありません（そして、それが測定可能な影響を与える場合は、実際のシフトを使用する理由）

  • 除算がより大きな式の一部になる場合、除算演算子を使用すると、優先順位が正しくなる可能性が高くなります。

    x = x / 2 + 5;
x = x >> 1 + 5;  // not the same as above

  • 符号付き演算は、上記の優先順位の問題よりもさらに複雑になる可能性があります

  • 繰り返しになりますが、コンパイラはとにかくこれをすでに実行します。実際、定数による除算を、2の累乗だけでなく、あらゆる種類の数値の一連のシフト、加算、および乗算に変換します。これに関するさらに詳しい情報へのリンクについては、この質問を参照してください。

つまり、実際に乗算または除算を行う場合は、バグを導入する可能性が高くなることを除いて、シフトをコーディングしても何も購入しません。コンパイラーがこの種のものを適切なときにシフトに最適化するほど賢くなかったので、それは一生になりました。

于 2012-05-21T08:34:03.790 に答える
63

どれが最良のオプションであり、なぜ整数を2で割るのですか？

あなたが最高の意味するところに依存します。

同僚にあなたを嫌ってもらいたい場合、またはコードを読みにくくしたい場合は、間違いなく最初のオプションを選択します。

数値を2で割りたい場合は、2番目の数値を使用してください。

この2つは同等ではなく、数値が負の場合や大きな式の内部にある場合は同じように動作しません。ビットシフトの優先順位は+またはより低く-、除算の優先順位は高くなります。

あなたはその意図が何であるかを表現するためにあなたのコードを書くべきです。パフォーマンスが懸念される場合でも、心配しないでください。オプティマイザーは、この種のマイクロ最適化で優れた機能を発揮します。

于 2012-05-21T07:59:03.743 に答える
60

/より明確であると仮定して、divide（）を使用するだけです。コンパイラはそれに応じて最適化します。

于 2012-05-21T07:56:04.133 に答える
39

x / 2その意図がより明確であり、コンパイラーがあなたのためにそれを最適化する必要があるので、あなたが好むべき他の答えに同意します。

x / 2ただし、を優先するもう1つの理由は、が署名されていて負の場合x >> 1、の動作>>が実装に依存することです。xint

セクション6.5.7から、ISOC99標準の箇条書き5：

の結果は、E1 >> E2右E1シフトされたE2ビット位置です。符号なし型がある場合E1、または符号付きE1型と非負の値がある場合、結果の値はE1/2の商の整数部分になりE2ます。が符号付きタイプで負の値の場合E1、結果の値は実装定義です。

于 2012-05-21T08:02:33.903 に答える
31

x / 2より明確で、x >> 1それほど高速ではありません（マイクロベンチマークによると、Java JVMの場合は約30％高速です）。他の人が指摘しているように、負の数の場合、丸めはわずかに異なるため、負の数を処理する場合はこれを考慮する必要があります。一部のコンパイラは、数値が負になり得ないことを知っている場合（これを確認できなかったとしても）、自動的にに変換x / 2する場合があります。x >> 1

いくつかのショートカットが可能x / 2であるため、（遅い）除算CPU命令を使用しない場合もありますが、それでも。よりも低速です。x >> 1

（これはC / C ++の質問ですが、他のプログラミング言語にはより多くの演算子があります。Javaの場合、符号なしの右シフトもありますがx >>> 1、これも異なります。2つの値の平均（平均）値を正しく計算できるため、次のように(a + b) >>> 1なります。との値が非常に大きい場合でも平均値を返しますa。bこれは、たとえば、配列インデックスが非常に大きくなる可能性がある場合のバイナリ検索に必要です。バイナリ検索の多くのバージョンには、平均の計算に使用されていたため、バグがありました(a + b) / 2。正しく機能しません。正しい解決策は、(a + b) >>> 1代わりに使用することです。）

于 2012-05-21T07:57:21.263 に答える
22

クヌースは言った：

時期尚早の最適化はすべての悪の根源です。

だから私は使用することをお勧めしますx /= 2;

このようにコードは理解しやすく、また、この形式でのこの操作の最適化は、プロセッサにとって大きな違いを意味しないと思います。

于 2012-05-22T23:58:57.280 に答える
18

決定に役立つコンパイラ出力を見てください。このテストは、
gcc（GCC）4.2.120070719[FreeBSD]を使用してx86-64で実行しました。

godboltでオンラインのコンパイラ出力も参照してください。

ご覧のとおり、コンパイラはsarlどちらの場合も（算術右シフト）命令を使用するため、2つの式の類似性を認識します。除算を使用する場合、コンパイラは負の数も調整する必要があります。これを行うには、符号ビットを最下位ビットにシフトダウンし、それを結果に追加します。これにより、除算の場合と比較して、負の数をシフトするときの1つずつずれた問題が修正されます。
除算の場合は2つのシフトを実行しますが、明示的なシフトの場合は1つしか実行しないため、ここで他の回答によって測定されたパフォーマンスの違いのいくつかを説明できます。

アセンブリ出力付きのCコード：

除算の場合、入力は次のようになります

int div2signed(int a) {
  return a / 2;
}

そしてこれはコンパイルされます

    movl    %edi, %eax
    shrl    $31, %eax
    addl    %edi, %eax
    sarl    %eax
    ret

シフトについても同様

int shr2signed(int a) {
  return a >> 1;
}

出力付き：

    sarl    %edi
    movl    %edi, %eax
    ret
于 2012-05-27T00:32:25.617 に答える
15

ただ追加されたメモ-

x * = 0.5は、一部のVMベースの言語（特にactionscript）では、変数が0で除算されているかどうかをチェックする必要がないため、多くの場合高速になります。

于 2012-05-21T18:46:31.020 に答える
13

x = x / 2; OR を使用するx /= 2;将来、新しいプログラマーがそれに取り組む可能性があるためです。したがって、彼はコード行で何が起こっているのかを簡単に見つけることができます。誰もがそのような最適化に気付いていないかもしれません。

于 2012-05-22T05:58:09.947 に答える
12

CPUに関する限り、ビットシフト演算は除算演算よりも高速です。ただし、コンパイラーはこれを認識しており、可能な範囲で適切に最適化するため、コードが効率的に実行されていることを知って、最も意味のある方法でコーディングし、安心してコーディングできます。ただし、以前に指摘した理由により、unsigned int缶は（場合によっては）より適切に最適化できることを忘れないでください。int符号付き算術が必要ない場合は、符号ビットを含めないでください。

于 2012-05-22T01:17:05.007 に答える
12

私はプログラミング競技の目的で話している。一般に、2による除算が何度も行われる非常に大きな入力があり、入力が正または負であることがわかっています。

x>>1はx/2よりも優れています。2回の演算で10^10以上の除算が行われるプログラムを実行してideone.comをチェックしました。x / 2は5.5秒近くかかりましたが、x>>1は同じプログラムで2.6秒近くかかりました。

于 2012-05-21T18:39:43.170 に答える
12

考慮すべきことがいくつかあると思います。

  1. ビットをシフトするために特別な計算は実際には必要ないため、ビットシフトはより高速である必要がありますが、指摘されているように、負の数には潜在的な問題があります。正の数が確実にあり、速度を求めている場合は、ビットシフトをお勧めします。

  2. 除算演算子は、人間にとって非常に読みやすいものです。したがって、コードの可読性を求めている場合は、これを使用できます。コンパイラの最適化の分野は長い道のりを歩んできたので、コードを読みやすく理解しやすくすることは良い習慣であることに注意してください。

  3. 基盤となるハードウェアに応じて、操作の速度が異なる場合があります。アムダールの法則は、一般的なケースを迅速にすることです。したがって、他のハードウェアよりも高速にさまざまな操作を実行できるハードウェアがある場合があります。たとえば、0.5で乗算すると、2で除算するよりも高速になる場合があります（整数除算を強制する場合は、乗算の下限を取る必要がある場合があります）。

純粋なパフォーマンスを求めている場合は、何百万回も操作を実行できるテストを作成することをお勧めします。実行を数回（サンプルサイズ）サンプリングして、OS/ハードウェア/コンパイラ/コードで統計的に最適なものを決定します。

于 2012-05-21T20:21:51.530 に答える
11

x = x / 2; は使用するのに適したコードです。ただし、操作は、生成する出力の方法に関する独自のプログラムによって異なります。

于 2012-05-21T12:07:29.733 に答える
11

意図を明確にします...たとえば、除算する場合は、x / 2を使用し、コンパイラにシフト演算子（またはその他）に最適化させます。

今日のプロセッサでは、これらの最適化がプログラムのパフォーマンスに影響を与えることはありません。

于 2012-05-22T08:29:03.087 に答える
10

これに対する答えは、作業している環境によって異なります。

  • 8ビットマイクロコントローラーなど、乗算をハードウェアでサポートしていないもので作業している場合、ビットシフトは予想され、ありふれたものです。コンパイラーはほぼ確実にになりますx /= 2がx >>= 1、除算記号の存在は、その環境でより多くの眉をひそめます。シフトを使用して除算を実行します。
  • パフォーマンスが重要な環境またはコードのセクションで作業している場合、またはコンパイラの最適化をオフにしてコードをコンパイルできる場合はx >>= 1、目的を明確にするために、その理由を説明するコメントがおそらく最適です。
  • 上記の条件のいずれにも該当しない場合は、を使用するだけでコードを読みやすくしますx /= 2。シフトがコンパイラの最適化よりも効率的であることを不必要に証明するよりも、コードをたまたま見た次のプログラマーをシフト操作で10秒間ダブルテイクする方がよいでしょう。

これらはすべて、符号なし整数を想定しています。単純なシフトは、おそらくあなたが署名したいものではありません。また、DanielHは、x *= 0.5ActionScriptなどの特定の言語での使用について良い点を示しています。

于 2012-05-22T21:11:21.797 に答える
8

mod 2、テスト=1。cの構文を知らない。しかし、これは最速かもしれません。

于 2012-05-21T20:30:22.530 に答える
7

一般的に右シフトは分割します：

q = i >> n; is the same as: q = i / 2**n;

これは、明確さを犠牲にしてプログラムを高速化するために使用されることがあります。私はあなたがそれをすべきではないと思います。コンパイラは、スピードアップを自動的に実行するのに十分スマートです。これは、シフトを入れることは、明快さを犠牲にして何も得られないことを意味します。

PracticalC++Programmingのこのページをご覧ください。

于 2012-05-22T10:41:15.207 に答える
7

明らかに、あなたがそれを読む次の人のためにあなたのコードを書いているなら、「x/2」の明快さのために行ってください。

ただし、速度が目標である場合は、両方の方法で試して、結果の時間を計ってください。数か月前、整数の配列をステップ実行し、各要素を2で除算するビットマップ畳み込みルーチンに取り組みました。これを最適化するために、「x >>1」を「x」に置き換えるという古いトリックを含め、さまざまなことを行いました。 /2"。

実際に両方のタイミングを計ったとき、驚いたことに、x/2がx>>1よりも速いことに気づきました。

これは、デフォルトの最適化がオンになっているMicrosoft VS2008C++を使用していました。

于 2012-06-08T11:34:59.853 に答える
4

パフォーマンスの面で。CPUのシフト操作は、オペコードを分割するよりも大幅に高速です。したがって、2で割ったり、2を掛けたりすることはすべて、シフト演算の恩恵を受けます。

ルックアンドフィールに関して。エンジニアとして、私たちはいつ化粧品に夢中になり、美しい女性でさえ使用しなくなりました！:)

于 2012-05-22T17:25:52.300 に答える
3

X /Yは正しいものです...そして">>"シフト演算子..整数を2で除算したい場合は、（/）被除数演算子を使用できます。シフト演算子はビットをシフトするために使用されます。

x = x / 2; x / = 2; このように使用できます。

于 2012-05-25T05:51:53.890 に答える
0

x>>1はx/2よりも高速ですが、負の値を処理する場合の>>の適切な使用は少し複雑です。次のようなものが必要です。

// Extension Method
public static class Global {
    public static int ShiftDivBy2(this int x) {
        return (x < 0 ? x + 1 : x) >> 1;
    }
}
于 2016-12-21T06:41:31.343 に答える