c++ - 在 C/C++ 中从 int 获取单个数字以进行基数排序的最佳方法

Question

从具有 n 个数字的 int 中获取单个数字以用于基数排序算法的最佳方法是什么？我想知道在 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;
}

使用移位和掩码(由基数为 2 的幂启用)避免昂贵的整数除法指令。

之后，选择最佳基础是一个实验性问题(针对您的特定硬件进行时间/空间权衡)。可能 k==3 (base 8) 效果很好并且限制了 buckets 的数量，但是 k==4 (base 16) 看起来更有吸引力，因为它划分了单词大小.但是，不划分字长的基数确实没有错，您可能会发现基数 32 或基数 64 的性能更好。这是一个实验性问题，可能会因硬件而异，具体取决于缓存的行为方式以及数组中的元素数量。

最后的说明:如果你正在对有符号整数进行排序，生活会更加痛苦，因为你想将最高有效位视为有符号。我建议将所有内容都视为无符号的，然后如果你真的需要签名，在基数排序的最后一步中你将交换桶，以便具有最高有效 1 的桶出现在最高有效 0 之前。这个问题是 如果 k 除以单词大小，肯定会更容易。