Spostare i bit mascherati sull'lsb

Question

Quando si immettono alcuni dati con una maschera su and, si ottiene un risultato che ha le stesse dimensioni dei dati/maschera. Quello che voglio fare è prendere i bit mascherati nel risultato (dove c'era 1 nella maschera) e spostarli a destra in modo che siano uno accanto all'altro e posso eseguire un CTZ (Count Trailing Zeroes) su loro.

Non sapevo come denominare una tale procedura, così Google mi ha fallito. L'operazione preferibilmente dovrebbe essere non una soluzione loop, questa operazione deve essere il più veloce possibile.

Ed ecco un'immagine incredibile realizzata in MS Paint.

Answer 1

Questa operazione è nota come compress right. È implementato come parte di BMI2 come istruzione PEXT, in processori Intel come Haswell.

Sfortunatamente, senza supporto hardware è un'operazione piuttosto fastidiosa. Naturalmente v'è una soluzione ovvia, semplicemente spostando i bit uno per uno in un ciclo, ecco quella data da hacker Delight:

unsigned compress(unsigned x, unsigned m) { 
    unsigned r, s, b; // Result, shift, mask bit. 

    r = 0; 
    s = 0; 
    do { 
     b = m & 1; 
     r = r | ((x & b) << s); 
     s = s + b; 
     x = x >> 1; 
     m = m >> 1; 
    } while (m != 0); 
    return r; 
} 

Ma c'è un altro modo, proposta anche da hacker Delight, che fa meno loop (numero di iterazioni logaritmico del numero di bit), ma più per iterazione:

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

noti che molti dei valori non dipende solo m. Dal momento che hai solo 512 diverse maschere, si potrebbe precompute quelle e semplificare il codice a qualcosa di simile (non testato)

unsigned compress(unsigned x, int maskindex) { 
    unsigned t; 
    int i; 

    x = x & masks[maskindex][0]; 

    for (i = 0; i < 5; i++) { 
     t = x & masks[maskindex][i + 1]; 
     x = x^t | (t >> (1 << i)); 
    } 
    return x; 
} 

Naturalmente tutti questi può essere trasformato in "non un ciclo" di srotolamento, il secondo e le terze vie sono probabilmente più adatte a questo. Questo è un po 'di cheat comunque.

Answer 2

È possibile utilizzare la tecnica di moltiplicazione multipla simile a quella descritta here. In questo modo non hai bisogno di loop.

Ad esempio con la maschera 0b10101001 == 0xA9 come sopra e dati a 8 bit abcdefgh (con ah è 8 bit) è possibile utilizzare l'espressione basso per ricevere 0000aceh

unsigned compress_maskA9(unsigned x) 
{ 
    const unsigned mask = 0xA9; 
    const unsigned mask1 = mask & 0xF0; 
    const unsigned mask2 = mask & 0x0F; 
    return (((x & mask1)*0x03000000 >> 28) & 0x0C) | ((x & mask2)*0x50000000 >> 30); 
} 

In questo caso ci sono alcune sovrapposizioni di i 4 bit quando si moltiplicano quindi li divido in 2 parti, il primo estrae i bit a e c, quindi e eh verranno estratti nell'ultima parte.

si possono vedere i risultati confrontati con la funzione di Harold live on ideone

Se si desidera che i bit del risultato invertito è possibile modificare facilmente il numero magico di conseguenza.

unsigned compress_maskA9_reversed1(unsigned x) 
{ 
    // result: he00 | 00ca; 
    return (((x & 0x09)*0x88000000 >> 28) & 0x0C) | (((x & 0xA0)*0x04800000) >> 30); 
} 

o è possibile estrarre il 3 bit E, C e, allo stesso tempo, lasciando h separatamente a causa di alcuni pezzi di sovrapposizione:

unsigned compress_maskA9_reversed(unsigned x) 
{ 
    return ((x & 0xA8)*0x12400000 >> 29) | (x & 0x01) << 3; // result: 0eca | h000 
} 

Correttezza controllo: http://ideone.com/PYUkty

Per un un numero maggiore di maschere è possibile precomputare i numeri magici corrispondenti a quella maschera e memorizzarli in un array per un uso successivo.

---

Spiegazione

Abbiamo abcdefgh & mask1 = a0c00000

 ........................a0c00000 
x 00000011000000000000000000000000 (magic1 = 0x03000000) 
__________________________________________________________________ 
    a0c00000........................ 
+ a0c00000......................... (the leading "a" bit is outside int's range so it'll be truncated 
    ↓↓ 
__________________________________________________________________  
r1 = acc............................. 

=> (r1 >> 28) & 0x0C = 0000ac00 

Allo stesso modo abcdefgh & mask2 = 0000e00h

 ........................0000e00h 
x  01010000000000000000000000000000 (magic2 = 0x50000000) 
__________________________________________________________________ 
    0000e00h............................ 
+ 0000e00h.............................. 
     ↓↓ 
__________________________________________________________________  
    r2 = eh.............................. 

=> (r2 >> 30) = 000000eh 

Pertanto

((r1 >> 28) & 0x0C) | (r2 >> 30) = 0000aceh