Operações de bit java (na classificação da radix)

Question

Outro dia, decidi escrever uma implementação de Radix Sort em java. O tipo Radix deve ser O (k*n), mas o meu acabou sendo O (k^2*n) por causa do processo de quebrar cada dígito em um número. Eu quebrei cada dígito moding (%) os dígitos anteriores e dividindo por dez para eliminar os dígitos seguintes. Perguntei ao meu professor se haveria uma maneira mais eficiente de fazer isso e ele disse para usar operadores de bits. Agora, para minhas perguntas: qual método seria o mais rápido em quebrar cada número em Java, 1) método mencionado acima. 2) Converta o número em string e use substrings. 3) Use operações de bits.

Se 3) então como isso funcionaria?

Answer 1

Como dica, tente usar um radix diferente de 10, pois os computadores lidam com a aritmética binária melhor que a decimal.

• x >>> n é equivalente a x / 2ⁿ
• X & (2ⁿ - 1) é equivalente a x % 2ⁿ

A propósito, o Java's >> executa a extensão de sinal, o que provavelmente não é o que você deseja neste caso. Use >>> em vez disso.

Answer 2

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

A linha de código que faz isso;

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

é a parte de manipulação de bits.

& é o operador a fazer um pouco e >> é um turno direito.