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

Question

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

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

Answer 1

Используйте цифры размера 2^k. Чтобы извлечь n th цифру:

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

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

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

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

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

Answer 2

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

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

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