Maske und Summenbits

Question

Ich versuche, die folgende Aufgabe effizient auszuführen:

INPUT VALUE: 01101011 
MASK:  00110010 
MASK RESULT: --10--1- 
AGGREGATED: 00000101 

Ich hoffe, dass diese Beispiele erklärt klar, was ich zu erreichen bin versucht. Was ist der beste Weg, dies in einer nicht-naiven Weise zu tun?

Answer 1

Diese Operation heißt compress_right oder nur compress, und es ist moderat schrecklich, ohne Hardware-Unterstützung zu implementieren. Der nicht-naive Code von Hacker Delight "7-4 Kompresse oder Generalized Extract" um diese Funktion zu implementieren ist

unsigned compress(unsigned x, unsigned m) { 
    unsigned mk, mp, mv, t; 
    int i; 
    x = x & m; // Clear irrelevant bits. 
    mk = ~m << 1; // We will count 0's to right. 
    for (i = 0; i < 5; i++) { 
     mp = mk^(mk << 1); // Parallel suffix. 
     mp = mp^(mp << 2); 
     mp = mp^(mp << 4); 
     mp = mp^(mp << 8); 
     mp = mp^(mp << 16); 
     mv = mp & m;  // Bits to move. 
     m = m^mv | (mv >> (1 << i)); // Compress m. 
     t = x & mv; 
     x = x^t | (t >> (1 << i)); // Compress x. 
     mk = mk & ~mp; 
    } 
    return x; 
} 

BMI2 (in Haswell umgesetzt und später) wird pext für diese Operation die Anweisung haben.

---

Wenn die Maske eine Konstante (oder keine Konstante, sondern mehrmals wiederverwendet), eine relativ offensichtlich Optimierung vorge Berechnung der Werte, die 5 mv während der Schleife statt. Die Berechnung der mv hängt nicht von x, so dass unabhängig voneinander berechnet werden, wie dieser (dem gleichen Algorithmus wie oben wirklich)

mk = ~m << 1; 
for (i = 0; i < 5; i++) { 
    mp = mk^(mk << 1); 
    mp = mp^(mp << 2); 
    mp = mp^(mp << 4); 
    mp = mp^(mp << 8); 
    mp = mp^(mp << 16); 
    mv = mp & m; 
    mask[i] = mv; 
    m = m^mv | (mv >> (1 << i)); 
    mk = mk & ~mp; 
} 

Noch sieht kompliziert aus, aber alles hier ist eine Konstante, so kann es im Voraus werden -computed (wenn der Compiler es nicht kann, dann Sie können, einfach durch Ausführen und Einfügen des Ergebnisses in den Code). Der „Realteil“ des Codes, der Code, muss tatsächlich zur Laufzeit führt dies:

x = x & m; 
t = x & mask[0]; 
x = x^t | (t >> 1); 
t = x & mask[1]; 
x = x^t | (t >> 2); 
t = x & mask[2]; 
x = x^t | (t >> 4); 
t = x & mask[3]; 
x = x^t | (t >> 8); 
t = x & mask[4]; 
x = x^t | (t >> 16); 

(dies ist auch in Hacker Delight, formatierte ein wenig anders)

Viele Fälle können einfacher sein wieder, zum Beispiel:

• wenn m = 0, ist das Ergebnis 0.
• Wenn m = -1, ist das Ergebnis x.
• Wenn m = 1, ist das Ergebnis x & 1.
• Wenn m = ((1 << n) - 1) << k, ist das Ergebnis (x >> k) & m.
• Wenn m = 0x80000000, ist das Ergebnis x >> 31.
• m wenn eine andere Zweierpotenz ist, ist das Ergebnis (x >> numberOfTrailingZeros(m)) & 1
• wenn m alterniert, der „perfekte unshuffle Algorithmus“ verwendet werden kann.
• Wenn m aus ein paar "Gruppen" besteht, kann der "Bit Group Moving" -Algorithmus verwendet werden (dh eine Gruppe maskieren, verschieben oder verschieben, ODER alle verschobenen Gruppen zusammen) ausgereifte Ansätze existieren), ist dies wahrscheinlich der wichtigste Fall in der Praxis.
• ...

Zum Beispiel würde fällt die Maske aus Ihrer Frage in der Fall, mit Code wie diese „Bitgruppe bewegt“:

return ((x >> 1) & 1) | ((x >> 3) & 6);