Jaki jest najprostszy sposób odwrócenia kolejności bitów w bajcie w C / C ++?


110

Chociaż istnieje wiele sposobów odwrócenia kolejności bitów w bajcie, jestem ciekawy, który z nich jest „najprostszy” do zaimplementowania przez programistę. I odwracając mam na myśli:

1110 -> 0111
0010 -> 0100

To jest podobne do tego pytania PHP , ale nie jest jego duplikatem .

To jest podobne do tego pytania , ale nie jest jego duplikatem . To pytanie dotyczy najłatwiejszej metody do wdrożenia przez programistę. „Najlepszy algorytm” dotyczy pamięci i wydajności procesora.


Użyj montażu inline. Lepiej, umieść tę funkcję w oddzielnej jednostce tłumaczeniowej. Miej jeden moduł języka asemblera dla każdej platformy docelowej. Pozwól procesowi kompilacji wybrać moduły.
Thomas Matthews

@Andreas Najprostsze wdrożenie
nathan

Odpowiedzi:


102

Jeśli mówisz o pojedynczym bajcie, prawdopodobnie najlepszym rozwiązaniem jest przeszukiwanie tabeli, chyba że z jakiegoś powodu nie masz dostępnych 256 bajtów.


12
Jeśli mówimy o czymś, co jest łatwe do zaimplementowania bez kopiowania gotowego rozwiązania, utworzenie tabeli przeglądowej nadal wymaga innego rozwiązania. (Oczywiście można to zrobić ręcznie, ale jest to podatne na błędy i czasochłonne…)
Arkku

7
Możesz ścisnąć tablicę do nieco mniej niż 256 bajtów, jeśli zignorujesz palindromy.
wilhelmtell

8
@wilhelmtell - potrzebowałbyś tabeli, aby wiedzieć, które z nich są palindromami.
Mark Ransom

6
@wilhelmtell: Cóż, aby napisać skrypt, nadal potrzebne jest inne rozwiązanie, o co mi chodziło - tablica przeglądowa jest prosta w użyciu, ale nie jest łatwa do utworzenia. (Z wyjątkiem kopiowania gotowej tabeli przeglądowej, ale wtedy równie dobrze można by skopiować dowolne rozwiązanie.) Na przykład, jeśli uważane jest za „najprostsze” rozwiązanie, które można zapisać na papierze podczas egzaminu lub rozmowy kwalifikacyjnej, nie zrobiłbym tego zacznij ręcznie tworzyć tablicę przeglądową, a program, który to zrobi, będzie zawierał już inne rozwiązanie (które byłoby prostsze samo w sobie niż to zawierające zarówno to, jak i tabelę).
Arkku

4
@Arkku Miałem na myśli napisanie skryptu, który wypisuje tablicę pierwszych 256 bajtów i ich odwrotne odwzorowanie. Tak, wróciłeś do pisania funkcji odwrotnej, ale teraz w swoim ulubionym języku skryptowym i może być tak paskudny, jak chcesz - wyrzucisz go, gdy tylko zostanie ukończony, i uruchomiłeś go raz. Posiada wyjście do skryptu jako kod C, jeszcze: unsigned int rtable[] = {0x800, 0x4000, ...};. Następnie wyrzuć scenariusz i zapomnij, że go kiedykolwiek miałeś. Pisanie jest znacznie szybsze niż odpowiadający mu kod w C ++ i będzie działał tylko raz, więc otrzymujesz środowisko uruchomieniowe O (1) w kodzie C ++.
wilhelmtell

227

To powinno działać:

unsigned char reverse(unsigned char b) {
   b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
   b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
   b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
   return b;
}

Najpierw lewe cztery bity są zamieniane na prawe cztery bity. Następnie zamieniane są wszystkie sąsiednie pary, a następnie wszystkie sąsiednie pojedyncze bity. Powoduje to odwróconą kolejność.


26
Raczej krótkie i szybkie, ale nie proste.
Mark Okup

3
To podejście również wyraźnie uogólnia wykonywanie zamiany bajtów dla endianness.
Boojum

2
Nie jest to najprostsze podejście, ale podoba mi się +1.
nathan

7
Tak, to proste. To rodzaj algorytmu dziel i rządź. Doskonały!
kiewic

Czy jest szybszy niż metoda sugerowana przez @Arkku poniżej?
2013

123

Myślę, że tablica przeglądowa musi być jedną z najprostszych metod. Nie potrzebujesz jednak pełnej tabeli odnośników.

//Index 1==0b0001 => 0b1000
//Index 7==0b0111 => 0b1110
//etc
static unsigned char lookup[16] = {
0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,
0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf, };

uint8_t reverse(uint8_t n) {
   // Reverse the top and bottom nibble then swap them.
   return (lookup[n&0b1111] << 4) | lookup[n>>4];
}

// Detailed breakdown of the math
//  + lookup reverse of bottom nibble
//  |       + grab bottom nibble
//  |       |        + move bottom result into top nibble
//  |       |        |     + combine the bottom and top results 
//  |       |        |     | + lookup reverse of top nibble
//  |       |        |     | |       + grab top nibble
//  V       V        V     V V       V
// (lookup[n&0b1111] << 4) | lookup[n>>4]

