Best way to get individual digits from int for radix sort in C/C++

Question

What is the best way to get individual digits from an int with n number of digits for use in a radix sort algorithm? I'm wondering if there is a particularly good way to do it in C/C++, if not what is the general best solution?

edit: just to clarify, i was looking for a solution other than converting it to a string and treating it like an array of digits.

Answer 1

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.

Answer 2

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.