Najbardziej wydajny algorytm odwracania bitów (z MSB->LSB do LSB - > MSB) w C [zamknięty]

Ten wątek przykuł moją uwagę, ponieważ zajmuje się prostym problemem, który wymaga dużo pracy (cykli procesora) nawet dla nowoczesnego procesora. I pewnego dnia stałem tam z tym samym problemem. Musiałem przerzucić miliony bajtów. Jednak Wiem, że wszystkie moje systemy docelowe są nowoczesne oparte na Intelu, więc zacznijmy optymalizację do skrajności!!!

Matt J ' s lookup bitflipping 400 000 000 bajtów: około 0.272 sekund.

Potem poszedłem do przodu i próbowałem sprawdzić, czy kompilator Intela ISPC może wektoryzować arytmetykę w odwrotnej kolejności.c.

Nie będę cię zanudzał moimi odkryciami, ponieważ próbowałem wiele pomóc kompilatorowi znaleźć rzeczy, tak czy inaczej skończyłem z wydajnością około 0.15 sekund do bitflip 400 000 000 bajtów. To świetna redukcja, ale dla mojego zastosowania to wciąż zbyt wolne..

Więc ludzie pozwólcie, że przedstawię najszybszy bitflipper oparty na Intelu na świecie. Taktowany w:

Time to bitflip 400000000 bajtów: 0.050082 sekund !!!!!

// Bitflip using AVX2 - The fastest Intel based bitflip in the world!!
// Made by Anders Cedronius 2014 (anders.cedronius (you know what) gmail.com)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <omp.h>

using namespace std;

#define DISPLAY_HEIGHT  4
#define DISPLAY_WIDTH   32
#define NUM_DATA_BYTES  400000000

// Constants (first we got the mask, then the high order nibble look up table and last we got the low order nibble lookup table)
__attribute__ ((aligned(32))) static unsigned char k1[32*3]={
        0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,
        0x00,0x08,0x04,0x0c,0x02,0x0a,0x06,0x0e,0x01,0x09,0x05,0x0d,0x03,0x0b,0x07,0x0f,0x00,0x08,0x04,0x0c,0x02,0x0a,0x06,0x0e,0x01,0x09,0x05,0x0d,0x03,0x0b,0x07,0x0f,
        0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0,0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0
};

// The data to be bitflipped (+32 to avoid the quantization out of memory problem)
__attribute__ ((aligned(32))) static unsigned char data[NUM_DATA_BYTES+32]={};

extern "C" {
void bitflipbyte(unsigned char[],unsigned int,unsigned char[]);
}

int main()
{

    for(unsigned int i = 0; i < NUM_DATA_BYTES; i++)
    {
        data[i] = rand();
    }

    printf ("\r\nData in(start):\r\n");
    for (unsigned int j = 0; j < 4; j++)
    {
        for (unsigned int i = 0; i < DISPLAY_WIDTH; i++)
        {
            printf ("0x%02x,",data[i+(j*DISPLAY_WIDTH)]);
        }
        printf ("\r\n");
    }

    printf ("\r\nNumber of 32-byte chunks to convert: %d\r\n",(unsigned int)ceil(NUM_DATA_BYTES/32.0));

    double start_time = omp_get_wtime();
    bitflipbyte(data,(unsigned int)ceil(NUM_DATA_BYTES/32.0),k1);
    double end_time = omp_get_wtime();

    printf ("\r\nData out:\r\n");
    for (unsigned int j = 0; j < 4; j++)
    {
        for (unsigned int i = 0; i < DISPLAY_WIDTH; i++)
        {
            printf ("0x%02x,",data[i+(j*DISPLAY_WIDTH)]);
        }
        printf ("\r\n");
    }
    printf("\r\n\r\nTime to bitflip %d bytes: %f seconds\r\n\r\n",NUM_DATA_BYTES, end_time-start_time);

    // return with no errors
    return 0;
}

Printf są do debugowania..

Oto koń pociągowy:

bits 64
global bitflipbyte

