Jak nauczyły nas stare procesory i kompilatory, if'y bywają kosztowne - każdy if tłumaczony jest na jeden lub dwa skoki (w zależności czy to if czy else if), a skoki miały zwyczaj czyścić kolejkę instrukcji do wykonania w CPU, przez co były dość kosztowne. W związku z czym szukało się innych metod na zapisanie serii if'ów, np. za pomocą operacji matematycznych lub logicznych, które były mniej kosztowne (gdy występowały w niewielkiej ilości) niż skoki które czyściły kolejkę instrukcji. Oczywiście nowe procesory pozwalają na oznaczenie bardziej prawdopodobnych skoków (druga grupa prefiksów, prefiksy 2E (branch not taken) i 3E (branch taken)), a nowe kompilatory C/C++ pozwalają oznaczyć czy warunek w if będzie bardziej czy mniej prawdopodobny (patrz __builtin_expect), a nawet można skorzystać z profilerów i samemu sformułować if'y tak aby testowały zawsze te mniej czy bardziej prawdopodobne warunki (oczywiście trzeba wiedzieć jak kompilator tłumaczy kod, ale nie jest to specjalnie trudne). Niemniej jednak czasami nachodzi człowieka ochota żeby zastąpić parę if'ów jakimś ładnym działaniem matematycznym, a tym samym... utrudnić sobie życie ;>

W zasadzie zanim przejdę dalej, gritzy za j00ru, który razem ze mną kombinował jak to inaczej zapisać ;>

Problem był prosty: zapisać za pomocą działań matematycznych poniższą, składającą się z dwóch inline if'ów, linijkę kodu (osoby związane z grafiką komputerową od strony programowania, pewnie nie raz widziały taką czy podobną linię kodu):
 r = r > 255 ? 255 : r < 0 ? 0 : r; // int r, CPU = x86, sizeof(int) = 4

Kod ten działa w taki oto sposób:
Jeżeli r jest większe od 255, r = 255
Jeżeli r jest mniejsze od 0, r = 0
Jeżeli r jest z przedziału domkniętego [0,255], r ma pozostać bez zmian

Zanim przejdę dalej, ważna uwaga - we wszystkich poniższych operacjach 'r' traktuje jak unsigned int - czyli w razie czego należy dokonać cast z int na unsigned int (nie chce aby kompilator korzystał z instrukcji dopełniających najbardziej znaczący bit przy niektórych operacjach).

Zacznijmy od części 'jeżeli r jest mniejsze od 0, r = 0' - czyli, dla każdej liczby ujemnej, r ma być równe 0. Jako że liczba 0 jest dość charakterystyczna (wszystkie bity ustawione na 0), możemy spróbować zrobić mnożenie lub AND bitowe na r liczby 0 jeżeli r jest ujemne, lub 0xff (255 = 0xff, 0xff = 1111 1111, 8 bitów bo do zapisania 255 i tak więcej nam nie potrzeba) jeśli r jest dodatnie, czyli np.:
 r = r & (r < 0 ? 0 : 0xff)

Oczywiście ten inline if tam nas nie zadowala, więc postarajmy się go zastąpić czymś innym.

Jak wiadomo, każda liczba ujemna zapisana w systemie U2 (z którego korzysta x86 w przypadku intów) będzie miała najbardziej znaczący bit (tj. 31 bit, licząc od 0) zapalony. Korzystając z tego, możemy napisać:
(r >> 31)

Po tej operacji, r będzie równe 0 jeżeli liczba była dodatnia, a 1 jeżeli była ujemna. Jednak my chcemy uzyskać 0 dla ujemnych, a 0xff dla dodatnich. Możemy to zrobić po prostu odejmując 1.

(r >> 31) - 1)

Teraz, dla liczb dodatnich, będzie to (0 - 1) czyli -1, a więc w systemie U2 0xffffffff, a dla liczb ujemnych, będzie to (1 - 1), czyli 0. Oczywiście teraz wystarczy zrobić AND bitowe z 0xff, i dostajemy 0xff dla dodatnich, i 0 dla ujemnych, czyli dokładnie to co zwraca (r < 0 ? 0 : 0xff). Możemy więc napisać:

r = r & (((r >> 31) - 1) & 0xff)

OK, dolna część liczb załatwiona, teraz czas na pozostałe dwa warunki, czyli 'dla liczb > 255, zwróć 255, a dla liczb mniejszych od 255, zwróć daną liczbę'. Całość możemy sprowadzić do instrukcji OR bitowego z liczbą 0xff jeżeli liczba jest większa od 255, lub 0 jeżeli liczba jest mniejsza, i do AND bitowego z 0xff.
r = (r | (r > 255 ? 0xff : 0)) & 0xff

