La meilleure façon d'obtenir des chiffres individuels à partir int pour le tri radix en C / C ++

Question

Quelle est la meilleure façon d'obtenir des chiffres individuels à partir d'un int avec n nombre de chiffres pour être utilisé dans un algorithme de tri radix? Je me demande s'il est un très bon moyen de le faire en C / C ++, sinon quelle est la meilleure solution générale?

modifier. Juste pour clarifier, je cherchais une solution autre que la conversion à une chaîne et de le traiter comme un tableau de chiffres

Answer 1

Utilisez les chiffres de la taille 2^k. Pour extraire le chiffre nth:

#define BASE (2<<k)
#define MASK (BASE-1)

inline unsigned get_digit(unsigned word, int n) {
    return (word >> (n*k)) & MASK;
}

En utilisant le décalage et le masque (activé par la base étant une puissance de 2) permet d'éviter instructions coûteux-division entière.

Après cela, le choix de la meilleure base est une question expérimentale (temps / espace Compromis pour votre matériel particulier). Probablement k==3 (base 8) fonctionne bien et limite le nombre de seaux, mais k==4 (base 16) semble plus intéressante, car elle divise la taille de texte. Cependant, il n'y a vraiment rien de mal à une base qui ne divise pas la taille de mot, et vous trouverez peut-être que la base 32 ou en base 64 fonctionnent mieux. Il est une question expérimentale et peut différer probablement par le matériel, selon la façon dont le cache et se comporte combien d'éléments il y a dans votre tableau.

Note finale: si vous triez signé entiers la vie est une douleur beaucoup plus, parce que vous voulez traiter le bit le plus significatif que signé. Je recommande le traitement tout comme non signé, et si vous avez vraiment besoin signé, dans la dernière étape de votre radix sorte que vous échangera les seaux, de sorte que des seaux avec un plus significatif 1 viennent avant un 0. Ce problème le plus important est certainement plus facile si k divise la taille de texte.

Answer 2

Ne pas utiliser la base de 10, la base de l'utilisation 16.

for (int i = 0; i < 8; i++) {
    printf("%d\n", (n >> (i*4)) & 0xf);
}

Étant donné que les entiers sont stockés en interne en binaire, ce sera plus efficace que la division par 10 pour déterminer décimal chiffres.