bitflipbyte:    
        vmovdqa     ymm2, [rdx]
        add         rdx, 20h
        vmovdqa     ymm3, [rdx]
        add         rdx, 20h
        vmovdqa     ymm4, [rdx]
bitflipp_loop:
        vmovdqa     ymm0, [rdi] 
        vpand       ymm1, ymm2, ymm0 
        vpandn      ymm0, ymm2, ymm0 
        vpsrld      ymm0, ymm0, 4h 
        vpshufb     ymm1, ymm4, ymm1 
        vpshufb     ymm0, ymm3, ymm0         
        vpor        ymm0, ymm0, ymm1
        vmovdqa     [rdi], ymm0
        add     rdi, 20h
        dec     rsi
        jnz     bitflipp_loop
        ret

Kod zajmuje 32 bajty, a następnie maskuje skubanie. Wysokie zagięcie przesuwa się w prawo o 4. Następnie używam vpshufb i ymm4 / ymm3 jako tabel wyszukiwania. Mógłbym użyć jednej tabeli wyszukiwania, ale wtedy musiałbym przesunąć w lewo przed ORing gryzaki razem ponownie.

Proszę nie komentować używania komend Intel C / C++ compiler Intrinsic Equivalent...

Jest to kolejne rozwiązanie dla ludzi, którzy kochają rekursję.

Illustrated in the example below.

Ex : If Input is 00101010   ==> Expected output is 01010100

1. Divide the input into 2 halves 
    0010 --- 1010

2. Swap the 2 Halves
    1010     0010

3. Repeat the same for each half.
    10 -- 10 ---  00 -- 10
    10    10      10    00

    1-0 -- 1-0 --- 1-0 -- 0-0
    0 1    0 1     0 1    0 0

Done! Output is 01010100

Oto funkcja rekurencyjna do jej rozwiązania. (Uwaga używałem unsigned int, więc może pracować dla wejść o rozmiarze do 8 bitów(unsigned int).

Funkcja rekurencyjna przyjmuje 2 parametry-wartość, której bity potrzebują do odwrócenia oraz liczba bitów w wartość.

int reverse_bits_recursive(unsigned int num, unsigned int numBits)
{
    unsigned int reversedNum;;
    unsigned int mask = 0;

    mask = (0x1 << (numBits/2)) - 1;

    if (numBits == 1) return num;
    reversedNum = reverse_bits_recursive(num >> numBits/2, numBits/2) |
                   reverse_bits_recursive((num & mask), numBits/2) << numBits/2;
    return reversedNum;
}

int main()
{
    unsigned int reversedNum;
    unsigned int num;

    num = 0x55;
    reversedNum = reverse_bits_recursive(num, 8);
    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);

    num = 0xabcd;
    reversedNum = reverse_bits_recursive(num, 16);
    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);

    num = 0x123456;
    reversedNum = reverse_bits_recursive(num, 24);
    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);

    num = 0x11223344;
    reversedNum = reverse_bits_recursive(num,32);
    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);
}

To jest wyjście:

Bit Reversal Input = 0x55 Output = 0xaa
Bit Reversal Input = 0xabcd Output = 0xb3d5
Bit Reversal Input = 0x123456 Output = 0x651690
Bit Reversal Input = 0x11223344 Output = 0x22cc4488

Odpowiedź Andersa Cedroniusa stanowi świetne rozwiązanie dla osób, które mają procesor x86 z obsługą AVX2. Dla platform x86 bez wsparcia AVX lub innych niż x86, jedna z poniższych implementacji powinna działać dobrze.

Pierwszy kod jest wariantem klasycznej metody partycjonowania binarnego, zakodowanej w celu maksymalizacji wykorzystania idiomu shift-plus-logic przydatnego w różnych procesorach ARM. Ponadto wykorzystuje on-the-fly Mask generation, które mogą być korzystne dla RISC procesory, które w przeciwnym razie wymagają wielu instrukcji do załadowania każdej 32-bitowej wartości maski. Kompilatory dla platform x86 powinny używać stałej propagacji do obliczania wszystkich masek w czasie kompilacji, a nie w czasie uruchamiania.

