Jak mogę wydajnie przetasować bity?

Question

Muszę przetasować 16-bitową liczbę całkowitą bez znaku w taki sposób, aby indeksy parzystości wylądowały w dolnym bajcie, a indeksy nieparzyste wylądowały w górnym bajcie.

input: 
fedcba(contiguously numbered) 

output: 
fdb97531 eca86420 (even and odd separated) 

Mój kod wygląda w tej chwili:

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

Zastanawiam się, czy istnieje bardziej eleganckie rozwiązanie niż po prostu ekstrakcji i przesuwanie każdy pojedynczy bit?

Answer 1

Jest bardzo wygodny zasobów internetowych, które pomaga rozwiązać wiele problemów nieco permutacji: Code generator for bit permutations. W tym szczególnym przypadku karmienie "0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15" na tej stronie daje dość szybki kod.

Niestety ten generator kodu nie może wygenerować kodu 64-bitowego (chociaż każdy mógł pobrać źródła i dodać tę opcję). Więc jeśli musimy wykonać 4 permutacje równolegle za pomocą instrukcji 64-bitowych, musimy rozszerzyć wszystkich zaangażowanych bitmasks do 64 bitów ręcznie:

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

Poziom równoległości może wzrosnąć nawet więcej (8 lub 16 permutacje naraz) z instrukcjami SSE. (A ostatnie wersje gcc mogą wektoryzować ten kod automatycznie).

Jeśli równoległość nie jest wymagana, a pamięć podręczna danych nie jest szeroko wykorzystywana przez inne części programu, lepszym rozwiązaniem byłoby użycie tabeli odnośników. Różne LUT approacehes zostały już omówione w innych odpowiedzi, jeszcze trochę więcej można powiedzieć tutaj:

1. Pierwsze i ostatnie bity z 16-bitowym słowem nigdy nie są przesuwane, musimy tylko losowe bity 1..14. Tak więc (jeśli chcemy wykonać zadanie z pojedynczym dostępem LUT) wystarczy mieć LUT z wpisami 16K, co oznacza 32K pamięci.
2. Moglibyśmy łączyć wyszukiwanie tabel i podejścia obliczeniowe. Dwa wyszukiwania w pojedynczej 256-bajtowej tabeli mogą losowo przetasować każdy bajt źródłowy. Następnie wystarczy wymienić dwa środkowe 4-bitowe przekąski. Pozwala to zachować niewielką tablicę przeglądową, wykorzystuje tylko 2 dostępy do pamięci i nie wymaga zbyt wielu obliczeń (tj. Obliczeń sald i dostępu do pamięci).

Oto realizacja drugiego podejścia:

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

Ale najszybszy podejście (jeśli przenośność nie jest problemem) korzysta pext dyspozycję instrukcją BMI2 ustawiony as noted by Nils Pipenbrinck. Za pomocą pary 64-bitowych pext mogliśmy równolegle wykonywać 4 16-bitowe tasowania. Ponieważ instrukcja pext jest przeznaczona właśnie dla tego rodzaju permutacji bitowych, to podejście łatwo przewyższa wszystkie inne.

Answer 2

Do każdego bajtu 16-bitowego numeru można użyć tabeli o długości 256 bajtów, utworzonej tak, aby spełniony był warunek parzysty/nieparzysty. Ręcznie koduj wpisy w tabeli (lub użyj algorytmu, który już masz), aby utworzyć tabele, a następnie tasowanie zostanie wykonane w czasie kompilacji. Zasadniczo byłaby to koncepcja tabeli tłumaczeń.

Answer 3

Można użyć tabeli 256 bajtów na każdy bajt numeru 16-bitowym, wykonane tak, że nawet/nieparzysty warunek jest spełniony.

Ach tak, tablice przeglądowe na ratunek :) Można nawet zrobić to z jednej tabeli i jeden dodatkowy Shift:

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

Podejście tabeli przedstawione przez innych jest najbardziej przenośna wersja i jest prawdopodobnie dość szybko.

Jeśli chcesz skorzystać ze specjalnych zestawów instrukcji, istnieją również inne opcje. W przypadku Intel Haswell, a później na przykład, można zastosować następujące podejście (wymaga rozszerzenia zestawu instrukcji BMI2):

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

Answer 5

Tabele. Ale generuj je podczas kompilacji!

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

Na korzyść będąc skrócie:

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

odpowiedź na parzystych i nieparzystych bitów do 64 bitów przetasować nie jest dokładna. Aby rozszerzyć rozwiązanie 16 bitowej do 64-bitowej rozwiązania, musimy nie tylko przedłużenie maski, ale również obejmować przedział swapping od 1 aż do 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);**