başka bir ikili modelle eşleştirilecek tüm 2-bit değerlerini bulun ve sonra onları

Question

İlk Değerini Özetle:

Aslında 2-bit değerlerinin kompakt dizi ikili değeri vardır. (Yani, her 2 bit, ikili değer 0, 1, 2 veya 3'ü temsil eder.) Yani, örneğin 0, 3, 1, 2 00110110 olur. Bu ikili dizede, tek umurumda olan 3'ler (ya da dönüşümlü olarak, bitleri çevirebilirim ve eğer cevabınızı kolaylaştırırsa, sadece 0'lara dikkat edebilirim). Diğer tüm sayılar alakasız (birazdan gireceğimiz için).

İkinci değer:

aynı şekilde temsil aynı zamanda 2-bit değerlerinin bir sıkıştırılmış dizi ikinci bir ikili değere sahiptir. Birinci Değere denk bir uzunluğa sahiptir.

Matematik:

Ben ilk Değerinden bir 3 ile aynı konuma sahip İkinci Değer 2 bitlik sayıların toplamını istiyorum. Ben başka deyişle, eğer: o bir "11 vardı sadece onlar vardı çünkü

First: 11000011 
Second: 01111101 

Sonra cevabım olurdu "2"(Ben, ilk sayı ve birlikte "İkinci" dan son numarayı eklendi "İlk Değer onları eşleşti.) mümkün olduğunca (bir GPU veya bir x86 mimarisine ya olduğunca az saat döngülerinde bunu yapmak istiyor

). Bununla birlikte, genellikle bir algoritma arıyorum, bir assembler çözümü değil. Her sayıdan bir anda iki bitin maskelenmesinden ve birkaç döngüyü çalıştırdığından daha hızlı bir yolu var mı?

Answer 1

Elbette.

// the two numbers 
unsigned int a; 
unsigned int b; 

Şimdi bir maske oluşturmak aynı pozisyonda biten '11' vardı sadece eğer bir tek pozisyonda '1' bit içeren bir olmalıdır.

unsigned int mask = a & (a >> 1) & 0x55555555; 

geri '11' desen almak için genişletin:

:

mask = mask | (mask << 1); 

Yani şimdi bir 1101100011 olsaydı, maske 1100000011.

Ardından maske ile b maske olduğunu

b = b & mask; 

ardından paralel b den (maskeli) sayıların eklenmesini gerçekleştirebilir:

b = (b & 0x33333333) + ((b & 0xcccccccc) >> 2); 
b = (b & 0x0f0f0f0f) + ((b & 0xf0f0f0f0) >> 4); 
b = (b & 0x00ff00ff) + ((b & 0xff00ff00) >> 8); 
b = (b & 0x0000ffff) + ((b & 0xffff0000) >> 16); 

32 bitlik bir sayı için, toplam şu anda b'nin en düşük bitleridir. Bu, bit alanlarının paralel eklenmesi için yaygın olarak bilinen bir modeldir. 32 bitlik sayılardan büyükse, 64 bitlik sayılar için bir tur daha ve 128 bit rakamlar için iki tur eklersiniz.