Opérations sur les bits Java (dans le tri radix)

Question

L’autre jour, j’ai décidé d’écrire une implémentation de la sorte de radix en Java. Le type de base est supposé être O (k * N) mais le mien a fini par être O (k ^ 2 * N) en raison du processus consistant à décomposer chaque chiffre en un chiffre. J'ai décomposé chaque chiffre en modifiant (%) les chiffres précédents et en les divisant par dix pour éliminer les chiffres suivants. J'ai demandé à mon professeur s'il y aurait un moyen plus efficace de le faire et il a dit d'utiliser des opérateurs de bits. Maintenant pour mes questions: Quelle méthode serait la plus rapide pour décomposer chaque nombre en Java, 1) Méthode indiquée ci-dessus. 2) Convertissez le nombre en chaîne et utilisez des sous-chaînes. 3) Utilisez les opérations de bits.

Si 3), comment cela fonctionnerait-il?

Answer 1

Comme indice, essayez d’utiliser une base différente de 10, car les ordinateurs gèrent mieux l’arithmétique binaire que décimale.

• x > > > n est équivalent à x / 2 ⁿ
• x & amp; (2 ⁿ - 1) équivaut à x% 2 ⁿ

Au fait, les > > de Java effectue une extension de signe, ce qui n'est probablement pas ce que vous voulez dans ce cas. Utilisez > > > à la place.

Answer 2

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

La ligne de code qui fait cela;

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

est la partie manipulation de bits.

& amp; est l'opérateur à faire un bitwise ET et > > est un changement à droite.