Лучший способ получить индивидуальные цифры из INT для Radix Сортировать в C / C ++

Question

Какой лучший способ получить индивидуальные цифры от INT с N количество цифр для использования в алгоритме Sort Radix? Я задаюсь вопросом, есть ли особенно хороший способ сделать это в C / C ++, если не то, что такое общее лучшее решение?

Редактировать: Просто чтобы уточнить, я искал решение, отличное от преобразования его в строку и обрабатывать его как массив цифр.

Answer 1

Использовать цифры размера 2^k. Отказ Извлечь nцифра:

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

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

Используя Shift и Mask (включено by base - мощность 2), избегает дорогостоящих целочисленных инструкций.

После этого выбирая лучшую базу является экспериментальным вопросом (срок компромиссы времени / пространства для вашего конкретного оборудования). Наверное k==3 (База 8) хорошо работает и ограничивает количество ведер, но k==4 (База 16) выглядит более привлекательно, потому что он разделяет размер слова. Однако на самом деле нет ничего плохого в базе, которая не разделяет размер слов, и вы можете обнаружить, что база 32 или базы 64 выполняет лучше. Это экспериментальный вопрос и, скорее всего, отличается аппаратным обеспечением, в соответствии с тем, как ведет себя кэш и сколько элементов существует в вашем массиве.

Последнее примечание: если вы сортировка подписанный Число целых чисел - гораздо большая боль, потому что вы хотите относиться к самому значению, как подписано. Я рекомендую лечить все как неподписанные, а затем, если вам действительно нужно подписать, на последнем этапе своего RADIX, вы поменяете ведра, чтобы ведра с наиболее значительными 1 пришли до самого значительного 0. Эта проблема определенно легче, если k делит размер слова.

Answer 2

Не используйте базу 10, используйте базу 16.

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

Поскольку целые числа хранятся внутри двоичных данных, это будет более эффективно, чем деление на 10, чтобы определить десятичная дробь цифры.