/* Classic binary partitioning algorithm */
inline uint32_t brev_classic (uint32_t a)
{
    uint32_t m;
    a = (a >> 16) | (a << 16);                            // swap halfwords
    m = 0x00ff00ff; a = ((a >> 8) & m) | ((a << 8) & ~m); // swap bytes
    m = m^(m << 4); a = ((a >> 4) & m) | ((a << 4) & ~m); // swap nibbles
    m = m^(m << 2); a = ((a >> 2) & m) | ((a << 2) & ~m);
    m = m^(m << 1); a = ((a >> 1) & m) | ((a << 1) & ~m);
    return a;
}

/* Knuth's algorithm from http://www.hackersdelight.org/revisions.pdf. Retrieved 8/19/2015 */
inline uint32_t brev_knuth (uint32_t a)
{
    uint32_t t;
    a = (a << 15) | (a >> 17);
    t = (a ^ (a >> 10)) & 0x003f801f; 
    a = (t + (t << 10)) ^ a;
    t = (a ^ (a >>  4)) & 0x0e038421; 
    a = (t + (t <<  4)) ^ a;
    t = (a ^ (a >>  2)) & 0x22488842; 
    a = (t + (t <<  2)) ^ a;
    return a;
}

Cóż, na pewno nie będzie to odpowiedź jak Matt J, ale mam nadzieję, że nadal będzie przydatna.

size_t reverse(size_t n, unsigned int bytes)
{
    __asm__("BSWAP %0" : "=r"(n) : "0"(n));
    n >>= ((sizeof(size_t) - bytes) * 8);
    n = ((n & 0xaaaaaaaaaaaaaaaa) >> 1) | ((n & 0x5555555555555555) << 1);
    n = ((n & 0xcccccccccccccccc) >> 2) | ((n & 0x3333333333333333) << 2);
    n = ((n & 0xf0f0f0f0f0f0f0f0) >> 4) | ((n & 0x0f0f0f0f0f0f0f0f) << 4);
    return n;
}

Jest to dokładnie ten sam pomysł, co najlepszy algorytm Matta, z wyjątkiem tego, że istnieje mała instrukcja zwana BSWAP, która zamienia bajty (nie bity) 64-bitowej liczby. Więc b7, b6, b5, b4, b3,b2,b1,b0 staje się b0,b1,b2,b3,b4,b5,b6, b7. Ponieważ pracujemy z numerem 32-bitowym, musimy przesunąć nasz numer zamieniony na bajty w dół o 32 bity. To tylko pozostawia nam zadanie wymiany 8 bity każdego bajtu, które jest zrobione i voila! skończyliśmy.

Czas: na mojej maszynie algorytm Matta działał w ~0,52 sekundy na próbę. Mój biegł w około 0,42 sekundy na próbę. 20% szybciej nie jest złe, myślę.

Jeśli martwisz się o dostępność instrukcji BSWAP Wikipedia wymienia instrukcję BSWAP jako dodaną z numerem 80846, która ukazała się w 1989 roku. Należy zauważyć, że Wikipedia stwierdza również, że instrukcja ta działa tylko na rejestrach 32-bitowych, które są oczywiście nie w moim komputerze, to bardzo działa tylko na rejestrach 64-bitowych.

Ta metoda będzie działać równie dobrze dla dowolnego typu danych całkowych, więc metoda może być uogólniona trywialnie, przekazując liczbę żądanych bajtów:

    size_t reverse(size_t n, unsigned int bytes)
    {
        __asm__("BSWAP %0" : "=r"(n) : "0"(n));
        n >>= ((sizeof(size_t) - bytes) * 8);
        n = ((n & 0xaaaaaaaaaaaaaaaa) >> 1) | ((n & 0x5555555555555555) << 1);
        n = ((n & 0xcccccccccccccccc) >> 2) | ((n & 0x3333333333333333) << 2);
        n = ((n & 0xf0f0f0f0f0f0f0f0) >> 4) | ((n & 0x0f0f0f0f0f0f0f0f) << 4);
        return n;
    }

