Bitler nasıl ayrılır (UnMortonizing?)

Question

Bit'leri 32 bit int'den ayırmanın en etkili yolu nedir? Bu özel durum için, ben sadece tek bitler hakkında endişe ediyorum, her iki set için herhangi bir çözümün genelleştirilmesi kolay olsa da eminim. Örneğin, 0b01000101'u 0b1011 içine dönüştürmek istiyorum. En hızlı yol nedir?

DÜZENLEME: Bu uygulamada

, hatta bitleri tamamen sıfırlı olduğunu garanti edemez. Hızını arttırmak veya alanı azaltmak için bu gerçeğin avantajlarından yararlanabilir miyim?

Answer 1

Eğer her bit uygulamanızda 0 olduğunu biliyoruz göz önüne alındığında, bunu şöyle yapabilirsiniz:

0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p x 
| 00a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0 x >> 1 
    -------------------------------- 
= 0aabbccddeeffgghhiijjkkllmmnnoop x | (x >> 1) 
& 00110011001100110011001100110011 0x33333333 
    -------------------------------- 
= 00ab00cd00ef00gh00ij00kl00mn00op (x | (x >> 1)) & 0x33333333 

Sonra ikinci adım:

x = (x | (x >> 1)) & 0x33333333; 
x = (x | (x >> 2)) & 0x0f0f0f0f; 
x = (x | (x >> 4)) & 0x00ff00ff; 
x = (x | (x >> 8)) & 0x0000ffff; 

ilk adım şöyle Bir seferde iki bit ile çalışır, vb.

Answer 2

Hız açısından bakıldığında, 2^32 girişleri ile geniş bir arama tablosu 16 bit zor olacak! Ancak bu kadar fazla belleğiniz yoksa, 256 girişli bir tabloda dört arama, artı birkaç vardiya ve bunları birleştirmek için AND'ler daha iyi bir seçenek olabilir. Ya da belki de tatlı nokta arasında bir yerde ... var olan kaynaklara bağlıdır ve arama tablosunu başlatma maliyetinin, gerçekleştirmeniz gereken arama sayısı üzerinden nasıl amorti edileceği.

Answer 3

öyle olacağını nasılhızlı emin değilim, ancak bir kapalı tüm tek bitleri çekin ve b koyacağımı Hangi

int a = 0b01000101; 
int b = 0; 
int i = 0; 
while (a > 0) { 
    b |= (a & 1) << i; 
    a >>= 2; 
} 

gibi bir şey yapabilirdi.