To dość proste do zakodowania i weryfikacji wizualnej.
Ostatecznie może to być nawet szybsze niż pełny stół. Bitowa arytmia jest tania, a tabela łatwo mieści się w wierszu pamięci podręcznej.


10
To doskonały sposób na zmniejszenie złożoności rozwiązania tabeli. +1
e.James

3
Fajnie, ale da ci brak pamięci podręcznej.
Johan Kotlinski

7
@kotlinski: co spowoduje brak pamięci podręcznej? Myślę, że wersja z małą tabelą może być bardziej wydajna w pamięci podręcznej niż duża. W moim Core2 linia pamięci podręcznej ma szerokość 64 bajtów, pełna tabela obejmowałaby wiele linii, podczas gdy mniejsza tabela z łatwością mieści jedną linię.
deft_code

4
@kotlinski: Lokalność czasowa jest ważniejsza w przypadku trafień w pamięci podręcznej lub strategii zastępowania niż lokalizacja adresu
por.

6
@Harshdeep: Weź pod uwagę binarnie zakodowane indeksy wpisów tabeli. indeks b0000 (0) -> b0000 (0x0) nudne; b0001(1) -> b1000(0x8), b0010(2) -> b0100(0x4), b1010(10) -> b0101(0x5). Widzisz wzór? Jest to na tyle proste, że możesz to obliczyć w głowie (jeśli potrafisz czytać binarnie, w przeciwnym razie będziesz potrzebować papieru, aby to obliczyć). Jeśli chodzi o skok, to odwrócenie 8-bitowej liczby całkowitej jest tym samym, co odwrócenie 4-bitowych części, a następnie ich zamiana; Mam doświadczenie i intuicję (lub magię).
deft_code,

46

Zobacz trochę dziwacznych hacków dla wielu rozwiązań. Tworzenie kopii z tego miejsca jest oczywiście łatwe do zaimplementowania. =)

Na przykład (na 32-bitowym procesorze):

uint8_t b = byte_to_reverse;
b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;

Jeśli przez „łatwe do wdrożenia” oznacza się coś, co można zrobić bez referencji na egzaminie lub rozmowie kwalifikacyjnej, to najbezpieczniejszym rozwiązaniem jest prawdopodobnie nieefektywne kopiowanie bitów jeden po drugim do innej zmiennej w odwrotnej kolejności (już pokazane w innych odpowiedziach ).


1
Z Twojego adresu URL: 32-bitowy procesor: b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;
Joshua

1
@Joshua: To także mój ulubiony. Zastrzeżenie (jak stwierdzono na połączonej stronie) polega na tym, że musi zostać przypisane lub wrzucone do uint8_t lub w górnych bitach będzie śmieci.
Arkku

42

Ponieważ nikt nie opublikował pełnego rozwiązania do wyszukiwania tabel, oto moje:

unsigned char reverse_byte(unsigned char x)
{
    static const unsigned char table[] = {
        0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
        0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
        0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
        0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
        0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
        0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
        0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
        0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
        0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
        0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
        0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
        0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
        0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
        0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
        0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
        0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
        0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
        0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
        0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
        0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
        0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
        0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
        0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
        0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
        0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
        0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
        0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
        0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
        0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
        0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
        0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
        0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
    };
    return table[x];
}

2
Przydatne, dzięki. Wygląda na to, że moja metoda wolniejszej zmiany biegów ograniczała wydajność w aplikacji osadzonej. Umieszczono tabelę w pamięci ROM na PIC (z dodatkiem słowa kluczowego rom).
zakończenie


25
template <typename T>
T reverse(T n, size_t b = sizeof(T) * CHAR_BIT)
{
    assert(b <= std::numeric_limits<T>::digits);

    T rv = 0;

    for (size_t i = 0; i < b; ++i, n >>= 1) {
        rv = (rv << 1) | (n & 0x01);
    }

    return rv;
}

EDYTOWAĆ:

Przekonwertowano go na szablon z opcjonalną liczbą bitcount


@nvl - naprawiono. Zacząłem budować go jako szablon, ale w połowie postanowiłem tego nie robić ... za dużo & gt & lt
i

Dla dodatkowego pedenatry wymienić sizeof(T)*8z sizeof(T)*CHAR_BITS.
Pillsy,

6
@andand Aby uzyskać dodatkową ozdobę, wymień sizeof(T)*CHAR_BITna std::numeric_limits<T>::digits(prawie 4 lata pedanterii później).
Morwenn,

1
Tak powinno być CHAR_BIT, nie CHAR_BITS.
Xunie,

1
powinno być rv = (rv << 1) | (n & 0x01);
Vignesh

16

Dwie linie:

for(i=0;i<8;i++)
     reversed |= ((original>>i) & 0b1)<<(7-i);

lub w przypadku problemów z częścią „0b1”:

for(i=0;i<8;i++)
     reversed |= ((original>>i) & 1)<<(7-i);

„oryginalny” to bajt, który chcesz cofnąć. „odwrócony” to wynik zainicjowany na 0.


14