Które można następnie nazwać tak:

    n = reverse(n, sizeof(char));//only reverse 8 bits
    n = reverse(n, sizeof(short));//reverse 16 bits
    n = reverse(n, sizeof(int));//reverse 32 bits
    n = reverse(n, sizeof(size_t));//reverse 64 bits

Kompilator powinien być w stanie zoptymalizować dodatkowy parametr (zakładając, że kompilator jest w linii funkcji) i w przypadku sizeof(size_t) przesunięcie w prawo zostanie całkowicie usunięte. Zauważ, że GCC na least nie jest w stanie usunąć bswap i przesunięcia w prawo, jeśli zostało przekazane sizeof(char).

Zakładając, że masz tablicę bitów, co powiesz na to: 1. Zaczynając od MSB, wciskaj bity do stosu jeden po drugim. 2. Pop bitów z tego stosu do innej tablicy (lub tej samej tablicy, jeśli chcesz zaoszczędzić miejsce), umieszczając pierwszy wyskakujący bit do MSB i przechodząc do mniej znaczących bitów stamtąd.

Stack stack = new Stack();
Bit[] bits = new Bit[] { 0, 0, 1, 0, 0, 0, 0, 0 };

for (int i = 0; i < bits.Length; i++) 
{
    stack.push(bits[i]);
}

for (int i = 0; i < bits.Length; i++)
{
    bits[i] = stack.pop();
}

To nie jest praca dla człowieka! ... ale idealny do maszyny

Jest rok 2015, 6 lat od kiedy to pytanie zostało po raz pierwszy zadane. Kompilatory stały się naszymi mistrzami, a naszą pracą jako ludzi jest tylko pomaganie im. Jaki jest najlepszy sposób na przekazanie naszych intencji maszynie?

Odwracanie bitów jest tak powszechne, że trzeba się zastanawiać, dlaczego wciąż rosnąca ISA x86 nie zawiera instrukcji, aby to zrobić jeden raz.

Powód: jeśli dasz swoją prawdziwą zwięzły zamiar kompilatora, odwrócenie bitów powinno zająć tylko ~20 cykli procesora . Pozwól, że pokażę Ci, jak wykonać reverse () i użyć go:

#include <inttypes.h>
#include <stdio.h>

uint64_t reverse(const uint64_t n,
                 const uint64_t k)
{
        uint64_t r, i;
        for (r = 0, i = 0; i < k; ++i)
                r |= ((n >> i) & 1) << (k - i - 1);
        return r;
}

int main()
{
        const uint64_t size = 64;
        uint64_t sum = 0;
        uint64_t a;
        for (a = 0; a < (uint64_t)1 << 30; ++a)
                sum += reverse(a, size);
        printf("%" PRIu64 "\n", sum);
        return 0;
}

Skompilowanie tego przykładowego programu w wersji Clang > = 3.6, - O3, - march=natywny (testowane z Haswellem), daje kod graficzny o jakości przy użyciu nowych instrukcji AVX2, z uruchomieniem 11 sekund przetwarzaniem ~1 miliard odwrotnych () s. to ~10 ns na odwrotną (), z .5 NS CPU cycle zakładając, że 2 GHz stawia nas na sweet 20 CPU cykle.

• możesz zmieścić 10 reverse () s w czasie potrzebnym do uzyskania dostępu do pamięci RAM dla jednej dużej tablicy!
• możesz zmieścić 1 reverse () w czasie potrzebnym do dwukrotnego dostępu do pamięci podręcznej L2 LUT.

Zastrzeżenie: ten przykładowy kod powinien być przyzwoitym benchmarkiem przez kilka lat, ale w końcu zacznie pokazywać swój wiek, gdy Kompilatory będą wystarczająco inteligentne, aby zoptymalizować main (), aby wydrukować końcowy wynik, zamiast naprawdę obliczać cokolwiek. Ale dla teraz działa w funkcji reverse ().

