Come posso mischiare i bit in modo efficiente?

Question

Ho bisogno di mescolare un numero intero senza segno a 16 bit in modo che gli indici pari vengano posizionati nel byte inferiore e gli indici dispari vengano posizionati nel byte superiore.

input: 
fedcba(contiguously numbered) 

output: 
fdb97531 eca86420 (even and odd separated) 

mio codice è simile al momento:

typedef unsigned short u16; 

u16 segregate(u16 x) 
{ 
    u16 g = (x & 0x0001); 
    u16 h = (x & 0x0004) >> 1; 
    u16 i = (x & 0x0010) >> 2; 
    u16 j = (x & 0x0040) >> 3; 
    u16 k = (x & 0x0100) >> 4; 
    u16 l = (x & 0x0400) >> 5; 
    u16 m = (x & 0x1000) >> 6; 
    u16 n = (x & 0x4000) >> 7; 

    u16 o = (x & 0x0002) << 7; 
    u16 p = (x & 0x0008) << 6; 
    u16 q = (x & 0x0020) << 5; 
    u16 r = (x & 0x0080) << 4; 
    u16 s = (x & 0x0200) << 3; 
    u16 t = (x & 0x0800) << 2; 
    u16 u = (x & 0x2000) << 1; 
    u16 v = (x & 0x8000); 

    return g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v; 
} 

mi chiedo se c'è una soluzione più elegante che semplicemente estraendo e spostando ogni singolo bit?

Answer 1

C'è una comoda risorsa web che aiuta a risolvere molti problemi po 'di permutazione: Code generator for bit permutations. In questo caso particolare l'alimentazione "0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15" a questa pagina produce codice abbastanza veloce.

Sfortunatamente questo generatore di codice non può produrre codice a 64 bit (sebbene chiunque possa scaricare fonti e aggiungere questa opzione). Quindi se occorre eseguire 4 permutazioni in parallelo con istruzioni a 64 bit, dobbiamo estendere tutti bitmasks interessate a 64 bit manualmente:

uint64_t bit_permute_step(uint64_t x, uint64_t m, unsigned shift) { 
    uint64_t t; 
    t = ((x >> shift)^x) & m; 
    x = (x^t)^(t << shift); 
    return x; 
} 

uint64_t segregate4(uint64_t x) 
{ // generated by http://programming.sirrida.de/calcperm.php, extended to 64-bit 
    x = bit_permute_step(x, 0x2222222222222222ull, 1); 
    x = bit_permute_step(x, 0x0c0c0c0c0c0c0c0cull, 2); 
    x = bit_permute_step(x, 0x00f000f000f000f0ull, 4); 
    return x; 
} 

livello di parallelismo potrebbe essere aumentata ancora di più (8 o 16 permutazioni contemporaneamente) con istruzioni SSE. (E le versioni recenti di gcc possono rendere automaticamente questo codice automaticamente).

Se il parallelismo non è richiesto e la cache di dati non è ampiamente utilizzata da altre parti del programma, un'alternativa migliore sarebbe utilizzare la tabella di ricerca. Vari approacehes LUT sono già discussi in altre risposte, ancora un po 'di più si potrebbe dire qui:

