Javaビット操作（基数ソート）

Question

先日、Javaで基数ソートの実装を作成することにしました。基数ソートはO（k * N）であると想定されていますが、各桁を1つの数値に分解するプロセスのため、私のものは最終的にO（k ^ 2 * N）になります。先行する数字を削除（％）し、10で割って後続の数字を削除することにより、各数字を分解しました。私は教授にこれをもっと効率的に行う方法があるかどうか尋ねたところ、ビット演算子を使うように言われました。さて、私の質問：Javaで各数値を分解するのに最も速い方法は、1）上記の方法です。 2）数値を文字列に変換し、部分文字列を使用します。 3）ビット演算を使用します。

3）の場合、どのように機能しますか？

Answer 1

ヒントとして、10以外の基数を使用してみてください。コンピューターは10進数よりも2進算術をうまく処理できるからです。

• x＆gt;＆gt;＆gt; nはx / 2 ⁿ
と同等です
• x＆amp; （2 ⁿ -1）はx％2 ⁿ
と同等です

ところで、Javaの＆gt;＆gt;符号拡張を実行しますが、これはおそらくこの場合には望んでいないことです。使用＆gt;＆gt;＆gt;代わりに。

Answer 2

[ http://en.literateprograms.org/Radix_sort_（Java）]（ http://en.literateprograms.org/Radix_sort_（Java））

これを行うコード行;

 int key = (a[p] & mask) >> rshift;

ビット操作部です。

＆amp;ビット単位のANDを行う演算子です＆gt;＆gt;右シフトです。