Chociaż prawdopodobnie nie przenośny, użyłbym języka asemblera.
Wiele języków asemblera ma instrukcje, aby obrócić nieco flagę przeniesienia i obrócić flagę przeniesienia do słowa (lub bajtu).

Algorytm to:

for each bit in the data type:
  rotate bit into carry flag
  rotate carry flag into destination.
end-for

Kod języka wysokiego poziomu jest znacznie bardziej skomplikowany, ponieważ C i C ++ nie obsługują rotacji do przenoszenia i rotacji do przenoszenia. Flaga nośna musi być wymodelowana.

Edycja: na przykład język asemblera

;  Enter with value to reverse in R0.
;  Assume 8 bits per byte and byte is the native processor type.
   LODI, R2  8       ; Set up the bit counter
Loop:
   RRC, R0           ; Rotate R0 right into the carry bit.
   RLC, R1           ; Rotate R1 left, then append carry bit.
   DJNZ, R2  Loop    ; Decrement R2 and jump if non-zero to "loop"
   LODR, R0  R1      ; Move result into R0.

7
Myślę, że ta odpowiedź jest przeciwieństwem prostej. Nieprzenośny, asemblerowy i wystarczająco złożony, aby można go było napisać w pseudokodzie zamiast w rzeczywistym zestawie.
deft_code

3
To całkiem proste. Umieściłem to w pseudokodzie, ponieważ mnemoniki asemblera są specyficzne dla rasy procesorów i istnieje wiele ras. Jeśli chcesz, mogę to edytować, aby pokazać prosty język asemblera.
Thomas Matthews,

Można by zobaczyć, czy optymalizacja kompilatora upraszcza się do odpowiedniej instrukcji asemblera.
Sparky

12

Uważam, że poniższe rozwiązanie jest prostsze niż inne bitowe algorytmy, które tu widziałem.

unsigned char reverse_byte(char a)
{

  return ((a & 0x1)  << 7) | ((a & 0x2)  << 5) |
         ((a & 0x4)  << 3) | ((a & 0x8)  << 1) |
         ((a & 0x10) >> 1) | ((a & 0x20) >> 3) |
         ((a & 0x40) >> 5) | ((a & 0x80) >> 7);
}

Pobiera każdy bit w bajcie i odpowiednio go przesuwa, zaczynając od pierwszego do ostatniego.

Wyjaśnienie:

   ((a & 0x1) << 7) //get first bit on the right and shift it into the first left position 
 | ((a & 0x2) << 5) //add it to the second bit and shift it into the second left position
  //and so on

Piękny! Jak dotąd mój ulubiony.
Nick Rameau

Jest to z pewnością proste, ale należy podkreślić, że czas wykonania wynosi raczej O (n) niż O (log₂ n), gdzie n to liczba bitów (8, 16, 32, 64 itd.).
Todd Lehman

10

Plik Najprostszym sposobem jest prawdopodobnie iteracyjne nad pozycjach bitowych w pętli:

unsigned char reverse(unsigned char c) {
   int shift;
   unsigned char result = 0;
   for (shift = 0; shift < CHAR_BIT; shift++) {
      if (c & (0x01 << shift))
         result |= (0x80 >> shift);
   }
   return result;
}

to jest CHAR_BIT, bez „s”
ljrk

CHAR_BITPo co używać, skoro zakładasz, że charmasz 8 bitów?
chqrlie

6

Możesz być zainteresowany std::vector<bool>(to jest bitowy) istd::bitset

Powinien być najprostszy zgodnie z żądaniem.

#include <iostream>
#include <bitset>
using namespace std;
int main() {
  bitset<8> bs = 5;
  bitset<8> rev;
  for(int ii=0; ii!= bs.size(); ++ii)
    rev[bs.size()-ii-1] = bs[ii];
  cerr << bs << " " << rev << endl;
}

Inne opcje mogą być szybsze.

EDYCJA: Jestem ci winien rozwiązanie wykorzystujące std::vector<bool>

#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>
using namespace std;
int main() {
  vector<bool> b{0,0,0,0,0,1,0,1};
  reverse(b.begin(), b.end());
  copy(b.begin(), b.end(), ostream_iterator<int>(cerr));
  cerr << endl;
}

Drugi przykład wymaga rozszerzenia c ++ 0x (aby zainicjować tablicę {...}). Zaleta używania a bitsetlub a std::vector<bool>(lub aboost::dynamic_bitset ) jest to, że nie jesteś ograniczony do bajtów lub słów, ale możesz odwrócić dowolną liczbę bitów.

HTH


Dlaczego bitset jest prostszy niż kapsuła? Pokaż kod albo nie jest.
wilhelmtell

Właściwie myślę, że kod odwróci zestaw bitów, a następnie odwróci go z powrotem do pierwotnego. Zmień ii! = Size (); do ii <size () / 2; i zrobi to lepiej =)
Viktor Sehr

(@ viktor-sehr nie, nie będzie, rev różni się od bs). Zresztą sama nie podoba mi się odpowiedź: myślę, że jest to przypadek, w którym arytmetyka binarna i operatory przesunięcia są lepiej dopasowane. Nadal najłatwiej jest to zrozumieć.
baol