1. Il primo e gli ultimi pezzi di parola a 16 bit non sono mai permutati, abbiamo bisogno di mescolare solo bit 1..14. Quindi (se vogliamo eseguire l'operazione con un singolo accesso LUT) è sufficiente avere un LUT con 16K voci che significa 32K di memoria.
2. Potremmo combinare gli approcci di ricerca tabella e calcolo. Due ricerche in una singola tabella da 256 byte potrebbero mescolare separatamente ciascun byte sorgente. Dopodiché abbiamo solo bisogno di scambiare due bocconcini medi da 4-bit. Ciò consente di mantenere piccola la tabella di ricerca, utilizza solo 2 accessi alla memoria e non richiede troppi calcoli (ad esempio calcoli di saldi e accessi alla memoria).

Ecco realizzazione del secondo approccio:

#define B10(x)   x+0x00,  x+0x10,  x+0x01,  x+0x11 
#define B32(x)  B10(x+0x00), B10(x+0x20), B10(x+0x02), B10(x+0x22) 
#define B54(x)  B32(x+0x00), B32(x+0x40), B32(x+0x04), B32(x+0x44) 
uint8_t lut[256] = {B54( 0x00), B54( 0x80), B54( 0x08), B54( 0x88)}; 
#undef B54 
#undef B32 
#undef B10 

uint_fast16_t segregateLUT(uint_fast16_t x) 
{ 
    uint_fast16_t low = lut[x & 0x00ff]; 
    low |= low << 4; 
    uint_fast16_t high = lut[x >> 8] << 4; 
    high |= high << 4; 
    return (low & 0x0f0f) | (high & 0xf0f0); 
} 

Ma più veloce approccio (se la portabilità non è un problema) sta usando pext istruzioni da istruzioni BMI2 set as noted by Nils Pipenbrinck. Con un paio di pext 64 bit potremmo eseguire 4 shuffle a 16 bit in parallelo. Poiché l'istruzione pext è concepita esattamente per questo tipo di bit di permutazioni, questo approccio supera facilmente tutti gli altri.

Answer 2

È possibile utilizzare una tabella a 256 byte per ogni byte del proprio numero a 16 bit, predisposto in modo che la condizione pari/dispari sia soddisfatta. Inserisci a mano le voci della tabella (o usa l'algoritmo che hai già) per creare le tabelle, e poi lo shuffling sarà fatto in fase di compilazione. Questo sarebbe essenzialmente un concetto di tabella di traduzione.

Answer 3

È possibile utilizzare una tabella a 256 byte per ogni byte del proprio numero a 16 bit, predisposto in modo che la condizione pari/dispari sia soddisfatta.

Ah, sì, tabelle di ricerca per il salvataggio :) Si può anche farlo con una singola tabella e un turno in più:

u16 every_other[256] = { 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f}; 

u16 segregate(u16 x) 
{ 
    return every_other[x & 0xff] 
     | every_other[(x >> 8)] << 4 
     | every_other[(x >> 1) & 0xff] << 8 
     | every_other[(x >> 9)] << 12; 
} 

Answer 4

L'approccio tabella mostrata da altri è la versione più portatile ed è probabilmente abbastanza veloce.

Se si desidera sfruttare set di istruzioni speciali, esistono anche altre opzioni. Per Intel Haswell e successivamente per esempio il seguente metodo può essere usato (richiede l'estensione set di istruzioni BMI2):

unsigned segregate_bmi (unsigned arg) 
{ 
    unsigned oddBits = _pext_u32(arg,0x5555); 
    unsigned evenBits = _pext_u32(arg,0xaaaa); 
    return (oddBits | (evenBits << 8)); 
} 

Answer 5

tabelle. Ma generali in fase di compilazione!

namespace details { 
    constexpr uint8_t bit(unsigned byte, unsigned n) { 
    return (byte>>n)&1; 
    } 
    constexpr uint8_t even_bits(uint8_t byte) { 
    return bit(byte, 0) | (bit(byte, 2)<<1) | (bit(byte, 4)<<2) | (bit(byte, 6)<<3); 
    } 
    constexpr uint8_t odd_bits(uint8_t byte) { 
    return even_bits(byte/2); 
    } 
    template<unsigned...>struct indexes{using type=indexes;}; 
    template<unsigned Max,unsigned...Is>struct make_indexes:make_indexes<Max-1,Max-1,Is...>{}; 
    template<unsigned...Is>struct make_indexes<0,Is...>:indexes<Is...>{}; 
    template<unsigned Max>using make_indexes_t=typename make_indexes<Max>::type; 

    template<unsigned...Is> 
    constexpr std::array< uint8_t, 256 > even_bit_table(indexes<Is...>) { 
    return { even_bits(Is)... }; 
    } 
    template<unsigned...Is> 
    constexpr std::array< uint8_t, 256 > odd_bit_table(indexes<Is...>) { 
    return { odd_bits(Is)... }; 
    } 
    constexpr std::array< uint8_t, 256 > even_bit_table() { 
    return even_bit_table(make_indexes_t<256>{}); 
    } 
    constexpr std::array< uint8_t, 256 > odd_bit_table() { 
    return odd_bit_table(make_indexes_t<256>{}); 
    } 

    static constexpr auto etable = even_bit_table(); 
    static constexpr auto otable = odd_bit_table(); 
} 

uint8_t constexpr even_bits(uint16_t in) { 
    return details::etable[(uint8_t)in] | ((details::etable[(uint8_t)(in>>8)])<<4); 
} 
uint8_t constexpr odd_bits(uint16_t in) { 
    return details::otable[(uint8_t)in] | ((details::otable[(uint8_t)(in>>8)])<<4); 
} 

live example

Answer 6

A favore di essere breve:

unsigned short segregate(unsigned short x) 
{ 
    x = (x & 0x9999) | (x >> 1 & 0x2222) | (x << 1 & 0x4444); 
    x = (x & 0xC3C3) | (x >> 2 & 0x0C0C) | (x << 2 & 0x3030); 
    x = (x & 0xF00F) | (x >> 4 & 0x00F0) | (x << 4 & 0x0F00); 
    return x; 
} 

Answer 7

la risposta ai bit pari e dispari casuale per 64 bit non è esatto. Per estendere la soluzione a 16 bit per una soluzione a 64 bit, abbiamo bisogno non solo di estendere le maschere, ma anche coprire l'intervallo di scambio da 1 fino a 16:

x = bit_permute_step(x, 0x2222222222222222, 1); 
x = bit_permute_step(x, 0x0c0c0c0c0c0c0c0c, 2); 
x = bit_permute_step(x, 0x00f000f000f000f0, 4); 
**x = bit_permute_step(x, 0x0000ff000000ff00, 8); 
x = bit_permute_step(x, 0x00000000ffff0000, 16);**