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);
Sehr gut, danke! –
@FilippoBistaffa kann es übrigens optimiert werden, wenn die Maske eine Konstante (oder eine Schleifenkonstante) ist. – harold
Ja, in meinem Szenario wäre es eine Konstante, aber ich denke, diese Art der Optimierung wird automatisch vom Compiler durchgeführt. Oder ist es besser, es explizit zu tun? –