一些這僅僅是另一個數

說奇（甚至）位，我有一些128位的數n：一些這僅僅是另一個數

0b10010101110101010101 ...

而且我要興建兩個新的64位數字，其中之一由n中的奇數位組成，其中一個由n中的偶數位組成。我可以通過單獨掩飾每個位並設置它來做到這一點，但我想知道是否有更快的算法。

這是我以前（在Ruby中）的算法來做到這一點：

n=0xAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 

odds=0 
evens=0 
0.upto(63) do |i| 
    even_mask = 1 << (2*i) 
    odd_mask = 1 << ((2*i)+1) 
    pos_mask = 1 << i 
    evens = (evens | pos_mask) if (n & even_mask) != 0 
    odds = (odds | pos_mask) if (n & odd_mask) != 0 
end 

puts odds.to_s(16) 
>> ffffffffffffffff 

puts evens.to_s(16) 
>> 0

有沒有更有效的方式來做到這一點，利用說恆定或登錄位操作（n_bits）是多少？

來源

2012-03-27 nohat

有一種快速的方法來做你所問的對象：http://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious – 2012-03-27 00:44:04

您可以預先計算查找索引中「odd」和「even」位的一些k位查找表（k爲類似於4,8或16的查找表），然後執行n/k表查找並通過移位和掩蔽重新組裝它們。

對於給定的k，對於每個處理的位模式，您仍然需要O（n_bits）操作，並且還需要一些開銷來構建表。但是如果你正在做這個操作很多次，那麼使用查找表可能會更有效率，而不是一次只做一次。

來源

2012-03-27 00:43:44

我喜歡你的想法。我需要完成同樣的事情，只有我必須解開N個單獨的頻道，其中n可以從2到1000！（我正在使用BigInegers。） – 2012-04-04 17:57:12

一些這僅僅是另一個數

回答

相關問題