Лучший способ получить отдельные цифры от интервала для вида основания в C/C++
Что лучший способ состоит в том, чтобы получить отдельные цифры от интервала с n количеством цифр для использования в алгоритме сортировки основания? Я задаюсь вопросом, существует ли особенно хороший способ сделать это в C/C++, если не, каково общее лучшее решение?
править: просто для уточнения я искал решение кроме преобразования его к строке и рассматривал его как массив цифр.
2 ответа
Используйте цифры размера 2^k. Для извлечения n-й цифры:
#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 разделит размер слова.
Не используйте основание 10, используйте основание 16.
for (int i = 0; i < 8; i++) {
printf("%d\n", (n >> (i*4)) & 0xf);
}
Поскольку целые числа внутри хранятся в двоичном виде, это будет более эффективно, чем деление на 10 для определения десятичных цифр.