1-AIN-140: Princípy počítačov - hardvér - 2. cvičenie

Pozastavme sa najskôr podrobnejšie pri materiáli z predchádzajúceho cvičenia - všimnime si rozdiely medzi nasledujúcimi aritmetickými operátormi:

 a + 1
 a++
Prvý rozdiel spočíva v tom, že operátor sčítania má 2 argumenty (hovoríme, že je to binárna operácia), zatiaľ čo operátor inkrementácie - čiže zvýšenia o 1 - má len jeden argument (voláme to unárna operácia). Okrem toho, operátor sčítania nemá na svoje argumenty žiaden vplyv, to znamená premenná a v prvom riadku príkladu hore sa nezmení. Naopak, operátor ++ svoj argument zmení - hodnota uložená v premennej a sa zvýši o 1. Napriek tomu aj tento operátor vracia hodnotu, takže môžeme zapísať napríklad:

 int c = 3;
 int b = c++;
Akú hodnotu bude mať teraz premenná b? Operátory inkrementácie a dekrementácie poznáme totiž v dvoch verziách: tzv. pre-increment a post-increment, resp. pre-decrement a post-decrement. Predpony pre- resp. post- vyjadrujú, či sa premenná zmení pred tým, ako sa jej hodnota pre výpočet hodnoty celého výrazu použije, alebo potom. V prípade pre-incrementu dôjde najskôr k zvýšeniu hodnoty premennej a až výsledná zvýšená hodnota premennej sa použije:

 int a = 1;
 int b = ++a;
 // a aj b majú teraz hodnotu 2
V prípade post-incrementu sa premenná zvýši až potom, čo sa jej hodnota použije na vyhodnotenie celého výrazu:

 int a = 1;
 int b = a++;
 // a má hodnotu 2, ale b má hodnotu 1
Ďalšiu vec, ktorú si chceme všimnúť, je, že príkaz priradenia, napríklad:

 x = 1;
nie je iba príkaz, ale je to tiež výraz (expression), ktorý sa vyhodnotí na nejakú hodnotu. Z tohoto hľadiska je operátor = podobný ako napr. operátor +, aj keď aj tu vidíme ten istý rozdiel podobne ako pri operátore ++: operátor = mení svoj ľavý operand - musí to byť premenná a zapíše do nej hodnotu na jeho pravej strane. Priraďovaná hodnota je zároveň hodnotou celého výrazu. Preto môžeme zapísať nasledujúce skratky:

 int x = y = 1;  // do x aj do y priradí 1

 if (!(f = fopen("meno_suboru.txt", "r")))
 {
   // súbor sa nepodarilo otvoriť, došlo k chybe a fopen() vrátil 0...
   // vypíš nejaké chybové hlásenie, alebo inak reaguj na neočakávanú chybu...
   return 0;
 }
 // spracuj súbor, v f je file handle otvoreného súboru
 fclose(f); 
 return 1;
Táto príjemná vlastnosť operátora = má ale aj trochu nebezpečné dôsledky. Ak omylom namiesto operátora porovnania (==) napíšeme len jedno rovnítko, tak kompilátor žiadnu chybu neodhalí, program skompiluje, ale bude robiť niečo celkom iné, ako sme potrebovali, napríklad nasledujúci kód:

 if (n = 3)
 {
   printf("prípad s 3 prvkami\n");
   ...
 }
vždy vojde do podmienky a vypíše uvedený reťazec znakov a naviac vždy nastaví premennú n na hodnotu 3. Keďže podmienka sa v jazyku C vyhodnocuje na čokoľvek nenulové (pravda, podmienka splnená) alebo na 0 (nepravda, podmienka nesplnená), hodnota 3, ktorú príkaz priradenia v podmienke if vráti, bude považovaná za pravdivú logickú hodnotu. Tento preklep ostane neodhalený, pričom sme pravdepodobne chceli zapísať toto:

 if (n == 3)
 {
   printf("prípad s 3 prvkami\n");
   ...
 }
Dnešné kompilátory väčšinou pri priradení v podmienke protestujú a ak ho chceme naozaj urobiť, treba výraz v podmienke obaliť ešte do jednej dvojice zátvoriek naviac.

Na tomto cvičení sa chceme pristaviť podrobnejšie pri logických a bitových operátoroch. Najskôr si uvedomme, aký je rozdiel medzi operátormi && a & a analogicky medzi operátormi || a |, resp. medzi ! a ~. V jazyku C namiesto logického typu, ktorý by nadobúdal iba dve možné hodnoty true a false, používame celočíselný typ int, ako sme už uviedli vyššie: hodnota, ktorá je nulová znamená nepravdu a akákoľvek nenulová hodnota znamená pravdu. Predstavme si, že máme dve funkcie:

int dnesPrsi(void);    // vráti niečo nenulové, ak prší, inak 0
int mamDnesCas(void);  // vráti niečo nenulové, ak mám dnes čas, inak 0
potom môžeme zapísať program:

