Lekce 7 - Binární operace

V minulé lekci, Konstantní hodnoty, jsme se věnovali konstantám. Dnes to bude ještě více nízkoúrovňové, než jsme zvyklí. Řeč bude totiž o binárních operacích.

Počítač pracuje v soustavě dvojkové. Jsou pouze 2 stavy (0/1), kterých může jeden vstup nabývat. Obecně můžeme stavy 0/1 převést na false (0) a true (1) - Celý počítač můžeme postavit na principu Booleovy algebry (část oboru matematické logiky). Booleova algebra disponuje dvěma stavy (true a false) a sadou několika funkcí, díky kterým můžeme vyjadřovat různé podmínky a závěry. V dnešním článku si jednotlivé funkce projdeme, řekneme si, jak jsou v C implementované a jak lze s nimi pracovat.

Logické funkce

Logická funkce zpravidla přijímá dva vstupy a má jeden výstup. Vstupy i výstup jsou hodnoty 0/1 neboli true/false. Pro článek projdeme pouze funkce, které jsou dostupné v C. Každou funkci můžeme určit tabulkou pravdivostních hodnot. Tabulka bude mít stejný počet vstupů jako má funkce, a navíc sloupeček udávající výstupní hodnotu. Za seznamem jednotlivých funkcí je uvedena tabulka a jsou do ní zaneseny všechny probírané funkce.

AND

And neboli logický součin. Jedná se o funkci, která je pravdivá pouze v případě, kdy jsou pravdivé oba vstupy. Obvykle použijeme při kontrole, zda je splněna nějaké předem daná podmínka. V céčku zapisujeme symbolem binární ekvivalenci ampersandu (&).

OR

Or neboli logický součet. Funkce je pravdivá v případě, že je alespoň jeden ze vstupů pravdivý. Obvykle se používá ke zjištění, zda je nějaká sada vstupů nastavena. V céčku zapisujeme binární ekvivalenci svislítkem (|).

XOR

Xor neboli exkluzivní or. Jak už název napovídá, funkce je velmi podobná logickému součtu. Jediný rozdíl je v situaci, kdy jsou oba vstupy pravdivé. Xor vrátí 0 (false), zatímco or vrátí 1 (true). Proto je xor označen jako exkluzivní or, musí být pravdivý pouze jeden ze vstupů, nesmí být oba. V céčku značíme binární ekvivalenci stříškou (^)

NOT

Not neboli negace je velmi jednoduchá funkce, která vrací opak vstupu. Je-li vstup pravdivý, funkce vrátí 0 (false). Při nepravdivém vstupu je návratová hodnota 1 (true). V céčku značíme binární ekvivalenci vlnovkou (~).

Nakonec uvádím tabulku pravdivostních hodnot, kde "a" a "b" jsou vstupy.

Chování logiky v C

V C se můžeme setkat s logikou například u podmínek nebo cyklů. Operace se vždy převede na pravdivostní hodnotu. Céčko nemá typ bool, jako je tomu třeba v C++ nebo v jiných jazycích. Z toho důvodu C jakoukoliv nenulovou hodnotu považuje za true. Pouze 0 je v C false. Pokud pravdivostní hodnotu samo generuje, poté C za true vypíše 1 (ukázka je ve výpisu dále).

Určitě jste se divili, proč u každé funkce explicitně říkám "binární ekvivalence". Céčko totiž standardně rozlišuje operace logické a binární. Logické operace již známe, běžně je používáme u podmínek (&&, ||, !). Binární operace pracují s celým číslem jako sekvencí bitů. Při aplikování binární operace se logické operace aplikuje pro každý bit v čísle. Před dalším čtením doporučují přečíst článek o převádění mezi soustavami.

Budeme-li pracovat pouze s čísly 1 a 0, budou logické a binární operace ekvivalentní. Pracujeme-li i s jinými čísly, výsledek se může lišit. To koneckonců ukazuje následující program:

int main(int argc, char** argv)
{
    printf("5 > 4 = %x\n", 5 > 4); //true
    printf("5 < 4 = %x\n", 5 < 4); //false
    if (1) printf("1 je vhodnoceno jako true\n");
    if (5) printf("5 je vhodnoceno jako true\n");
    if (0); else printf("0 je vyhodnoceno jako false\n");
    if (!0) printf("!0 je vyhodnoceno jako true\n");
    printf("5 && 4 = %x\n", 5 && 4); //logický AND
    printf("5 & 4 = %x\n", 5 & 4); //binární AND
    printf("5 || 4 = %x\n", 5 || 4); //logický OR
    printf("5 | 4 = %x\n", 5 | 4); //binární OR
    printf("!5 = %x\n", !5); //logická negace
    printf("!0 = %x\n", !0); //logická negace
    printf("~5 = %x\n", ~5); //binární negace
    printf("5 ^ 4 = %x\n", 5 ^ 4); //binární XOR
    printf("(5 ^ 4) && 0 = %x", (5^4) && 0);
    return (EXIT_SUCCESS);
}

