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 os
pozycji w prawo i pozbywa się nieparzystych bloków przy użyciu maski.(num << s) & ~mask
przesuwa nieparzyste bloki os
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.