if (dnesPrsi() && mamDnesCas())
  printf("podme do kina!\n");
Tento program bude fungovat aj vtedy, keď prvá funkcia vráti napr. hodnotu 3 a druhá hodnotu 4. Ak by sme namiesto operátora && použili &, program by prestal fungovať. Je to preto, že operátor & vypočítava výsledok po jednotlivých bitoch a nepozerá sa na svoje argumenty ako na jeden celok tvoriaci logickú hodnotu. V tomto prípade by teda došlo k bitovému logickému súčinu (AND) medzi hodnotami 3 a 4. Ako ukazuje nasledujúci obrázok, výsledok bude v tom prípade 0:

x       00000011     (dvojkový zápis hodnoty 3)
y       00000100     (dvojkový zápis hodnoty 4)
        --------
x & y   00000000     (výsledok 3 & 4 - AND po bitoch)
Výsledok (x && y) však bude 1 podľa očakávania, lebo premenné x a y preň vyjadrujú pravdivostnú hodnotu v štýle pravdivý/nepravdivý. Pripomeňme si význam jednotlivých logických operácií a uvedomme si ako ich môžeme využiť na manipuláciu s jednotlivými bitmi. V prípade riadenia hardvéru je to veľmi potrebné, keďže komunikácia s hardvérom je typicky riešená namapovaním rozličných riadiacich signálov do jednotlivých bitov registrov.

 A   B   |  A and B   A or B   not A   A xor B
---------+---------------------------------------
logický  |
operátor |  A && B    A || B    !A      ----         napr. 12 && 6 -> 1, 12 && 3 -> 1, 12 || 6 -> 1
jazyka C |
         |
bitový   |
operátor |  A & B     A | B     ~A     A ^ B          napr. 12 & 6 -> 4,  12 & 3 -> 0, 12 | 6 -> 14
jazyka C |
         |
 0   0   |    0         0        1       0
 0   1   |    0         1        1       1
 1   0   |    0         1        0       1
 1   1   |    1         1        0       0
a preto ak X je jednobitová hodnota (0 alebo 1), platí:

  X & 0  -> 0       // and s nulou = vynulovanie bitu
  X & 1  -> X       // and s jednotkou = zachovanie bitu

  X | 0  -> X       // or s nulou = zachovanie bitu
  X | 1  -> 1       // or s jednotkou = nastavenie bitu

  X ^ 0  -> X       // xor s nulou = zachovanie bitu
  X ^ 1  -> ~X      // xor s jednotkou = flipnutie bitu
Čiže nasledujúce podmienky, resp. príkazy majú takýto skutočný význam:

  if (x & 1) ...     // ak je bit X nastavený, tak...

  x = x & 0;         // vynulovat bit

  x = x | 1;         // nastaviť bit na 1

  x = x ^ 1;         // zinvertovať bit
Už vieme pracovať s jedným bitom, ale bity sú v registroch združené po 8, 16, prípadne 32 bitoch a niekedy potrebujeme zistiť, nastaviť, vynulovať, alebo invertovať hodnotu i-teho bitu v poradí. Vtedy sa nám hodia operátory bitového posunu vľavo (<<) a vpravo (>>). Keď už hovoríme o poradí bitov, zastavme sa trochu pri tom, ako sa toto poradie udáva.

Uvažujme číslo 42 v desiatkovej sústave a prepíšme ho do dvojkovej sústavy:

 (42)10 = (101010)2
Desiatková aj dvojková sústava sú pozičné sústavy a preto platí:

   (42)10 = 4.101 + 2.100
   (101010)2 = 1.25 + 0.24 + 1.23 + 0.22 + 1.21 + 0.20 
Vidíme, že posledný bit v dvojkovom zápise má rád jednotiek (20), predposledný rád dvojek (21), potom rád 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, ... (každý ostrieľaný informatik pozná túto postupnosť aspoň po 2^16 spamäti...).
Preto sa posledný bit v dvojkovom zápise čísla označuje ako 0-tý, predposledný ako prvý, atď. A tiež posledný bit (celkom vpravo) sa niekedy označuje ako najmenej významný (least significant) a prvý bit sa označuje ako najvýznamnejší (most significant). Toto označenie sa používa aj pri skladaní dvoch bajtov do jedného 16-bitového slova: najvýznamnejší bajt (most significant byte = MSB) a najmenej významný bajt (least significant byte = LSB). Nebuďte prekvapení, keď sa so skratkami MSB/LSB stretnete v technických referenčných manuáloch k hardvérovým zariadeniam (tzv. datasheet).

Všimnime si teraz, čo sa stane, ak všetky bity nejakého čísla X posunieme o jeden bit vľavo (pri posune sa posledný bit dopĺňa 0):

   int x = 42;
   x = x << 1;

   // teraz X vyzerá takto: (1010100)2 = 1.26 + 0.25 + 1.24 + 0.23 + 1.22 + 0.21 = 2.(42)10
