Operaciones de bits de Java (en clasificación de radix)

Question

El otro día decidí escribir una implementación de clasificación de radios en Java. Se supone que la clasificación de radix es O (k * N) pero la mía terminó siendo O (k ^ 2 * N) debido al proceso de descomponer cada dígito en un número. Desglosé cada dígito modificando (%) los dígitos anteriores y dividiéndolos por diez para eliminar los dígitos siguientes. Le pregunté a mi profesor si habría una forma más eficiente de hacer esto y me dijo que usara operadores de bits. Ahora para mis preguntas: ¿Qué método sería el más rápido para desglosar cada número en Java? 1) Método indicado anteriormente. 2) Convierta el número a Cadena y use subcadenas. 3) Usar operaciones de bit.

Si 3) entonces, ¿cómo funcionaría eso?

Answer 1

Como pista, intente usar una raíz diferente de 10, ya que las computadoras manejan la aritmética binaria mejor que la decimal.

• x > > > n es equivalente a x / 2 ⁿ
• x & amp; (2 ⁿ - 1) es equivalente a x% 2 ⁿ

Por cierto, Java > > realiza la extensión de signo, que probablemente no sea lo que desea en este caso. Utilice > > > en su lugar.

Answer 2

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

La línea de código que hace esto;

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

es la parte de manipulación de bits.

& amp; es el operador para hacer un AND y > > es un desplazamiento a la derecha.