La mejor manera de obtener dígitos individuales de int para ordenar radix en C/C++

Question

¿Cuál es la mejor manera de obtener dígitos individuales de una int con n números de dígitos para usar en un algoritmo de ordenación de radix? Me pregunto si hay una manera particularmente buena de hacerlo en C/C++, si no, ¿cuál es la mejor solución general?

editar: solo para aclarar, estaba buscando una solución que no sea convertirla en una cadena y tratarla como una matriz de dígitos.

Answer 1

Utilice los dígitos del tamaño 2^k. Para extraer el n º dígito:

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

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

Usando el desplazamiento y la máscara (activado por la base de ser una potencia de 2) evita costosas instrucciones número entero-dividen.

Después de eso, elegir la mejor base es una pregunta experimental (compensación de tiempo/espacio para su hardware en particular). Probablemente k==3 (base 8) funciona bien y limita el número de cubos, pero k==4 (base 16) parece más atractivo porque divide el tamaño de la palabra. Sin embargo, realmente no hay nada de malo en una base que no divida el tamaño de la palabra, y es posible que encuentre que la base 32 o la base 64 rinden mejor. Es una pregunta experimental y es probable que difiera según el hardware, de acuerdo con el comportamiento de la memoria caché y la cantidad de elementos que hay en la matriz.

Nota final: si está ordenando con números enteros la vida es mucho más grande, porque quiere tratar el bit más significativo como firmado. Recomiendo tratar todo como unsigned, y luego si realmente necesita firmar, en el último paso de su clasificación de radix intercambiará los depósitos, de modo que los cubos con un 1 más significativo lleguen antes que un 0. El problema es definitivamente más fácil si k divide el tamaño de la palabra.

Answer 2

No utilice la base 10, de uso base 16.

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

Desde enteros se almacenan internamente en el sistema binario, esto será más eficiente que dividir por 10 para determinar decimales dígitos.