Oczywiście oczywiste źródło bit-twidling hacki jest tutaj: http://graphics.stanford.edu/ ~ seander / bithacks. html # BitReverseObvious

Natywna Instrukcja ARM "rbit" potrafi to zrobić z 1 cyklem cpu i 1 dodatkowym rejestrem cpu, niemożliwym do pokonania.

Wiem, że to nie C tylko asm:

var1 dw 0f0f0
clc
     push ax
     push cx
     mov cx 16
loop1:
     shl var1
     shr ax
loop loop1
     pop ax
     pop cx

To działa z bitem przenoszenia, więc możesz też zapisać flagi

Implementacja z niską pamięcią i najszybsza.

private Byte  BitReverse(Byte bData)
    {
        Byte[] lookup = { 0, 8,  4, 12, 
                          2, 10, 6, 14 , 
                          1, 9,  5, 13,
                          3, 11, 7, 15 };
        Byte ret_val = (Byte)(((lookup[(bData & 0x0F)]) << 4) + lookup[((bData & 0xF0) >> 4)]);
        return ret_val;
    }

Byłem ciekaw, jak szybko będzie to oczywiste raw rotation. Na moim komputerze (i7@2600) średnia dla 1,500,150,000 iteracji wynosiła 27.28 ns (w losowym zestawie 131,071 64-bitowych liczb całkowitych).

Zalety: ilość potrzebnej pamięci jest niewielka, a kod jest prosty. Powiedziałbym, że nie jest też tak duża. Wymagany czas jest przewidywalny i stały dla dowolnego wejścia (128 operacji przesunięcia arytmetycznego + 64 operacje logiczne i operacje + 64 operacje logiczne lub operacje).

Porównałem do najlepszy czas uzyskał @ Matt J-który ma zaakceptowaną odpowiedź. Jeśli dobrze odczytałem jego odpowiedź, najlepsze, co dostał, to 0.631739 sekundy na iteracje, co prowadzi do średniej 631 ns na obrót.

Fragment kodu, którego użyłem, to ten poniżej:

unsigned long long reverse_long(unsigned long long x)
{
    return (((x >> 0) & 1) << 63) |
           (((x >> 1) & 1) << 62) |
           (((x >> 2) & 1) << 61) |
           (((x >> 3) & 1) << 60) |
           (((x >> 4) & 1) << 59) |
           (((x >> 5) & 1) << 58) |
           (((x >> 6) & 1) << 57) |
           (((x >> 7) & 1) << 56) |
           (((x >> 8) & 1) << 55) |
           (((x >> 9) & 1) << 54) |
           (((x >> 10) & 1) << 53) |
           (((x >> 11) & 1) << 52) |
           (((x >> 12) & 1) << 51) |
           (((x >> 13) & 1) << 50) |
           (((x >> 14) & 1) << 49) |
           (((x >> 15) & 1) << 48) |
           (((x >> 16) & 1) << 47) |
           (((x >> 17) & 1) << 46) |
           (((x >> 18) & 1) << 45) |
           (((x >> 19) & 1) << 44) |
           (((x >> 20) & 1) << 43) |
           (((x >> 21) & 1) << 42) |
           (((x >> 22) & 1) << 41) |
           (((x >> 23) & 1) << 40) |
           (((x >> 24) & 1) << 39) |
           (((x >> 25) & 1) << 38) |
           (((x >> 26) & 1) << 37) |
           (((x >> 27) & 1) << 36) |
           (((x >> 28) & 1) << 35) |
           (((x >> 29) & 1) << 34) |
           (((x >> 30) & 1) << 33) |
           (((x >> 31) & 1) << 32) |
           (((x >> 32) & 1) << 31) |
           (((x >> 33) & 1) << 30) |
           (((x >> 34) & 1) << 29) |
           (((x >> 35) & 1) << 28) |
           (((x >> 36) & 1) << 27) |
           (((x >> 37) & 1) << 26) |
           (((x >> 38) & 1) << 25) |
           (((x >> 39) & 1) << 24) |
           (((x >> 40) & 1) << 23) |
           (((x >> 41) & 1) << 22) |
           (((x >> 42) & 1) << 21) |
           (((x >> 43) & 1) << 20) |
           (((x >> 44) & 1) << 19) |
           (((x >> 45) & 1) << 18) |
           (((x >> 46) & 1) << 17) |
           (((x >> 47) & 1) << 16) |
           (((x >> 48) & 1) << 15) |
           (((x >> 49) & 1) << 14) |
           (((x >> 50) & 1) << 13) |
           (((x >> 51) & 1) << 12) |
           (((x >> 52) & 1) << 11) |
           (((x >> 53) & 1) << 10) |
           (((x >> 54) & 1) << 9) |
           (((x >> 55) & 1) << 8) |
           (((x >> 56) & 1) << 7) |
           (((x >> 57) & 1) << 6) |
           (((x >> 58) & 1) << 5) |
           (((x >> 59) & 1) << 4) |
           (((x >> 60) & 1) << 3) |
           (((x >> 61) & 1) << 2) |
           (((x >> 62) & 1) << 1) |
           (((x >> 63) & 1) << 0);
}