A co powiesz na std::vector<bool> b = { ... }; std::vector<bool> rb ( b.rbegin(), b.rend()); - bezpośrednie użycie odwrotnych iteratorów?
MSalters

@MSalters Podoba mi się niezmienność tego.
baol

6

W bardzo ograniczonym przypadku stałego 8-bitowego wejścia ta metoda nie kosztuje pamięci ani procesora w czasie wykonywania:

#define MSB2LSB(b) (((b)&1?128:0)|((b)&2?64:0)|((b)&4?32:0)|((b)&8?16:0)|((b)&16?8:0)|((b)&32?4:0)|((b)&64?2:0)|((b)&128?1:0))

Użyłem tego dla ARINC-429, gdzie kolejność bitów (endianness) etykiety jest przeciwna do reszty słowa. Etykieta jest często stała i zwykle jest ósemkowa.

Oto jak użyłem go do zdefiniowania stałej, ponieważ specyfikacja definiuje tę etykietę jako big-endian 205 ósemkową.

#define LABEL_HF_COMM MSB2LSB(0205)

Więcej przykładów:

assert(0b00000000 == MSB2LSB(0b00000000));
assert(0b10000000 == MSB2LSB(0b00000001));
assert(0b11000000 == MSB2LSB(0b00000011));
assert(0b11100000 == MSB2LSB(0b00000111));
assert(0b11110000 == MSB2LSB(0b00001111));
assert(0b11111000 == MSB2LSB(0b00011111));
assert(0b11111100 == MSB2LSB(0b00111111));
assert(0b11111110 == MSB2LSB(0b01111111));
assert(0b11111111 == MSB2LSB(0b11111111));
assert(0b10101010 == MSB2LSB(0b01010101));

5

Istnieje wiele sposobów odwracania bitów, w zależności od tego, co masz na myśli w „najprostszy sposób”.


Odwróć przez rotację

Chyba najbardziej logiczne jest obrócenie bajtu z nałożeniem maski na pierwszy bit (n & 1):

unsigned char reverse_bits(unsigned char b)
{
    unsigned char   r = 0;
    unsigned        byte_len = 8;

    while (byte_len--) {
        r = (r << 1) | (b & 1);
        b >>= 1;
    }
    return r;
}

1) Ponieważ długość znaku unsigner wynosi 1 bajt, co jest równe 8 bitom, oznacza to, że przeskanujemy każdy bit while (byte_len--)

2) Najpierw sprawdzamy, czy b jest trochę na skrajnej prawej stronie (b & 1); jeśli tak, ustawiamy bit 1 na r z |i przesuwamy go o 1 bit w lewo, mnożąc r przez 2 przez(r << 1)

3) Następnie dzielimy znak b bez znaku b przez 2, b >>=1aby usunąć bit znajdujący się po prawej stronie zmiennej b. Przypominamy, że b >> = 1; jest równoważne b / = 2;


Odwróć w jednej linii

To rozwiązanie jest przypisywane Richowi Schroeppelowi w sekcji Programming Hacks

unsigned char reverse_bits3(unsigned char b)
{
    return (b * 0x0202020202ULL & 0x010884422010ULL) % 0x3ff;
}

1) Operacja mnożenia (b * 0x0202020202ULL) tworzy pięć oddzielnych kopii 8-bitowego wzorca bajtowego do rozłożenia na 64-bitową wartość.

2) Operacja AND (& 0x010884422010ULL) wybiera bity, które znajdują się we właściwych (odwróconych) pozycjach względem każdej 10-bitowej grupy bitów.

3) Razem operacje mnożenia i AND kopiują bity z oryginalnego bajtu, więc każdy z nich pojawia się tylko w jednym z 10-bitowych zestawów. Odwrócone pozycje bitów z oryginalnego bajtu pokrywają się z ich względnymi pozycjami w ramach dowolnego zestawu 10-bitowego.

4) Ostatni krok (% 0x3ff), który polega na dzieleniu modułu przez 2 ^ 10 - 1, skutkuje scaleniem każdego zestawu 10 bitów (z pozycji 0-9, 10-19, 20-29, ...) w wartości 64-bitowej. Nie nakładają się, więc kroki dodawania leżące u podstaw dzielenia modułu zachowują się jak operacje OR.


Dziel i zwyciężaj

unsigned char reverse(unsigned char b) {
   b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
   b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
   b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
   return b;
}

To jest najbardziej pozytywna odpowiedź i pomimo pewnych wyjaśnień myślę, że dla większości ludzi trudno jest sobie wyobrazić, co naprawdę oznacza 0xF0, 0xCC, 0xAA, 0x0F, 0x33 i 0x55.

Nie korzysta z '0b', które jest rozszerzeniem GCC i jest dołączone od standardu C ++ 14, wydanego w grudniu 2014, a więc chwilę po tej odpowiedzi z kwietnia 2010

Stałe całkowite można zapisać jako stałe binarne, składające się z sekwencji cyfr „0” i „1”, poprzedzonych prefiksem „0b” lub „0B”. Jest to szczególnie przydatne w środowiskach, które często działają na poziomie bitowym (np. Mikrokontrolery).

