Operazioni bit Java (nell'ordinamento Radix)

Question

L'altro giorno ho deciso di scrivere un'implementazione di radix sort in Java. Si suppone che l'ordinamento Radix sia O (k * N) ma il mio ha finito per essere O (k ^ 2 * N) a causa del processo di scomposizione di ogni cifra in un numero. Ho scomposto ogni cifra modificando (%) le cifre precedenti e dividendole per dieci per eliminare le cifre successive. Ho chiesto al mio professore se ci sarebbe stato un modo più efficiente per farlo e lui ha detto di usare operatori bit. Ora per le mie domande: quale metodo sarebbe il più veloce per abbattere ogni numero in Java, 1) Metodo indicato sopra. 2) Converti il ??numero in String e usa sottostringhe. 3) Utilizzare le operazioni a bit.

Se 3) come funzionerebbe?

Answer 1

Come suggerimento, prova a utilizzare una radice diversa da 10, poiché i computer gestiscono l'aritmetica binaria meglio dei decimali.

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

A proposito, Java è > > esegue l'estensione del segno, che probabilmente non è quello che vuoi in questo caso. Usa > > > invece.

Answer 2

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

La riga di codice che esegue ciò;

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

è la parte di manipolazione dei bit.

& amp; è l'operatore che esegue un AND bit per bit e > > è uno spostamento a destra.