c++ - C/C++で基数ソートのためにintから個々の数字を取得する最良の方法

Question

基数ソートアルゴリズムで使用する n 桁の int から個々の桁を取得する最良の方法は何ですか? C/C++でそれを行うための特に良い方法があるかどうか疑問に思っています.一般的な最善の解決策は何ですか?

編集：明確にするために、文字列に変換して数字の配列のように扱う以外の解決策を探していました。

Answer 1

サイズの数字を使用します2^k。n3桁目を抽出するには：

#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);
}

整数は 2 進数で内部的に格納されるため、これは 10 で割って 10進数を決定するよりも効率的です。