Mask e bit aggregati

Question

sto cercando di eseguire in modo efficiente l'attività seguente:

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

Spero che questo esempio spiega chiaramente quello che sto cercando di realizzare. Qual è il modo migliore per farlo in modo non ingenuo?

Answer 1

Questa operazione è denominata compress_right o solo compress ed è moderatamente terribile da implementare senza supporto hardware. Il codice non-naive dal piacere del Hacker "7-4 compressa, o estratto generalizzate" per attuare questa funzione è

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 (implementato in Haswell e successive) avrà l'istruzione pext per questa operazione.

---

Se la maschera è una costante (o non è una costante, ma riutilizzati più volte), un'ottimizzazione relativamente ovvio è pre-calcolando i 5 valori che mv assume durante il ciclo. Il calcolo dei mv non dipende x, in modo che può essere calcolato in modo indipendente, così (lo stesso algoritmo sopra realmente)

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; 
} 

sembra ancora complicato, ma tutto qui è una costante, in modo che possa essere pre -computato (se il compilatore non può farlo, allora si può può, semplicemente eseguendolo e quindi incollando il risultato nel codice). La "parte reale" del codice, il codice che ha effettivamente a funzionare in fase di esecuzione è questo:

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); 

(questo è anche in Delight di Hacker, formattato in modo leggermente diverso)

Molti casi possono essere più semplice di nuovo, ad esempio:

• se m = 0, il risultato è 0.
• se m = -1, il risultato è x.
• se m = 1, il risultato è x & 1.
• se m = ((1 << n) - 1) << k, il risultato è (x >> k) & m.
• se m = 0x80000000, il risultato è x >> 31.
• se m è un'altra potenza di due, il risultato è (x >> numberOfTrailingZeros(m)) & 1
• se m si alterna, il "algoritmo unshuffle perfetto" può essere usato.
• se m è costituito da pochi "gruppi", è possibile utilizzare l'algoritmo "spostamento di gruppi di bit" (cioè mascherare un gruppo, spostarlo in posizione (o spostare prima, seconda maschera), O tutti i gruppi spostati insieme, anche se più esistono approcci sofisticati), questo è probabilmente il caso più importante nella pratica.
• ...

Per esempio, la maschera dalla tua domanda rientra nella definizione del "gruppo di bit in movimento" caso, con il codice come questo:

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