Výsledek:

BinarniALogickeOperace
5 > 4 = 0x1
5
< 4 = 0
1 je vyhodnoceno jako true
5 je vyhodnoceno jako true
0 je vyhodnoceno jako false
0! je vyhodnoceno jako true
5 && 4 = 0x1
5 & 4 = 0x4
5 || 4 = 0x1
5 | 4 = 0x5
!5 = 0
!0 = 0x1
~5 = 0xfffffffa
5 ^ 4 = 0x1
(5 ^ 4) && 0 = 0

Dopuručuji si příklady pořádně projít. Logické a binární operace nepracují stejně, ale lze je kombinovat (jak předvádí poslední výstup). K tomuto tématu se ještě jednou vrátíme v příštím článku, kde si představíme tzv. bitové flagy.

Bitový posun

Existuje ještě jedna operace, která nemá základ v logických operacích. Jedná se o tzv. bitový posun. Nejprve si představíme číslo jako bitové pole. Posunem rozumíme takovou operaci, kdy se všechny bity přesunou o stejný počet míst. Bity, které vypadly z pole zahodíme a bity, které nám nyní chybí, doplníme nulami. Představme si číslo o velikosti 1 bajt reprezentované v binární soustavě. Bitové posuny se chovají následujícím způsobem:

10010111 => 00101110    //bitový posun o jedno místo vlevo
10010111 => 10111000    //bitový posun o tři místa vlevo
10010111 => 01001011    //bitový posun o jedno místo vpravo
10010111 => 00010010    //bitový posun o tři místa vpravo

V céčku značíme bitový posun dvěma šipkami. Současně se za šipky přidává index, o kolik se má číslo posunout. Příklad výše by byl v C zapsán následovně:

0b10010111 << 1 == 0b00101110   //bitový posun o jedno místo vlevo
0b10010111 << 3 == 0b10111000   //bitový posun o tři místa vlevo
0b10010111 >> 1 == 0b01001011   //bitový posun o jedno místo vpravo
0b10010111 >> 3 == 0b00010010   //bitový posun o tři místa vpravo

Pozn. autora: Předpona 0b znamená, že je číslo zapsané v binární podobě. Tato konstrukce není podporovaná u všech kompilátorů. GCC, který je nainstalovat v Cygwinu, tuto podobu čísla akceptuje.

Bitový posun je ekvivalentní s operací dělení (nebo násobení) čísla mocninou 2. Na rozdíl od dělení (nebo násobení) je operace bitového posunu méně náročná na procesor (a je tedy rychlejší). Tím ovšem nechci říct, abyste od teď používali pro operace násobení a dělení bitové posuny. Kompilátory jsou již dnes dostatečně chytré na to, aby váš kód dokázali optimalizovat. Pokud tedy někde použijete operaci dělení číslem 2, je velmi pravděpodobné, že kompilátor operaci nahradí právě bitovým posunem.

int main(int argc, char** argv)
{
    printf("0x26 >> 1 = %#x\n", 0x26 >> 1);  //bitový posun o jedno místo vpravo
    printf("0x26 >> 3 = %#x\n", 0x26 >> 3);  //bitový posun o tři místa vpravo
    printf("0x26 << 1 = %#x\n", 0x26 << 1);  //bitový posun o jedno místo vlevo
    printf("0x26 << 3 = %#x\n", 0x26 << 3);  //bitový posun o tři místa vlevo
    printf("14 / 2 = %d\n", 14 >> 1);
    printf("32 / 8 = %d\n", 32 >> 3);
    printf("3 * 2 = %d\n", 3 << 1);
    printf("3 * 16 = %d\n", 3 << 4);
    return (EXIT_SUCCESS);
}

Výsledek:

BitovyPosun
0x26 >> 1 = 0x13
0x26 >> 3 = 0x4
0x26 << 1 = 0x4c
0x26 << 3 = 0x130
14 / 2 = 7
32 / 8 = 4
3 * 2 = 6
3 * 16 = 48

Bitový posun můžeme využít například při extrahování barevných složek. Budeme vědět, že každá barva zabírá 1 bajt. Dále víme, že složky jsou poskládány jako RGBA (tedy červená, zelená, modrá, průhlednost). Potom hodnotu zelené složky získáme jednoduše:

int zelena = (barva << 8) >> 24.

Nyní byste měli být schopni pracovat s jednotlivými bity. Zatím ale nemáme nejmenší důvod něco takového dělat. To napravíme příště, v lekci Výčtové typy, kdy si řekneme o výčtových typech a bitových příznacích.