Jeżeli r będzie większe niż 255, to zostanie wykonany OR bitowy z 255, czyli bity od 0 do 7 zostaną zapalone, a następnie AND bitowy przytnie wszystkie pozostałe bity, tak aby zostało tylko to 1111 1111, czyli 255. Ale znowu mamy inline if'a.

Jak się go pozbyć ? Możemy tutaj skorzystać z faktu że jeżeli liczba jest większa niż 255, to na pewno będzie zapalony któryś bit powyżej 7dmego (jak pisałem wcześniej, 255 to 1111 1111, czyli bity od 0 do 7 zapalone, tak więc każda większa liczba będzie musiała zapalić któryś dalszy bit, np. 8smy czy 30sty). Skorzystajmy więc z negacji liczby (!) aby osiągnąć wartości 0 lub jeden, jeżeli któreś górne bity r są zapalone:
!(r >> 8)

Teraz, dla r > 255, dostaniemy !(liczba większa lub równa 1), czyli 0, a dla r <= 255, dostaniemy !(0), czyli 1. Ponownie skorzystamy z odejmowania aby dostać wszystkie bity zapalone lub zgaszone, i ponownie użyjemy AND bitowego do obcięcia bitów zapalonych do dolnych ośmiu.
(((!(r >> 8)) - 1) & 0xff)

Po tej operacji dla dodatnich r > 255 dostajemy liczbę 0xff, a dla dodatnich r <= 255, dostajemy 0. Czyli możemy podmienić powyższego if'a.
r = (r | (((!(r >> 8)) - 1) & 0xff)) & 0xff

Oczywiście powyższy zapis nie działa za dobrze dla liczb ujemnych, które przecież wszystkie mają zapalony bit numer 31, więc zostaną potraktowane jak liczby większe od 255. Ale spokojnie możemy to zignorować - druga część równania (czyli to co wyprowadziliśmy wcześniej) się tym zajmie.

OK, a teraz łączymy obie części równania - jest to dość proste - za pierwsze 'r' w pierwszym równaniu wystarczy podstawić drugie równanie, dzięki czemu otrzymamy:
r = (r | (((!(r >> 8)) - 1) & 0xff)) & 0xff & (((r >> 31) - 1) & 0xff)

Oczywiście tak na prawdę wystarczy jedno & 0xff, więc reszty możemy się pozbyć - zostawmy tylko ostatnie.
r = (r | ((!(r >> 8)) - 1)) & (((r >> 31) - 1) & 0xff)

Możemy jeszcze napisać jakiś programik testowy, i zobaczyć że to na prawdę działa:

#include <stdio.h>

int func(unsigned int r)
{
 r = (r | ((!(r >> 8)) - 1)) & (((r >> 31) - 1) & 0xff);
 return r;

}

int
main(void)
{
 int i;

 for(i = -1024; i <= 1024; i++)
   printf("%i = %i\n", i, func((unsigned int)i));

 return 0;
}


Kompilacja i output:

$ g++ t1.cpp
$ ./a.out
-1024 = 0
-1023 = 0
-1022 = 0
-1021 = 0
[...]
-3 = 0
-2 = 0
-1 = 0
0 = 0
1 = 1
2 = 2
3 = 3
4 = 4
[...]
252 = 252
253 = 253
254 = 254
255 = 255
256 = 255
257 = 255
258 = 255
[...]
1020 = 255
1021 = 255
1022 = 255
1023 = 255
1024 = 255


Powyższy post stanowi dowód na to że można część ifów zapisać jako operacje matematyczne, ale prawie że na pewno nie należy tego robić ze względu na znaczną utratę czytelności kodu ;>
Natomiast niewątpliwie jest to pouczające doświadczenie ;>

Pytanie na koniec - czy będzie to rzeczywiście szybsze od dwóch if'ów? Hmm... może na starszych komputerach, ale teraz, nie sądzę ;&gt; (niemniej jednak zachęcam do testów)

I tyle...

P.S. dodam że niektóre (tak, GCC) kompilatory operacje ! zapisują jako:
       test    eax, eax
       jne     L2
       mov     DWORD PTR [ebp-4], 0
       jmp     L4
L2:
       mov     DWORD PTR [ebp-4], -1
L4:

Tak więc ćwiczenie dla zainteresowanych - jak się pozbyć ! z działań ?;>