java - 2のべき乗のときに除算をビットごとのシフトに変える方法は?

Question

私は頻繁に行う必要がある次の部門を持っています。

int index = pos / 64;

除算は、CPU レベルで高価になる可能性があります。ビット単位のシフトでそれを行う方法があることを願っています。また、除算からシフトへの移行方法も理解したいと思います。つまり、ビット単位の式だけを覚えたくありません。

Answer 1

int index = pos >> 6しますが、これは不要です。合理的なコンパイラは、この種のことを行います。確かに、Sun/Oracle コンパイラはそうします。

一般的なルールは、i/(2^n)で実装できることi >> nです。も同様i*(2^n)ですi << n。

iが署名されている場合は、負の数値表現に注意する必要があります。たとえば、2 の補数は妥当な結果を生成します (右シフトが算術演算の場合、符号ビットがコピーされます)。符号付きマグニチュードはありません。

Answer 2

必要なものを理解し、コンパイラーに正確にそれを行うように依頼する限り、コンパイラーは最も効率的な方法でそれを実装します。この場合、シフトが最も効率的な方法である場合、コンパイラはシフトを使用します。

ただし、符号付き除算を実行している(つまりpos、符号付き) 場合は、シフトだけでは完全に実装できないことに注意してください。Shift だけでは、 の負の値に対して無効な結果が生成されますpos。コンパイラがこの操作にシフトを使用することを決定した場合、言語仕様の要件に一致させるために、中間結果に対していくつかのシフト後の修正も実行する必要があります。

このため、除算の効率を最大限に高めたい場合は、signed 型をむやみに使用しないように注意する必要があります。可能な限り符号なしの型を使用し、必要な場合にのみ符号付きの型を使用してください。

PS AFAIK、Javaはユークリッド除算を実装しています。つまり、上記の発言はJavaには当てはまりません。ユークリッド除算は、2 の補数表現で負の約数をシフトすることによって正しく実行されます。上記の注意事項は、C/C++ に適用されます。

Answer 3

http://www.java-samples.com/showtutorial.php?tutorialid=58

割りたい 2 のべき乗ごとに、1 回右シフトします。したがって、4 で割るには、右シフトを 2 回行う必要があります。8で割るには右シフトを3回。16で割ります右シフト4回。32回→5回。64 -> 6回。したがって、64 で割るには、右シフトを 6 回行う必要があります。私の値 = 私の値 >> 6;