Z každého člena sme vyňali 2. Bitový posun o 1 bit vľavo teda znamená vynásobenie 2, bitový posun o 5 bitov vľavo bude znamenať... ...vynásobenie číslom 2^5 = 32. Podobne bitový posun vpravo o 1, 2, 3... bity zodpovedá deleniu číslom 2, 4, 8, ... hoci sa pritom posledné bity (tvoriacie zvyšok po delení) stratia/odrežú sa.

Po tejto príprave nám už nerobí problém zapísať príkazy, ktoré zistia/nastavia/vynulujú/invertujú i-ty bit v zadanom čísle x, pripomíname, že jazyk C umožňuje skrátený zápis, napr. x |= 3 znamená x = x | 3.

  x |= (1 << i);    // nastaví i-ty bit na 1 a ostatné bity nezmení (bity číslujeme sprava a od 0)
  x &= ~(1 << i);   // nastaví i-ty bit na 0 a ostatné bity nezmení (bity číslujeme sprava a od 0)
  x ^= (1 << i);    // invertuje i-ty bit a ostatné bity nezmení (bity číslujeme sprava a od 0)

  printf("%d-ty bit v %d je: %d\n", i, x, (x >> i) & 1);  // vypíše 0 alebo 1
  if (x & (1 << i)) ...   // ak nám nezáleží, že výsledok nie je 0/1, môžeme použiť aj toto
Pri práci s bitovými operáciami je lepšie používať celočíselné typy unsigned, pretože bežné číselné typy umožňujú ukladanie záporných čísel a tie sa vyznačujú tým, že najvyšší bit majú nastavený na 1 a preto bitový posun vpravo - ktorý bežne do najľavejšieho bitu umiestňuje 0 tam v prípade záporných čísel umiestňuje 1. Keď už sme týmto zablúdili do témy záporných čísel, tak si uvedomme, ako sú v počítači záporné čísla reprezentované.

Na prvý pohľad najjednoduchším spôsobom ukladania záporných čísel do 8- 16- 32- atď bitových registrov by bolo obetovať jeden - napríklad najvýznamnejší - bit na znamienko a inak čísla ukladať rovnako. Čiže napríklad pre 8-bitové registre, ak (5)10 = (00000101)2, tak (-5)10 by mohlo byť (10000101)2. Potom, ak by sme použili bežné pozičné sčítanie, ktoré funguje na kladných číslach, dostaneme čudné výsledky:

   00000101                                 00000101
 + 00000101                               + 10000101
 ----------                               ---------- 
   00001010  (5 + 5 = 10, to je ok)         10001010  (5 + (-5) = -10, čo už nie je veľmi ok)

alebo

   00000101
 + 10000100
 ----------
   10001001  (5 + (-4) = -9, to je tiež poriadna galiba)
Našťastie existuje iný spôsob zápisu čísel, ktorý tento problém rieši. Hľadáme také X, aby X + (-X) = 0. Napríklad:

   00000001
 + ????????
 ----------
   00000000
spätným odvodením od posledného bitu (čo musíme dosadiť za posledný ?, aby sme dostali vo výsledku 0? no predsa 1..., čo musíme dosadiť za predposledný ?...atď.) dostaneme:

   00000001
 + 11111111
 ----------
   00000000    (skutočný výsledok je 100000000, ale register má len 8 bitov a preto 8. bit 
		sprava bude zahodený, dojde síce k pretečeniu a v registri príznakov (flags) 
             procesora sa nastaví bit pretečenia, ale výsledok bude taký, ako potrebujeme.)
čiže -1 bude reprezentovaná číslom, ktoré má v dvojkovom zápise samé jednotky, v prípade 8-bitových registrov je to hodnota 255.

Vidíme, že pre ľubovoľné x bude platiť x + (-x) = 2^N, kde N je rád bitu, ktorý sa už do registra nevôjde, v tomto prípade N=8, čiže (-x) budeme reprezentovať ako 256-x. Hodnoty 0..127 teda budú zodpovedať kladným číslam 0..127 a hodnoty 128..255 budú zodpovedať záporným číslam -128..-1. Záporných a nezáporných čísel je teda rovnako veľa (128), ale medzi nezápornými je aj nula, takže takáto reprezentácia dokáže uložiť o 1 viac záporných čísel ako kladných: rozsah je -128..127. Podobne pre 16-bitové znamienkové čísla (v jazyku C väčšinou typ short) je rozsah -32768..32767.

V domácej úlohe si precvičíme prácu s bitovými i ostatnými operátormi, s cyklami, premennými a celočíselnými typmi. Veľa úspechov, v prípade nejasností alebo odhalených problémov v testoch nám napíšte mail, určite sa potešíme!
Ak vás téma bitových operácií zaujala, pozrite si túto skvelú stránku: Bit Twiddling Hacks od Seana Andersona zo Stanfordu.

pokračovanie...