W zasadzie jest to to samo co pierwsze " reverse ()", ale jest to 64 bit i wymaga tylko jednej natychmiastowej maski do załadowania ze strumienia instrukcji. GCC tworzy kod bez skoków, więc powinno to być dość szybkie.

#include <stdio.h>

static unsigned long long swap64(unsigned long long val)
{
#define ZZZZ(x,s,m) (((x) >>(s)) & (m)) | (((x) & (m))<<(s));
/* val = (((val) >>16) & 0xFFFF0000FFFF) | (((val) & 0xFFFF0000FFFF)<<16); */

val = ZZZZ(val,32,  0x00000000FFFFFFFFull );
val = ZZZZ(val,16,  0x0000FFFF0000FFFFull );
val = ZZZZ(val,8,   0x00FF00FF00FF00FFull );
val = ZZZZ(val,4,   0x0F0F0F0F0F0F0F0Full );
val = ZZZZ(val,2,   0x3333333333333333ull );
val = ZZZZ(val,1,   0x5555555555555555ull );

return val;
#undef ZZZZ
}

int main(void)
{
unsigned long long val, aaaa[16] =
 { 0xfedcba9876543210,0xedcba9876543210f,0xdcba9876543210fe,0xcba9876543210fed
 , 0xba9876543210fedc,0xa9876543210fedcb,0x9876543210fedcba,0x876543210fedcba9
 , 0x76543210fedcba98,0x6543210fedcba987,0x543210fedcba9876,0x43210fedcba98765
 , 0x3210fedcba987654,0x210fedcba9876543,0x10fedcba98765432,0x0fedcba987654321
 };
unsigned iii;

for (iii=0; iii < 16; iii++) {
    val = swap64 (aaaa[iii]);
    printf("A[]=%016llX Sw=%016llx\n", aaaa[iii], val);
    }
return 0;
}

Możesz użyć standardowej biblioteki szablonów. Może być wolniejszy niż wyżej wymieniony kod. Wydaje mi się jednak jaśniejsze i łatwiejsze do zrozumienia.

 #include<bitset>
 #include<iostream>


 template<size_t N>
 const std::bitset<N> reverse(const std::bitset<N>& ordered)
 {
      std::bitset<N> reversed;
      for(size_t i = 0, j = N - 1; i < N; ++i, --j)
           reversed[j] = ordered[i];
      return reversed;
 };


 // test the function
 int main()
 {
      unsigned long num; 
      const size_t N = sizeof(num)*8;

      std::cin >> num;
      std::cout << std::showbase << std::hex;
      std::cout << "ordered  = " << num << std::endl;
      std::cout << "reversed = " << reverse<N>(num).to_ulong()  << std::endl;
      std::cout << "double_reversed = " << reverse<N>(reverse<N>(num)).to_ulong() << std::endl;  
 }

Generic

