將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條指令中......可能是兩個週期。另一半需要更長的時間，但最終的結果將是一個改進。如果想到的話，你可能會進一步優化這條線。

我想這也將取決於分支預測的效率。