C++ - tips & tricks

Kilka mniej lub bardziej użytecznych sztuczek, które czasem mogą okazać się przydatne. Można stosować je także w innych językach, niż C++.
Zaprezentowane niżej sztuczki nie są wymyślone przeze mnie – ja je tylko zebrałem i opisałem w jaki sposób działają.

Zamienianie miejscami 2 liczb bez użycia zmiennej tymczasowej

Standardowy kod służący do zamiany między sobą zawartości 2 zmiennych wygląda mniej więcej tak:

int a,b,//liczby, które chcemy zamienić miejscami
t;//zmienna tymczasowa
t=a;
a=b;
b=t;

Można jednak wykonać taką operację nie używając zmiennej tymczasowej, korzystając z instrukcji XOR:

a^=b^=a^=b;

co jest równoważne konstrukcji:

a^=b;
b^=a;
a^=b;

Dlaczego to działa? Już tłumaczę. Przyjmijmy, ze zmienna 'a' jest początkowo równa 'x', a zmienna 'b' jest równa 'y':

//a=x
//b=y
a^=b;
//a=x^y
//b=y
b^=a;
//a=x^y
//b=y^x^y=x
a^=b;
//a=x^y^x=y
//b=x

Jak widać, po ostatnim kroku algorytmu zmienna 'a' jest równa 'y', a 'b' jest równa 'x', wiec wszystko działa poprawnie :)
Jest tu wykorzystane kilka własności operacji XOR, czyli:

1. (a XOR b) XOR c = a XOR (b XOR c) = a XOR b XOR c

2. a XOR b = b XOR a

3. a XOR a = 0

4. a XOR 0 = a

Jak widać, należy uważać podczas używania tego sposobu, gdyż jeżeli 'a' i 'b' będą referencjami wskazującymi na tę samą zmienną, to wówczas obie zmienne zostaną wyzerowane!

Szybka operacja modulo

Aby uzyskać resztę z dzielenia a przez b, gdzie b jest całkowitą dodatnią potęgą liczby 2, nie trzeba koniecznie używać powolnego standardowego operatora '%' (MOD). Można to samo wykonać używając o wiele wydajniejszego operatora '&' (AND).

a%b

jest równoważne

a&(b-1)

przy założeniu, że b jest potęga liczby 2.

Czyli, na przykład a MOD 2 jest równoważne a AND 1, a a MOD 16 jest równoważne a AND 15.

Działanie tej metody opiera się na spostrzeżeniu, że w systemie binarnym potęgi liczby 2 są reprezentowane za pomocą jedynki, po której następują same zera (dokładnie n zer). Liczba postaci 2ⁿ – 1 jest reprezentowana natomiast jako n jedynek. Reszta z dzielenia przez liczbę będącą n-tą potęgą podstawy systemu liczbowego jest po prostu liczbą stworzoną z n ostatnich cyfr liczby w tym systemie, np.:

123352532₍₁₀₎ MOD 100₍₁₀₎ = 32₍₁₀₎

101001101₍₂₎ MOD 10₍₂₎ = 1₍₂₎

Operacja AND posiada następujące właściwości:

1 AND 1 = 1
1 AND 0 = 0
0 AND 1 = 0
0 AND 0 = 0

Tak wiec wynik operacji a AND b będzie zawierał bity zawsze wyzerowane na tych pozycjach, gdzie liczba 'b' posiada bity wyzerowane. Natomiast na pozycjach, na których liczba 'b' posiadała bity o wartości 1, wynik będzie zawierał bit z tej samej pozycji liczby 'a' (ale namieszałem... ;)).

Tak więc, liczba 'b' będzie postaci 2ⁿ – 1 (czyli będzie zawierać n kolejnych zapalonych bitów), to wynikiem operacji a AND b będzie liczba utworzona z n ostatnich bitów liczby 'a'.

Następna potęga liczby 2

Czasami przytrafia się sytuacja, w której musimy znaleźć liczbę większą od podanej i będącą całkowitą dodatnia potęgą liczby 2. Możemy to osiągnąć na przykład tak:

int y = (int)pow(2,(ceil(log(x) / log(2))));