Kod C. Użycie 1-bajtowej liczby danych wejściowych jako przykładu.

    unsigned char num = 0xaa;   // 1010 1010 (aa) -> 0101 0101 (55)
    int s = sizeof(num) * 8;    // get number of bits
    int i, x, y, p;
    int var = 0;                // make var data type to be equal or larger than num

    for (i = 0; i < (s / 2); i++) {
        // extract bit on the left, from MSB
        p = s - i - 1;
        x = num & (1 << p);
        x = x >> p;
        printf("x: %d\n", x);

        // extract bit on the right, from LSB
        y = num & (1 << i);
        y = y >> i;
        printf("y: %d\n", y);

        var = var | (x << i);       // apply x
        var = var | (y << p);       // apply y
    }

    printf("new: 0x%x\n", new);

A może:

    uint reverseMSBToLSB32ui(uint input)
    {
        uint output = 0x00000000;
        uint toANDVar = 0;
        int places = 0;

        for (int i = 1; i < 32; i++)
        {
            places = (32 - i);
            toANDVar = (uint)(1 << places);
            output |= (uint)(input & (toANDVar)) >> places;

        }


        return output;
    }

Myślałem, że to jeden z najprostszych sposobów na odwrócenie bitu. proszę dać mi znać, jeśli jest jakaś wada w tej logice. zasadniczo w tej logice sprawdzamy wartość bitu w pozycji. Ustaw bit, jeśli wartość jest 1 na odwróconej pozycji.

void bit_reverse(ui32 *data)
{
  ui32 temp = 0;    
  ui32 i, bit_len;    
  {    
   for(i = 0, bit_len = 31; i <= bit_len; i++)   
   {    
    temp |= (*data & 1 << i)? (1 << bit_len-i) : 0;    
   }    
   *data = temp;    
  }    
  return;    
}    

unsigned char ReverseBits(unsigned char data)
{
    unsigned char k = 0, rev = 0;

    unsigned char n = data;

    while(n)

    {
        k = n & (~(n - 1));
        n &= (n - 1);
        rev |= (128 / k);
    }
    return rev;
}

Myślę, że najprostsza metoda, którą znam, jest następująca. MSB jest wejściem, a LSB jest wyjściem "odwróconym":

unsigned char rev(char MSB) {
    unsigned char LSB=0;  // for output
    _FOR(i,0,8) {
        LSB= LSB << 1;
        if(MSB&1) LSB = LSB | 1;
        MSB= MSB >> 1;
    }
    return LSB;
}

//    It works by rotating bytes in opposite directions. 
//    Just repeat for each byte.

// Purpose: to reverse bits in an unsigned short integer 
// Input: an unsigned short integer whose bits are to be reversed
// Output: an unsigned short integer with the reversed bits of the input one
unsigned short ReverseBits( unsigned short a )
{
     // declare and initialize number of bits in the unsigned short integer
     const char num_bits = sizeof(a) * CHAR_BIT;

     // declare and initialize bitset representation of integer a
     bitset<num_bits> bitset_a(a);          

     // declare and initialize bitset representation of integer b (0000000000000000)
     bitset<num_bits> bitset_b(0);                  

     // declare and initialize bitset representation of mask (0000000000000001)
     bitset<num_bits> mask(1);          

     for ( char i = 0; i < num_bits; ++i )
     {
          bitset_b = (bitset_b << 1) | bitset_a & mask;
          bitset_a >>= 1;
     }

     return (unsigned short) bitset_b.to_ulong();
}

void PrintBits( unsigned short a )
{
     // declare and initialize bitset representation of a
     bitset<sizeof(a) * CHAR_BIT> bitset(a);

     // print out bits
     cout << bitset << endl;
}


// Testing the functionality of the code

int main ()
{
     unsigned short a = 17, b;

     cout << "Original: "; 
     PrintBits(a);

     b = ReverseBits( a );

     cout << "Reversed: ";
     PrintBits(b);
}

// Output:
Original: 0000000000010001
Reversed: 1000100000000000

Inne rozwiązanie oparte na pętli, które szybko wychodzi, gdy liczba jest niska (w C++ dla wielu typów)

