Число, которое является просто нечетными (или четными) битами другого числа - PullRequest
Новая
       6

Число, которое является просто нечетными (или четными) битами другого числа

1 голос
/ 27 марта 2012

Скажем, у меня есть 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) количество побитовых операций?

1 Ответ

2 голосов
/ 27 марта 2012

Вы можете предварительно рассчитать некоторые таблицы поиска шириной в k бит (где k равно 4, 8 или 16), удерживая «нечетные» и «четные» биты индекса поиска, затем выполнить n / k поиск таблицы иСоберите их с помощью сдвига и маскирования.

Для данного k вам все еще нужно O (n_bits) операций для каждого обработанного битового шаблона, с некоторыми накладными расходами для построения таблиц.Но если вы выполняете эту операцию много раз, вероятно, будет все же более эффективно использовать таблицы поиска, а не делать это по одному биту за раз.

...