Zamiana pary bitów w bajcie

Mam dowolny 8-bitowy numer binarny np. 11101101

Muszę zamienić wszystkie pary bitów jak:

Przed zamianą: 11-10-11-01 Po zamianie: 11-01-11-10

Zapytano mnie o to w wywiadzie !
Author: RaviPathak, 2010-09-21
Source

6 answers

W pseudo-kodzie: 

x = ((x & 0b10101010) >> 1) | ((x & 0b01010101) << 1)

Działa poprzez obsługę niskich i wysokich bitów każdej pary bitów osobno, a następnie połączenie wyniku:

  • wyrażenie x & 0b10101010 pobiera wysoki bit z każdej pary, a następnie >> 1 przesuwa go do pozycji niskiego bitu.
  • podobnie wyrażenie (x & 0b01010101) << 1 pobiera niski bit z każdej pary i przesuwa go do wysokiego bitu.
  • obie części są następnie łączone za pomocą bitowego-OR.

Ponieważ nie wszystkie języki pozwala zapisywać literały binarne bezpośrednio, można je zapisać na przykład w szesnastkowym: 

Binary        Hexadecimal  Decimal 
0b10101010    0xaa         170
0b01010101    0x55         85
 32
Author: Mark Byers,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-09-21 08:33:38
  1. utwórz dwie maski bitowe, jedna zawierająca wszystkie parzyste bity i jedna zawierająca nierówne bity (10101010 i 01010101).
  2. Użyj bitwise - i filtruj dane wejściowe na dwie liczby, jedna ma wszystkie parzyste bity zerowane, druga ma wszystkie nierównomierne bity zerowane.
  3. przesuń liczbę zawierającą tylko parzyste bity o jeden bit w lewo, a drugi o jeden bit w prawo
  4. Użyj bitowe-lub połączyć je z powrotem razem.

Przykład dla 16 bitów (nie rzeczywistych kod): 

short swap_bit_pair(short i) {
    return ((i & 0101010110101010b) >> 1) | ((i & 0x0101010101010101b) << 1));
}
 5
Author: tdammers,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-09-21 08:17:42 
b = (a & 170 >> 1) | (a & 85 << 1)
 0
Author: Andy,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-08-21 13:43:05

Najbardziej eleganckim i elastycznym rozwiązaniem jest, jak mówili inni, nałożenie maski "grzebieniowej" zarówno na parzyste, jak i nieparzyste bity, a następnie przesunięcie ich odpowiednio w lewo i w prawo o jedno miejsce, aby połączyć je za pomocą bitowego or.

Inne rozwiązanie, o którym warto pomyśleć, wykorzystuje stosunkowo niewielki rozmiar Twojego typu danych. Możesz utworzyć tabelę z 256 wartościami, która jest statycznie inicjowana na wartości, które chcesz uzyskać jako wynik input: 

const unsigned char lookup[] = { 0x02, 0x01, 0x03, 0x08, 0x0A, 0x09, 0x0B ...

Każda wartość jest umieszczana w tablicy w celu reprezentowania transformacji indeksu. Więc jeśli to zrobisz: 

unsigned char out = lookup[ 0xAA ];

out będzie zawierać 0x55

Jest to bardziej uciążliwe i mniej elastyczne niż pierwsze podejście (co zrobić, jeśli chcesz przejść z 8 bitów do 16?), ale ma podejście, że będzie wymiernie szybsze, jeśli przeprowadzi dużą liczbę tych operacji.

 0
Author: Component 10,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-10-22 08:24:39

Załóżmy, że Twoja liczba to num.

Najpierw znajdź parzysty bit pozycji:
num & oxAAAAAAAA

Drugi krok znajdź dziwny bit pozycji:
num & ox55555555

3. krok zmiana pozycji Pozycja nieparzysta na pozycję parzystą bit i pozycja parzysta na pozycję nieparzystą bit:
Even = (num & oxAAAAAAAA)>>1
Odd = (num & 0x55555555)<<1

Ostatni krok ... result = Even | Odd

Wydrukuj wynik

 0
Author: Sandeep Kumar,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-06-09 19:08:51

Najpierw zakodowałbym go "longhand" - to znaczy w kilku oczywistych, wyraźnych etapach, i użyłbym go do potwierdzenia, że testy jednostkowe, które miałem na miejscu, działały poprawnie, a następnie przejdę do bardziej ezoterycznych rozwiązań manipulacji bitami, jeśli potrzebowałbym wydajności (i że dodatkowa wydajność została dostarczona przez wspomniane improwizacje)

Kod dla ludzi po pierwsze, komputery po drugie.

 -5
Author: PaulJWilliams,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-09-21 08:16:00