Sprawdź poniższe fragmenty kodu, aby zapamiętać i lepiej zrozumieć to rozwiązanie, w którym poruszamy się o połowę:

unsigned char reverse(unsigned char b) {
   b = (b & 0b11110000) >> 4 | (b & 0b00001111) << 4;
   b = (b & 0b11001100) >> 2 | (b & 0b00110011) << 2;
   b = (b & 0b10101010) >> 1 | (b & 0b01010101) << 1;
   return b;
}

NB: Dzieje się >> 4tak, ponieważ w 1 bajcie jest 8 bitów, co jest znakiem bez znaku, więc chcemy wziąć drugą połowę i tak dalej.

Moglibyśmy łatwo zastosować to rozwiązanie do 4 bajtów z tylko dwoma dodatkowymi wierszami i zgodnie z tą samą logiką. Ponieważ obie maski się uzupełniają, możemy nawet użyć ~, aby zmienić bity i zaoszczędzić trochę atramentu:

uint32_t reverse_integer_bits(uint32_t b) {
   uint32_t mask = 0b11111111111111110000000000000000;
   b = (b & mask) >> 16 | (b & ~mask) << 16;
   mask = 0b11111111000000001111111100000000;
   b = (b & mask) >> 8 | (b & ~mask) << 8;
   mask = 0b11110000111100001111000011110000;
   b = (b & mask) >> 4 | (b & ~mask) << 4;
   mask = 0b11001100110011001100110011001100;
   b = (b & mask) >> 2 | (b & ~mask) << 2;
   mask = 0b10101010101010101010101010101010;
   b = (b & mask) >> 1 | (b & ~mask) << 1;
   return b;
}

[Tylko C ++] Odwróć wszystkie niepodpisane (szablon)

Powyższą logikę można podsumować pętlą, która działałaby na dowolnym typie bez znaku:

template <class T>
T reverse_bits(T n) {
    short bits = sizeof(n) * 8; 
    T mask = ~T(0); // equivalent to uint32_t mask = 0b11111111111111111111111111111111;

    while (bits >>= 1) {
        mask ^= mask << (bits); // will convert mask to 0b00000000000000001111111111111111;
        n = (n & ~mask) >> bits | (n & mask) << bits; // divide and conquer
    }

    return n;
}

Spróbuj sam z włączeniem powyższej funkcji:

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

template <class T>
void print_binary(T n)
{   T mask = 1ULL << ((sizeof(n) * 8) - 1);  // will set the most significant bit
    for(; mask != 0; mask >>= 1) putchar('0' | !!(n & mask));
    putchar('\n');
}

int main() {
    uint32_t n = 12;
    print_binary(n);
    n = reverse_bits(n); 
    print_binary(n);
    unsigned char c = 'a';
    print_binary(c);
    c = reverse_bits(c);
    print_binary(c);
    uint16_t s = 12;
    print_binary(s);
    s = reverse_bits(s);
    print_binary(s);
    uint64_t l = 12;
    print_binary(l);
    l = reverse_bits(l);
    print_binary(l);
    return 0;
}

Odwróć z asm volatile

Wreszcie, jeśli najprostszy oznacza mniej linii, dlaczego nie spróbować montażu na linii?

Możesz przetestować poniższy fragment kodu, dodając -masm=intelpodczas kompilacji:

unsigned char reverse_bits(unsigned char c) {
    __asm__ __volatile__ (R"(
        mov cx, 8       
    daloop:                   
        ror di          
        adc ax, ax      
        dec cx          
        jnz short daloop  
    ;)");
}

Objaśnienia wiersz po wierszu:

        mov cx, 8       ; we will reverse the 8 bits contained in one byte
    daloop:             ; while loop
        shr di          ; Shift Register `di` (containing value of the first argument of callee function) to the Right
        rcl ax          ; Rotate Carry Left: rotate ax left and add the carry from shr di, the carry is equal to 1 if one bit was "lost" from previous operation 
        dec cl          ; Decrement cx
        jnz short daloop; Jump if cx register is Not equal to Zero, else end loop and return value contained in ax register

3

Wyszukiwanie w tabeli lub

uint8_t rev_byte(uint8_t x) {
    uint8_t y;
    uint8_t m = 1;
    while (m) {
       y >>= 1;
       if (m&x) {
          y |= 0x80;
       }
       m <<=1;
    }
    return y;
}

edytować

Spójrz tutaj dla innych rozwiązań, które mogłyby działać lepiej dla Ciebie


3

wolniejsza, ale prostsza implementacja:

static int swap_bit(unsigned char unit)
{
    /*
     * swap bit[7] and bit[0]
     */
    unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01)) << 7) | (unit & 0x7f));
    unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01))) | (unit & 0xfe));
    unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01)) << 7) | (unit & 0x7f));

    /*
     * swap bit[6] and bit[1]
     */
    unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02)) << 5) | (unit & 0xbf));
    unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02))) | (unit & 0xfd));
    unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02)) << 5) | (unit & 0xbf));

    /*
     * swap bit[5] and bit[2]
     */
    unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04)) << 3) | (unit & 0xdf));
    unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04))) | (unit & 0xfb));
    unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04)) << 3) | (unit & 0xdf));

    /*
     * swap bit[4] and bit[3]
     */
    unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08)) << 1) | (unit & 0xef));
    unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08))) | (unit & 0xf7));
    unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08)) << 1) | (unit & 0xef));

    return unit;
}

