一些这仅仅是另一个数

说奇（甚至）位，我有一些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

一些这仅仅是另一个数

回答

相关问题