Odwróć liczbę n-bitową w czasie O(log n)

Gdy kiedyś pisałem tekst o tym, jak działa skanowanie tablicy mieszającej w Redisie, natknąłem się na interesujący algorytm na odwrócenie liczby całkowitej. Na przykład, liczba 10100011 zostaje zamieniona na 11000101. Co więcej, zmiana ta następuje w O(log n) iteracjach.

Oto kod, o którym mówię:

unsigned long reverse(unsigned long num) {
  unsigned long s = 8 * sizeof(num); // bit size; must be power of 2
  unsigned long mask = ~0;
  while ((s >>= 1) > 0) {
    mask ^= (mask << s);
    num = ((num >> s) & mask) | ((num << s) & ~mask);
  }
  return num;
}

9 linijek zawierających sygnatury i zamknięcia nawiasów klamrowych. Zobaczmy, jak to działa.

W dalszej części artykułu przyjrzymy się kodowi linijka po linijce.

Update: złożoność czasowa O(log n) dotyczy tylko n ≤ długość słowa maszynowego, która zazwyczaj wynosi dzisiaj 64 bity. Dziękuję wszystkim, którzy zwrócili mi na to uwagę.

Rekurencyjny block-swapping

Algorytm ten rekurencyjnie podmienia bloki bitów, zmniejszając przez to rozmiar bloku w każdej iteracji. Zaczyna od podmienienia 2 bloków n/2 bitowych, potem 4 bloków n/4 bitowych, 8 bloków n/8 bitowych i tak dalej, aż kończy na n liczbie bloków z 1 bitem. 

W każdej iteracji wszystkie pary przylegających bloków są równolegle podmieniane. Wynikiem tego jest właśnie odwrócona liczba. Aby podmieniać bloki równolegle, algorytm wykorzystuje operatory i maski bitowe. 

ADNOTACJA: oryginalny kod używa 32-bitowego wejścia. My użyjemy 8-bitowych liczb całkowitych, żeby ułatwić zrozumienie pewnych rzeczy. 

Zamiana przylegających bloków bitów

Równoległa zamiana bloków dzieje się dzięki specjalnie wykonanej masce bitowej. 

Dla bloku od długości s maska bitowa mask składa się z naprzemianległych bloków s zer i s jedynek. Na przykład, dla s = 4, mask == 00001111, a dla s = 2, mask == 00110011.

Poniższa linijka wykorzystuje maskę do równoległej zamiany wszystkich par bloków: 

num = ((num >> s) & mask) | ((num << s) & ~mask);

• (num >> s) & mask)przesuwa parzyste bloki o s pozycji w prawo i pozbywa się nieparzystych bloków przy użyciu maski.
• (num << s) & ~maskprzesuwa nieparzyste bloki o s pozycji w lewo i czyści parzyste bloki używając bitowego NIE maski.
• Operator bitowy LUB jest wykorzystywany do połączenia powyższych rezultatów w odwróconą liczbę.

Niesamowicie proste, prawda?

Tworzenie maski

Kolejny trick polega na tym, w jaki sposób tworzona jest maska. Składa się ona bowiem z naprzemianległych bloków s zer i jedynek. Pierwsza wersja maski zawiera same jedynki i jest aktualizowana w pierwszej linijce pętli. 

while ((s >>= 1) > 0) {
  mask ^= (mask << s);
  ...

Dzieje się to zaraz po tym, jak s zostaje zmniejszone o połowę, aby było połową rozmiaru bloku mask. W pierwszej iteracji mask == 11111111 i s == 4. Maska jest aktualizowana przez funkcję XOR z kolejną kopią samej siebie, przesuniętej w lewo o s miejsc.

mask = 
    11111111 XOR  // mask
    11110000      // mask << s
  = 00001111

Funkcja XOR z dwóch bitów wynosi jeden wtedy i tylko wtedy, gdy nie są one sobie równe. W każdej iteracji aktualizacji maski, wszystkie bloki są przesuwane w lewo o połowę ich rozmiaru.

Kiedy użyjemy na bloku funkcji XOR z poprzednią maską, połowa bloku nałoży się na zera, a druga połowa nałoży się na jedynki. Tworzy to 2 bloki w nowej masce, każdy o połowę miejszy od swojego poprzedniego wcielenia. Oto jak to wygląda:

0000000011111111  // original mask, 8-bit blocks
0000111111110000  // mask shifted left by block-size/2
0000111100001111  // XORed: new mask, 4-bit blocks

Składanie wszystkiego do kupy

Oto krótka animacja, która pokazuje nasz algorytm w akcji:

Niesamowite, jak dużo głębi można odnaleźć w 9 linijkach kodu. 

Oryginał tekstu w języku angielskim przeczytasz tutaj.