3

Czy to może być szybkie rozwiązanie?

int byte_to_be_reversed = 
    ((byte_to_be_reversed>>7)&0x01)|((byte_to_be_reversed>>5)&0x02)|      
    ((byte_to_be_reversed>>3)&0x04)|((byte_to_be_reversed>>1)&0x08)| 
    ((byte_to_be_reversed<<7)&0x80)|((byte_to_be_reversed<<5)&0x40)|
    ((byte_to_be_reversed<<3)&0x20)|((byte_to_be_reversed<<1)&0x10);

Eliminuje konieczność korzystania z pętli for! ale eksperci proszę mi powiedzieć, czy to jest wydajne i szybsze?


Czas wykonania wynosi O (n), a nie O (log₂ n), gdzie n to liczba bitów (8, 16, 32, 64 itd.). Zobacz gdzie indziej odpowiedzi, które są wykonywane w czasie O (log₂ n).
Todd Lehman

2

Przed wdrożeniem jakiegokolwiek rozwiązania algorytmicznego sprawdź język asemblera dla dowolnej architektury procesora, którego używasz. Twoja architektura może zawierać instrukcje obsługujące takie manipulacje bitowe (a co może być prostsze niż pojedyncza instrukcja asemblera?).

Jeśli taka instrukcja nie jest dostępna, sugerowałbym skorzystanie z trasy tabeli przeglądowej. Możesz napisać skrypt / program, który wygeneruje tabelę dla Ciebie, a operacje wyszukiwania będą szybsze niż którykolwiek z algorytmów odwracania bitów tutaj (kosztem konieczności przechowywania gdzieś tabeli przeglądowej).


2

Ta prosta funkcja używa maski do testowania każdego bitu w bajcie wejściowym i przenoszenia go na przesuwające się wyjście:

char Reverse_Bits(char input)
{    
    char output = 0;

    for (unsigned char mask = 1; mask > 0; mask <<= 1)
    {
        output <<= 1;

        if (input & mask)
            output |= 1;
    }

    return output;
}

Przepraszam, maska ​​powinna być niepodpisana.
luci88filter

1

Ta jedna jest oparta na jednym BobStein-VisiBone przewidzianym

#define reverse_1byte(b)    ( ((uint8_t)b & 0b00000001) ? 0b10000000 : 0 ) | \
                            ( ((uint8_t)b & 0b00000010) ? 0b01000000 : 0 ) | \
                            ( ((uint8_t)b & 0b00000100) ? 0b00100000 : 0 ) | \
                            ( ((uint8_t)b & 0b00001000) ? 0b00010000 : 0 ) | \
                            ( ((uint8_t)b & 0b00010000) ? 0b00001000 : 0 ) | \
                            ( ((uint8_t)b & 0b00100000) ? 0b00000100 : 0 ) | \
                            ( ((uint8_t)b & 0b01000000) ? 0b00000010 : 0 ) | \
                            ( ((uint8_t)b & 0b10000000) ? 0b00000001 : 0 ) 

Bardzo mi się to podoba, ponieważ kompilator automatycznie obsługuje pracę za Ciebie, więc nie wymaga żadnych dodatkowych zasobów.

można to również rozszerzyć do 16-bitów ...

#define reverse_2byte(b)    ( ((uint16_t)b & 0b0000000000000001) ? 0b1000000000000000 : 0 ) | \
                            ( ((uint16_t)b & 0b0000000000000010) ? 0b0100000000000000 : 0 ) | \
                            ( ((uint16_t)b & 0b0000000000000100) ? 0b0010000000000000 : 0 ) | \
                            ( ((uint16_t)b & 0b0000000000001000) ? 0b0001000000000000 : 0 ) | \
                            ( ((uint16_t)b & 0b0000000000010000) ? 0b0000100000000000 : 0 ) | \
                            ( ((uint16_t)b & 0b0000000000100000) ? 0b0000010000000000 : 0 ) | \
                            ( ((uint16_t)b & 0b0000000001000000) ? 0b0000001000000000 : 0 ) | \
                            ( ((uint16_t)b & 0b0000000010000000) ? 0b0000000100000000 : 0 ) | \
                            ( ((uint16_t)b & 0b0000000100000000) ? 0b0000000010000000 : 0 ) | \
                            ( ((uint16_t)b & 0b0000001000000000) ? 0b0000000001000000 : 0 ) | \
                            ( ((uint16_t)b & 0b0000010000000000) ? 0b0000000000100000 : 0 ) | \
                            ( ((uint16_t)b & 0b0000100000000000) ? 0b0000000000010000 : 0 ) | \
                            ( ((uint16_t)b & 0b0001000000000000) ? 0b0000000000001000 : 0 ) | \
                            ( ((uint16_t)b & 0b0010000000000000) ? 0b0000000000000100 : 0 ) | \
                            ( ((uint16_t)b & 0b0100000000000000) ? 0b0000000000000010 : 0 ) | \
                            ( ((uint16_t)b & 0b1000000000000000) ? 0b0000000000000001 : 0 ) 

