Eine Zahl, die nur die ungeraden (oder gerade) Bits einer anderen Zahl ist

Question

Sagen wir, ich habe einige 128-Bit-Zahl n:

0b10010101110101010101 ...

Und ich möchte zwei neue 64-Bit konstruieren Zahlen, von denen eine aus den ungeraden Bits in n besteht und von denen eine aus den geraden Bits in n besteht. Ich kann dies tun, indem ich jedes Bit einzeln maskiere und es setze, aber ich frage mich, ob es einen schnelleren Algorithmus gibt.

Dies ist der Algorithmus I (in Ruby) verwendet, dies zu tun:

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 

Gibt es eine effizientere Art und Weise, es zu tun, sagen mit einer konstanten oder log (n_bits) Anzahl von Bit-Operationen?

Answer 1

Sie könnten einige k-Bit-weite Nachschlagetabellen (mit k etwa 4, 8 oder 16) vorberechnen, die die "ungeraden" und "geraden" Bits des Nachschlage-Indexes enthalten, und dann Nachschlagetabellen für n/k-Tabellen durchführen und setze sie durch Verschieben und Maskieren wieder zusammen.

Für ein gegebenes k benötigen Sie noch O (n_bits) -Operationen für jedes verarbeitete Bitmuster mit etwas Overhead, um die Tabellen zu erstellen. Aber wenn Sie diese Operation viele Male ausführen, ist es wahrscheinlich immer noch effizienter, die Nachschlagetabellen zu verwenden, anstatt sie jeweils ein Bit zu machen.