algorithm - 桶大小不同的桶排序

Question

我试图根据不断变化的范围将 0..2^12 之间的所有数字分成 4 个桶。

例如，我有 [0, 1000, 2100, 4000, 4096]，所以我有 4 个桶:[0-1000]、[1000-2100]、[2100-4000]、[4000-4096]。

我如何构建一个将每个数字放入正确数字中的函数 - 没有 if、switch cases 等。

我需要一些非常高效的东西，所以我正在寻找按位运算，或者先进行加法\减法，然后再进行按位运算。

Answer 1

输入的形式为 [0, a, b, c, 4096]。如果您不介意预先计算，您可以使用建议的数组。否则，您可以根据以下假设做类似的事情:

• 32 位有符号数
• 桶:
  • n
  • a <= n < b
  • b <= n < c
  • n >= c
• 桶标记为 0 到 3。

3 - ((n - a) >> 31) - ((n - b) >> 31) - ((n - c) >> 31)

想法是，如果数字变为负数，则最高位将被设置，并且通过将其移动 31 个位置，您将得到 1。

您也可以只将 3 个相减的表达式相加得到 4 个桶，但第 0 个桶包含最高的数字。