Umieściłbym bw nawiasach na wypadek, gdyby było to bardziej złożone wyrażenie niż pojedyncza liczba, a może również zmienić nazwę makra na REVERSE_BYTEwskazówkę, że prawdopodobnie nie chcesz mieć tam bardziej złożonego (uruchomieniowego) wyrażenia. Lub uczyń to funkcją wbudowaną. (Ale ogólnie podoba mi się to jako na tyle proste, że można to łatwo zrobić z pamięci z bardzo małą szansą na błąd.)
Arkku

1

Zakładając, że Twój kompilator zezwala na długi bez znaku :

unsigned char reverse(unsigned char b) {
  return (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;
}

Odkryto tutaj


1

Jeśli używasz małego mikrokontrolera i potrzebujesz szybkiego rozwiązania o małej powierzchni, mogą to być rozwiązania. Można go użyć do projektu C, ale musisz dodać ten plik jako plik assemblera * .asm, do swojego projektu w C. Instrukcje: W projekcie C dodaj tę deklarację:

extern uint8_t byte_mirror(uint8_t);

Wywołaj tę funkcję z C

byteOutput= byte_mirror(byteInput);

To jest kod, nadaje się tylko do rdzenia 8051. W rejestrze procesora r0 znajdują się dane z byteInput . Kod obróć w prawo r0 cross carry, a następnie obróć w lewo do r1 . Powtórz tę procedurę 8 razy dla każdego bitu. Następnie rejestr r1 jest zwracany do funkcji c jako byteOutput. W rdzeniu 8051 można obracać tylko akumulator a .

NAME     BYTE_MIRROR
RSEG     RCODE
PUBLIC   byte_mirror              //8051 core        

byte_mirror
    mov r3,#8;
loop:   
    mov a,r0;
    rrc a;
    mov r0,a;    
    mov a,r1;
    rlc a;   
    mov r1,a;
    djnz r3,loop
    mov r0,a
    ret

PLUSY: Jest mały, jest szybki WADY: Nie jest to kod wielokrotnego użytku, dotyczy tylko 8051

011101101-> nosić

101101110 <-carry


Chociaż ten kod może odpowiedzieć na pytanie, lepiej byłoby uwzględnić kontekst, wyjaśniając, jak to działa i kiedy go używać. Odpowiedzi zawierające tylko kod nie są przydatne na dłuższą metę.
fNek

0
  xor ax,ax
  xor bx,bx
  mov cx,8
  mov al,original_byte!
cycle:   shr al,1
  jnc not_inc
  inc bl
not_inc: test cx,cx
  jz,end_cycle
  shl bl,1
  loop cycle
end_cycle:

odwrócony bajt będzie w rejestrze bl


3
W innym kontekście to może być uczciwa odpowiedź, ale pytanie dotyczyło C lub C ++, a nie asm ...
jadsq

0
typedef struct
{
    uint8_t b0:1;
    uint8_t b1:1;
    uint8_t b2:1;
    uint8_t b3:1;
    uint8_t b4:1;
    uint8_t b5:1;
    uint8_t b6:1;
    uint8_t b7:1;
} bits_t;

uint8_t reverse_bits(uint8_t src)
{
    uint8_t dst = 0x0;
    bits_t *src_bits = (bits_t *)&src;
    bits_t *dst_bits = (bits_t *)&dst;

    dst_bits->b0 = src_bits->b7;
    dst_bits->b1 = src_bits->b6;
    dst_bits->b2 = src_bits->b5;
    dst_bits->b3 = src_bits->b4;
    dst_bits->b4 = src_bits->b3;
    dst_bits->b5 = src_bits->b2;
    dst_bits->b6 = src_bits->b1;
    dst_bits->b7 = src_bits->b0;

    return dst;
}

Jako uwaga stylistyczna, uważam, że użycie uint8_tpól 1-bitowych jest trochę brzydkie, ponieważ wydaje się, że najpierw mówi, że zajmie 8 bitów, ale na końcu linii definiuje to jako tylko jeden bit. Chciałbym używać unsigned b0:1itd.
Arkku

0
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i;
    unsigned char rev = 0x70 ; // 0b01110000
    unsigned char tmp = 0;

    for(i=0;i<8;i++)
    {
    tmp |= ( ((rev & (1<<i))?1:0) << (7-i));
    }
    rev = tmp;

    printf("%x", rev);       //0b00001110 binary value of given number
    return 0;
}

Proszę dodać wyjaśnienie.
zcui93,

0

Myślę, że to dość proste

uint8_t reverse(uint8_t a)
{
  unsigned w = ((a << 7) & 0x0880) | ((a << 5) & 0x0440) | ((a << 3) & 0x0220) | ((a << 1) & 0x0110);
  return static_cast<uint8_t>(w | (w>>8));
}

lub

uint8_t reverse(uint8_t a)
{
  unsigned w = ((a & 0x11) << 7) | ((a & 0x22) << 5) | ((a & 0x44) << 3) | ((a & 0x88) << 1);
  return static_cast<uint8_t>(w | (w>>8));
}

