Javaはビットシフトに対して2の累乗で除算を最適化しますか？

Question

Javaコンパイラまたは JITコンパイラは、ビットシフトまで2の一定の累乗で除算または乗算を最適化しますか？

たとえば、次の2つのステートメントは同じに最適化されていますか？ （基本的にthis questionが、Java用）

int median = start + (end - start) >>> 1; 
int median = start + (end - start)/2; 

Answer 1

それは(end - start)の兆候がどうなるかについて確認することはできませんので、いいえ、Javaコンパイラは、それをしません。なぜこれは問題なのでしょうか？負の整数のビットシフトは、通常の除算とは異なる結果をもたらします。ここでは、デモを見ることができます：this simple test：

System.out.println((-10) >> 1); // prints -5 
System.out.println((-11) >> 1); // prints -6 
System.out.println((-11)/2); // prints -5 

はまた、私は>>代わりの>>>を使用していることに注意してください。 >>>は符号なしビットシフトであり、>>は符号付きです。

System.out.println((-10) >>> 1); // prints 2147483643 

---

@Mystical：受け入れ答えは分裂ができるという意味で、右ですがhttps://ideone.com/aKDShA

Answer 2

：私は、コンパイラ/ JVMは、その最適化を行っていないことを示している、ベンチマークを書きましたベンチマークはひどく間違っています。 Javaのベンチマークが1秒未満で実行されている場合は、通常、通訳者のパフォーマンスを測定している可能性があります。

私は抵抗できず、主にそれがもっと複​​雑であることを主に示すbenchmarkを書きました。私は完全にresultsを説明しようとしていないんだけど、それは避けます

一般部門はいまいましい遅い操作です

• と言うことができる定数による除算は、常に私の知る限りを取得する多くの
可能としてあります2のべき乗によって何とか最適化
• 分割は右シフトと負の数
• の調整に置き換えます手動で最適化された発現は、より良いかもしれない

Answer 3

JVMで実行しない場合は、簡単に実行できます。

前述のように、結果が間違った方向に丸められているため、負の数の右シフトは除算と同じように動作しません。被除数が負でないことが分かっている場合は、分母をシフトで置き換えることができます。それが負の場合は、次の方法を使用できます。

このフォームであなたの元のコードを表現することができた場合：

int result = (x + (x >> 31 >>> (32 - shift))) >> shift; 

か、あるいは：

int result = (x + ((x >> 31) & ((1 << shift) - 1))) >> shift; 

これら

int result = x/(1 << shift); 

をあなたは、この最適化されたコードに置き換えることができます数式は、被除数の符号ビットから計算された少数を加算することによって、不正確な丸めを補償する。

：シフトが1である場合、これはその後、 >> 31はこの非常に整頓スニペットを与えるために最初の式で削除することができます（つまり、あなたは2で割るされている）1から30

へのすべてのシフト値を持つすべてのxのために働きます

int result = (x + (x >>> 31)) >> 1; 

シフトが一定でなくても、これらの手法が高速であることがわかりましたが、シフトが一定であれば、最も効果的です。注：longx代わりにintために、63及び64

Examining the generated machine codeにそれぞれ31及び32を変更する（当然）のHotSpotサーバVMは（も当然）シフトが一定であるときに自動的にこの最適化を行うことができるが、ことを示していますHotSpot Client VMはあまりにも愚かです。