Jednak liczenie logarytmu naturalnego jest powolne. Możemy także przechowywać tablicy kolejne potęgi dwójki, a podczas działania programu wyszukiwać binarnie odpowiednią liczbę. Istnieje także inny algorytm, w którym stosowane są operacje bitowe – procesor potrafi wykonywać je bardzo szybko. Odpowiedni kod wygląda następująco:

x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
++x;

Na pierwszy rzut oka wygląda skomplikowanie, ale jest on bardzo prosty. Jak już opisywałem w poprzednim punkcie, liczby postaci 2n – 1 składają się z n jedynek. Tak więc wystarczy spowodować, aby wszystkie bity począwszy od najbardziej znaczącego zapalonego bitu były również zapalone, czyli należy spowodować, aby liczba stała się potęgą dwójki zmniejszoną o 1. Później wystarczy jedynie dodać 1 do otrzymanej liczby, uzyskując wynik :)
Pozostaje pytanie – jak zapalić odpowiednie bity?
Otóż to również nie jest skomplikowane. Wystarczy skorzystać z funkcji OR, która ma następujące właściwości:

1 OR 1 = 1
1 OR 0 = 1
0 OR 1 = 1
0 OR 0 =0

Przydatne są także operatory przesunięcia bitowego, o których można poczytać na przykład na Wikipedii: http://pl.wikipedia.org/wiki/Przesuni%C4%99cie_bitowe
Początkowo nasza liczba x jest postaci:...01abcde....po przesunięciu jej o jeden bit w prawo otrzymamy:...001abcd...Po wykonaniu operacji OR na tych 2 liczbach otrzymamy:...011fghij...Czyli zapaliliśmy kolejny bit (i może jeszcze kilka – ale to nic nie zmienia ;)).Można zauważyć, że przesuwając cały czas o 1 bit w prawo i wykonując operacje OR uzyskali byśmy w końcu oczekiwana liczbę. Jednak jest to sposób nieefektywny. Łatwo zauważyć, że możemy przesuwać o kolejne potęgi dwójki (zadanie dla niedowiarków – sprawdzić). Da to nam złożoność logarytmiczną względem liczby bitów w liczbie.

Czasem zdarza się też sytuacja, że chcemy zaokrąglić liczbę do następnej potęgi dwójki tylko wtedy, kiedy nie jest ona (ta liczba) potęgą dwójki. Okazuje się, że rozwiązanie tego problemu jest banalne – wystarczy odjąć jedynkę od początkowej liczby! Dlaczego to działa? Wyobraźmy sobie skrajną sytuację: kiedy x jest już potęgą dwójki. Po odjęciu jedynki i wykonaniu przedstawionego wcześniej algorytmu rezultatem będzie x, więc wszystko się zgadza. Tak więc, po modyfikacjach, kod będzie wyglądał w ten sposób:

--x;
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
++x;

Warto zauważyć, że można ten algorytm wykorzystać również podczas korzystania ze zmiennych o większym lub mniejszym rozmiarze – wystarczy go tylko lekko zmodyfikować, co pozostawiam jako ćwiczenie :)

Sprawdzanie, czy liczba jest potęgą dwójki

Potęgi dwójki są liczbami postaci:

 ...00001000000... 

Potęgi dwójki zmniejszone o 1 są postaci:

 ...00000111111...

 Jeżeli więc wykonamy operację x AND (x-1) i jej wynik będzie równy 0, to liczba 'x' jest potęga dwójki. Można sprawdzić, że dla pozostałych liczb taka sytuacja nie zachodzi. 

Najbardziej znaczący bit 

 Aby znaleźć najbardziej znaczący bit( http://pl.wikipedia.org/wiki/Najbardziej_znacz%C4%85cy_bit ) można wykonać algorytm znajdywania następnej potęgi dwójki większej od podanej liczby, a następnie wykonać przesunięcie bitowe w prawo. Zastanowienie się nad tym dlaczego to działa pozostawiam jako ćwiczenie dla dociekliwego czytelnika.

I to by było na tyle. Jeżeli znacie więcej tego typu sztuczek, to proszę o opisywanie ich w komentarzach.