Mejor manera de conseguir cifras individuales de int radix de clase en C / C ++

Question

¿Cuál es la mejor manera de obtener los dígitos individuales a partir de un int con n número de dígitos para su uso en un algoritmo radix tipo? Me pregunto si hay una especialmente buena manera de hacerlo en C / C ++, si no lo que es la mejor solución general?

editar:. Sólo para aclarar, yo estaba buscando una solución que no sea convirtiéndola en una cadena y tratándolo como una serie de dígitos

Answer 1

Use digits of size 2^k. To extract the nth digit:

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

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

Using the shift and mask (enabled by base being a power of 2) avoids expensive integer-divide instructions.

After that, choosing the best base is an experimental question (time/space tradeoff for your particular hardware). Probably k==3 (base 8) works well and limits the number of buckets, but k==4 (base 16) looks more attractive because it divides the word size. However, there is really nothing wrong with a base that does not divide the word size, and you might find that base 32 or base 64 perform better. It's an experimental question and may likely differ by hardware, according to how the cache behaves and how many elements there are in your array.

Final note: if you are sorting signed integers life is a much bigger pain, because you want to treat the most significant bit as signed. I recommend treating everything as unsigned, and then if you really need signed, in the last step of your radix sort you will swap the buckets, so that buckets with a most significant 1 come before a most significant 0. This problem is definitely easier if k divides the word size.

Answer 2

Don't use base 10, use base 16.

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

Since integers are stored internally in binary, this will be more efficient than dividing by 10 to determine decimal digits.