Битовые операции Java (в сортировке Radix)

Question

На днях я решил написать реализацию radix sort на Java. Предполагается, что сортировка по корням должна быть O (k * N), но моя оказалась O (k ^ 2 * N) из-за процесса разбиения каждой цифры на одно число. Я разбил каждую цифру, отредактировав (%) предыдущие цифры и разделив на десять, чтобы исключить последующие цифры. Я спросил своего профессора, будет ли более эффективный способ сделать это, и он сказал, что нужно использовать битовые операторы. Теперь о моих вопросах: какой метод будет самым быстрым при разбивании каждого числа в Java, 1) метод, указанный выше. 2) Преобразовать число в строку и использовать подстроки. 3) Используйте битовые операции.

Если 3), то как это будет работать?

Answer 1

В качестве подсказки попробуйте использовать основание, отличное от 10, поскольку компьютеры обрабатывают двоичную арифметику лучше, чем десятичную.

• x >>> n эквивалентно x / 2 ⁿ
• x & (2 ⁿ - 1) эквивалентно x% 2 ⁿ

Кстати, Java >> выполняет расширение знака, что, вероятно, не то, что вам нужно в этом случае. Вместо этого используйте >>>.

Answer 2

[http://en.literateprograms.org/Radix_sort_(Java)] (http://en.literateprograms.org/Radix_sort_(Java))

Строка кода, которая делает это;

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

- часть управления битами.

& - оператор для побитового И, а >> - сдвиг вправо.