0
unsigned char c ; // the original
unsigned char u = // the reversed
c>>7&0b00000001 |
c<<7&0b10000000 |
c>>5&0b00000010 |
c<<5&0b01000000 |
c>>3&0b00000100 |
c<<3&0b00100000 |
c>>1&0b00001000 |
c<<1&0b00010000 ;

Explanation: exchanged bits as per the arrows below.
01234567
<------>
#<---->#
##<-->##
###<>###

0

Wrzucę swoje rozwiązanie, ponieważ jak dotąd nie mogę znaleźć czegoś takiego w odpowiedziach. Może jest trochę przeprojektowany, ale generuje tablicę przeglądową przy użyciu C ++ 14 std::index_sequencew czasie kompilacji.

#include <array>
#include <utility>

constexpr unsigned long reverse(uint8_t value) {
    uint8_t result = 0;
    for (std::size_t i = 0, j = 7; i < 8; ++i, --j) {
        result |= ((value & (1 << j)) >> j) << i;
    }
    return result;
}

template<size_t... I>
constexpr auto make_lookup_table(std::index_sequence<I...>)
{
    return std::array<uint8_t, sizeof...(I)>{reverse(I)...};   
}

template<typename Indices = std::make_index_sequence<256>>
constexpr auto bit_reverse_lookup_table()
{
    return make_lookup_table(Indices{});
}

constexpr auto lookup = bit_reverse_lookup_table();

int main(int argc)
{
    return lookup[argc];
}

https://godbolt.org/z/cSuWhF


0

Oto proste i czytelne rozwiązanie, przenośne na wszystkie zgodne platformy, w tym te z sizeof(char) == sizeof(int):

#include <limits.h>

unsigned char reverse(unsigned char c) {
    int shift;
    unsigned char result = 0;

    for (shift = 0; shift < CHAR_BIT; shift++) {
        result <<= 1;
        result |= c & 1;
        c >>= 1;
    }
    return result;
}

0

Wiem, że to pytanie jest przestarzałe, ale nadal uważam, że temat jest istotny do pewnych celów, a oto wersja, która działa bardzo dobrze i jest czytelna. Nie mogę powiedzieć, że jest najszybszy lub najbardziej wydajny, ale powinien być jednym z najczystszych. Dołączyłem również funkcję pomocniczą do łatwego wyświetlania wzorów bitowych. Ta funkcja używa niektórych standardowych funkcji bibliotecznych zamiast pisania własnego manipulatora bitowego.

#include <algorithm>
#include <bitset>
#include <exception>
#include <iostream>
#include <limits>
#include <string>

// helper lambda function template
template<typename T>
auto getBits = [](T value) {
    return std::bitset<sizeof(T) * CHAR_BIT>{value};
};

// Function template to flip the bits
// This will work on integral types such as int, unsigned int,
// std::uint8_t, 16_t etc. I did not test this with floating
// point types. I chose to use the `bitset` here to convert
// from T to string as I find it easier to use than some of the
// string to type or type to string conversion functions,
// especially when the bitset has a function to return a string. 
template<typename T>
T reverseBits(T& value) {
    static constexpr std::uint16_t bit_count = sizeof(T) * CHAR_BIT;

    // Do not use the helper function in this function!
    auto bits = std::bitset<bit_count>{value};
    auto str = bits.to_string();
    std::reverse(str.begin(), str.end());
    bits = std::bitset<bit_count>(str);
    return static_cast<T>( bits.to_ullong() );
}

// main program
int main() {
    try {
        std::uint8_t value = 0xE0; // 1110 0000;
        std::cout << +value << '\n'; // don't forget to promote unsigned char
        // Here is where I use the helper function to display the bit pattern
        auto bits = getBits<std::uint8_t>(value);
        std::cout << bits.to_string() << '\n';

        value = reverseBits(value);
        std::cout << +value << '\n'; // + for integer promotion

        // using helper function again...
        bits = getBits<std::uint8_t>(value);
        std::cout << bits.to_string() << '\n';

    } catch(const std::exception& e) {  
        std::cerr << e.what();
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}

I daje następujący wynik.

224
11100000
7
00000111

0

Ten pomógł mi z zestawem tablic z matrycą punktową 8x8.

uint8_t mirror_bits(uint8_t var)
{
    uint8_t temp = 0;
    if ((var & 0x01))temp |= 0x80;
    if ((var & 0x02))temp |= 0x40;
    if ((var & 0x04))temp |= 0x20;
    if ((var & 0x08))temp |= 0x10;

    if ((var & 0x10))temp |= 0x08;
    if ((var & 0x20))temp |= 0x04;
    if ((var & 0x40))temp |= 0x02;
    if ((var & 0x80))temp |= 0x01;

    return temp;
}

1
Ta funkcja w rzeczywistości nie działa, odwrotnością 0b11001111 powinno być 0b11110011, ale nie działa z tą funkcją. Ta sama metoda testowania działa w przypadku wielu innych wymienionych tutaj funkcji.
Dan

Tak, dzięki, poprawiłam odpowiedź. Dzięki za poinformowanie mnie o moim błędzie :)
R1S8K
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.