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

Question

对于32位整数，将其分成32个连续整数的整数，这样每个整数的整数连续的箱子。第一个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）在0仓和仓31 0，但是这并不重要）：

// 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，但这并不重要。

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

Answer 1

通过在计数零之前尝试对数据进行排序，可以改进算法。

例如，首先将其与2^31进行比较，如果其较大者将其放入该垃圾箱，则继续计算尾部零。有了这个，你现在有一半的数据集放入它的bin在2条指令中......可能是两个周期。另一半需要更长的时间，但最终的结果将是一个改进。如果想到的话，你可能会进一步优化这条线。

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