c - 将 32 位整数映射到 32 个 bin，每个 bin 有 1,2,4..2^31 个连续整数

Question

对于一个 32 位整数，将其分成 32 个连续整数的 bin，这样每个连续的 bin 中的整数都是原来的两倍。第一个 bin 包含 0，第二个 0..1，等等直到 0..2^31-1。

我能想到的最快算法，给定一个 32 位整数 i，在 i7 上是 5 个周期(位扫描是 3 个周期):

// bin is the number of leading zeroes, and then we clear the msb to get item
bin_index = bsr(i)
item = i ^ (1 << bin_index)

或者等价地(它将项目 0..2^(32-1) 存储在 bin 0 中，将 0 存储在 bin 31 中，但这并不重要):

// bin is the number of trailing zeroes, and then we shift down by that many bits + 1
bin_index = bsf(i)
item = i >> (bin_index + 1)

在每种情况下，bin 索引都被编码为前导/尾随零位的数量，并用 1 将它们与项目编号分开。您可以对前导或尾随的数字执行相同的操作，并用零分隔它们。两者都不适用于 i=0，但这并不重要。

整数和 bins/items 之间的映射可以是完全任意的，只要每个连续 bin 中的连续整数的两倍多并且 bins 中的整数总数总和为 2^32-1 即可。你能想出一种更有效的算法来将 32 个整数装箱到 i7 上吗？请记住，i7 是超标量的，因此任何不依赖于彼此的操作都可以并行执行，最高可达每种指令类型的吞吐量。

Answer 1

您可以尝试在计算零之前先对数据进行排序，从而改进您的算法。

例如，首先将它与 2^31 进行比较，如果它更大，则将其放入该容器中，否则继续计算尾随零。有了这个，你现在有一半的数据集在 2 条指令中放入它的 bin 中......可能是两个周期。另一半需要更长的时间，但最终结果会有所改善。如果考虑的话，您可能可以进一步优化此行。

我想这也取决于分支预测的效率。