對於32位整數,將其分成32個連續整數的整數,這樣每個整數的整數連續的箱子。第一個bin包含0,第二個0..1等等直到0..2^31-1。將32位整數映射爲32個bin,每個bin具有1,2,4..2^31個連續整數
最快的算法我能想出,給定一個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是超標量的,因此任何不依賴於彼此的操作都可以並行執行,直到每種指令類型的吞吐量。
既然你提到i7,你可以嘗試將整數轉換爲浮點數並提取指數以得到一個有偏見的bin_index。零需要特別關注。 – 2013-05-14 04:14:43
看起來它不是一個勝利,http://www.agner.org/optimize/instruction_tables.pdf把操作放在一個i7上3 + 2個週期(不確定這裏的+2是什麼意思,但它與3是無關的足以殺死任何可能的收益 – Eloff 2013-05-14 11:33:06
我更喜歡思考SSE單元並且至少並行執行4個操作 – 2013-05-14 13:40:08