template<class T>
T reverse_bits(T in) {
    T bit = static_cast<T>(1) << (sizeof(T) * 8 - 1);
    T out;

    for (out = 0; bit && in; bit >>= 1, in >>= 1) {
        if (in & 1) {
            out |= bit;
        }
    }
    return out;
}

Lub w C dla niepodpisanej liczby całkowitej

unsigned int reverse_bits(unsigned int in) {
    unsigned int bit = 1u << (sizeof(T) * 8 - 1);
    unsigned int out;

    for (out = 0; bit && in; bit >>= 1, in >>= 1) {
        if (in & 1)
            out |= bit;
    }
    return out;
}

Wydaje się, że wiele innych postów dotyczy prędkości (tj. najlepszy = najszybszy). A co z prostotą? Consider:

char ReverseBits(char character) {
    char reversed_character = 0;
    for (int i = 0; i < 8; i++) {
        char ith_bit = (c >> i) & 1;
        reversed_character |= (ith_bit << (sizeof(char) - 1 - i));
    }
    return reversed_character;
}

I mam nadzieję, że sprytny kompilator zoptymalizuje dla Ciebie.

Jeśli chcesz odwrócić dłuższą listę bitów (zawierającą sizeof(char) * n bity), możesz użyć tej funkcji, aby uzyskać:

void ReverseNumber(char* number, int bit_count_in_number) {
    int bytes_occupied = bit_count_in_number / sizeof(char);      

    // first reverse bytes
    for (int i = 0; i <= (bytes_occupied / 2); i++) {
        swap(long_number[i], long_number[n - i]);
    }

    // then reverse bits of each individual byte
    for (int i = 0; i < bytes_occupied; i++) {
         long_number[i] = ReverseBits(long_number[i]);
    }
}

Spowoduje to odwrócenie [10000000, 10101010] do [01010101, 00000001].

Odwrócenie bitów w pseudo kodzie

Źródło - > bajt do odwrócenia b00101100 destination - > reversed, również musi być typu unsigned, więc bit znaku nie jest propogowany w dół

Kopiuj do temp, więc oryginał nie ma wpływu, również musi być typu unsigned, aby bit znaku nie był przesuwany automatycznie

bytecopy = b0010110

LOOP8: / / zrób to 8 razy test, czy bytecopy jest

    set bit8 (msb) of reversed = reversed | b10000000 

else do not set bit8

shift bytecopy left 1 place
bytecopy = bytecopy << 1 = b0101100 result

shift result right 1 place
reversed = reversed >> 1 = b00000000
8 times no then up^ LOOP8
8 times yes then done.

Moje proste rozwiązanie

BitReverse(IN)
    OUT = 0x00;
    R = 1;      // Right mask   ...0000.0001
    L = 0;      // Left mask    1000.0000...
    L = ~0; 
    L = ~(i >> 1);
    int size = sizeof(IN) * 4;  // bit size

    while(size--){
        if(IN & L) OUT = OUT | R; // start from MSB  1000.xxxx
        if(IN & R) OUT = OUT | L; // start from LSB  xxxx.0001
        L = L >> 1;
        R = R << 1; 
    }
    return OUT;

To jest dla 32 bitów, musimy zmienić rozmiar jeśli weźmiemy pod uwagę 8 bitów.

    void bitReverse(int num)
    {
        int num_reverse = 0;
        int size = (sizeof(int)*8) -1;
        int i=0,j=0;
        for(i=0,j=size;i<=size,j>=0;i++,j--)
        {
            if((num >> i)&1)
            {
                num_reverse = (num_reverse | (1<<j));
            }
        }
        printf("\n rev num = %d\n",num_reverse);
    }

Odczyt wejściowej liczby całkowitej " num " w porządku LSB->MSB i zapis w num_reverse w porządku MSB - > LSB.

int bit_reverse(int w, int bits)
{
    int r = 0;
    for (int i = 0; i < bits; i++)
    {
        int bit = (w & (1 << i)) >> i;
        r |= bit << (bits - i - 1);
    }
    return r;
}