Strukture podataka i algoritmi 1

SPA1 - Vežbe 3

Bitovske operacije

Prioriteti operatora

Uobičajeni logički operatori u programskom jeziku (&&, ||, ^^ i !) operišu nad celobrojnim promenljivama i uzimaju u obzir vrednosti operanada u celosti, pri čemu se vrednost 0 tumači kao “netačno”, a bilo koja vrednost različita od 0 (ne samo 1), tumači se kao “tačno”, i pri tom nije moguće pristupati pojedinačnim bitovima.

U većini uobičajenih situacija, pristup pojedinačnim bitovima nije neophodan, međutim, postoje i situacije u kojima pristup bitovima može da bude jako koristan (npr. shift operator je brži od množenja i deljenja).

U programskom jeziku C, pristup pojedinačnim bitovima pri obavljanju logičkih operacija postiže se upotrebom specijalizovanih operatora:

Bitovsko AND (&)

Bitovski operator konjunkcije (bitovsko AND) operiše nad dve celobrojne vrednosti, pristupajući nezavisno parovima bitova na istoj poziciji u obe promenljive, pri čemu se (na svakoj pojedinačnoj poziciji) primenjuje tablica istinosti.

Tablica istinitosti za bitovski operator konjunkcije (AND), prikazana je ispod:

a b a & b
0 0 0
0 1 0
1 0 0
1 1 1

U opštem smislu, rezultat je ‘tačno’, samo ako su oba uslova tačna. U slučaju operatora &, rezultat je 1 ako oba bita imaju vrednost 1.

Primer 1

Kada se bitovski operator & upotrebi između dve osmobitne celobrojne promenljive (brojevi 157 i 171), dobija se sledeći rezultat:

  1 0 0 1 1 1 0 1
& 1 0 1 0 1 0 1 1
= 1 0 0 0 1 0 0 1

Kada prevedemo u dekadni sistem, kao celobrojnu vrednost dobijamo 137.

Napomena: Celobrojne vrednosti su tipično 32-bitne, ali ćemo u primerima koristiti 8-bitne zbog preglednosti.

Bitovsko OR (|)

Bitovski operator disjunkcije | (bitovsko OR), takođe je binarni operator koji funkcioniše na sličan način kao AND, samo koristeći sledeću tablicu istinitosti:

a b a | b
0 0 0
0 1 1
1 0 1
1 1 1

U opštem smislu, rezultat je ‘tačno’, ako je bar jedan od uslova tačan. U slučaju operatora |, rezultat je 1 ako bar jedan bit ima vrednost 1.

Primer 2

Kada se bitovski operator | upotrebi između dve osmobitne celobrojne promenljive (brojevi 157 i 171), dobija se sledeći rezultat:

  1 0 0 1 1 1 0 1
| 1 0 1 0 1 0 1 1
= 1 0 1 1 1 1 1 1

Kada prevedemo u dekadni sistem, kao celobrojnu vrednost dobijamo 191.

Bitovsko XOR (^)

Bitovski operator isključive disjunkcije ^ (bitovsko XOR) je binarni operator koji koristi sledeću tablicu istinitosti:

a b a ^ b
0 0 0
0 1 1
1 0 1
1 1 0

U opštem smislu, rezultat je ‘tačno’, onda kada je samo jedan od dva uslova tačan (ukoliko dva uslova sadrže različite istinitosne vrednosti). U slučaju bitovske ekskluzivne disjunkcije, rezultat je 1 ukoliko par bitova sadrži jednu nulu i jednu jedinicu (ukoliko su bitovi različiti).

Primer 3

Kada se bitovski operator ^ upotrebi između dve osmobitne celobrojne promenljive (brojevi 157 i 171), dobija se sledeći rezultat:

  1 0 0 1 1 1 0 1
^ 1 0 1 0 1 0 1 1
= 0 0 1 1 0 1 1 0

Kada prevedemo u dekadni sistem, kao celobrojnu vrednost dobijamo 54.

Bitovsko NOT (~)

Bitovski operator negacije (bitovsko NOT) je, za razliku od prethodnih, unarni operator - operiše nad jednom promenljivom. Tablica istinitosti izgleda ovako:

a ~a
0 1
1 0

U opštem smislu, vrednost se invertuje - ukoliko je uslov prethodno imao vrednost “netačno”, dobija vrednost “tačno”, u suprotnom, dobija vrednost “netačno”. U slučaju bitovske negacije, bit se invertuje - ukoliko je bit prethodno imao vrednost 0, dobija vrednost 1, u suprotnom, dobija vrednost 0.

Primer 4

Kada se bitovski operator ~ upotrebi nad celobrojnom promenljivom (broju 171), dobija se sledeći rezultat:

~ 1 0 1 0 1 0 1 1
= 0 1 0 1 0 1 0 0

Kada prevedemo u dekadni sistem, kao celobrojnu vrednost dobijamo 84.

Shift left («)

Operator << (pomeranje ulevo) je binarni bitovski operator preko koga se, svi bitovi celobrojne promenljive, pomeraju određeni broj mesta ulevo.

U naredbi a << n, svi bitovi promenljive a pomeraju se za n mesta ulevo, pri čemu važe sledeća pravila:

Upotrebom operatora <<, određena vrednost lako se može pomnožiti nekim od stepena broja dva (vrednostima kao što su 2, 4 … 64, 128 … 512 i sl).

Primer 5

Ukoliko promenljiva a na početku ima vrednost 1, posle operacije a << 2, imaće vrednost 4.

  0 0 0 0 0 0 0 1
« 0 0 0 0 0 0 1 0
= 0 0 0 0 0 1 0 0

Primer 6

Upotrebom a << 1 na 8-bitnoj promenljivoj 128, dobiće se vrednost 0, jer će se jednim pomeranjem bita u levo prvi bit zanemariti, a sa desne strane će se dodati još jedna 0.

  1 0 0 0 0 0 0 0
« 0 0 0 0 0 0 0 1
= 0 0 0 0 0 0 0 0

Primer 7

Kada se bitovski operator << upotrebi nad celobrojnim promenljivama (brojevima 171 i 2, tj. pomeri bitove za 2 mesta ulevo u celobrojnoj promenljivoj 171), dobija se sledeći rezultat:

  1 0 1 0 1 0 1 1
« 0 0 0 0 0 0 1 0
= 1 0 1 0 1 1 0 0

Kada prevedemo u dekadni sistem, kao celobrojnu vrednost dobijamo 172.

Shift right (»)

Operator >> (pomeranje udesno) je binarni bitovski operator preko koga se, svi bitovi celobrojne promenljive, pomeraju određeni broj mesta udesno.

U naredbi a >> n, svi bitovi promenljive a pomeraju se za n mesta udesno, pri čemu važe sledeća pravila:

Pri upotrebi operatora pomeranja bitova udesno, takođe se mora uvek voditi računa o jedinicama sa (ovoga puta) desne strane.

Međutim, ukoliko se operator » koristi kao mehanizam za “brzinsko deljenje” nekim od stepena dvojke, jasno je da je u pitanju celobrojno deljenje bez ostatka, ali, takođe je jasno (shodno svemu što smo prethodno naveli), da će rezultat uvek biti korektan.

Primer 8

Ukoliko promenljiva a na početku ima vrednost 8, posle operacije a >> 2, imaće vrednost 2.

  0 0 0 0 1 0 0 0
» 0 0 0 0 0 0 1 0
= 0 0 0 0 0 0 1 0

Primer 9

Kada se bitovski operator >> upotrebi nad celobrojnim promenljivama (brojevima 171 i 2, tj. pomeri bitove za 2 mesta udesno u celobrojnoj promenljivoj 171), dobija se sledeći rezultat:

  1 0 1 0 1 0 1 1
» 0 0 0 0 0 0 1 0
= 0 0 1 0 1 0 1 0

Kada prevedemo u dekadni sistem, kao celobrojnu vrednost dobijamo 42.

Maskiranje bita

Operacija koja se popularno naziva “maskiranje bit(ov)a”, podrazumeva (tipično, ali ne i uvek), upotrebu pomoćne promenljive koja ima isključene sve bitove, i jedan uključen bit - na poziciji na kojoj je, u glavnoj promenljivoj, potrebno očitati vrednost bita ili obaviti neku drugu operaciju.

Uključivanje određenog bita (u pomoćnoj promenljivoj), najlakše se izvodi tako što se prvo uključi samo prvi bit (m = 1), posle čega se prvi bit, preko operatora pomeranja ulevo m = m << (p - 1);, postavlja na poziciju p.

m 0 0 0 0 0 0 0 1
p               4
m « (p - 1) 0 0 0 0 1 0 0 0

Uključivanje bita

Za uključivanje određenog bita (odnosno, za zadavanje vrednosti 1 određenom bitu), potrebno je prvo "maskirati" poziciju i potom pozvati bitovski operator disjunkcije (bitovsko OR).

Svi bitovi, osim “maskiranog” bita, zadržaće svoje vrednosti, dok će maskirani bit posle izvršavanja operacije, obavezno imati vrednost 1.

m 0 0 0 0 0 0 0 1
p               4
m « (p - 1) 0 0 0 0 1 0 0 0

U tabeli iznad prikazano je generisanje maske m.

a 1 1 0 1 0 1 0 1
m 0 0 0 0 1 0 0 0
a = a | m 1 1 0 1 1 1 0 1

Bitovski operator | ostaviće sve bitove, osim maskiranog, u prvobitnom stanju, a maskirani će uključiti (imaće vrednost 1).

Isključivanje bita

Za isključivanje određenog bita (postavljanje vrednosti određenog bita na 0), prvo je potrebno napraviti standardnu masku (kao i za uključivanje bita), a zatim je invertovati i pozvati bitovski operator konjunkcije (bitovsko AND).

m 0 0 0 0 0 0 0 1
p               4
m « (p - 1) 0 0 0 0 1 0 0 0

Generisanje maske m.

a 1 1 0 1 1 1 0 1
~m 1 1 1 1 0 1 1 1
a = a & ~m 1 1 0 1 0 1 0 1

Upotrebom invertovane maske (i operatora bitovske konjunkcije), postižemo da svi uključeni bitovi ostanu uključeni, dok će prvobitno uključeni bit na poziciji p, na kraju biti isključen.

Vrednost pojedinačnog bita

Očitavanje vrednosti bita na određenoj poziciji je najopštija od svih operacija koje se mogu izvoditi nad pojedinačnim bitovima. Tipično se sprovodi postupak kojim se traženi bit pomera na prvu poziciju, i potom se očitava vrednost prvog bita (ili, u praktičnom smislu - vrednost traženog bita).

Ako je potrebno očitati 4. bit sa desne strane u promenljivoj a, prvo je potrebno dovesti četvrti bit promenljive a na prvu poziciju, preko operatora >>:

a 1 1 1 0 1 0 0 1
p               4
x = a » (p - 1) 0 0 0 1 1 1 0 1

Zatim, uz korišćenje bitovskog operatora konjunkcije (&), rezultat se svodi na 0 ili 1 (i pamti se preko dodatne promenljive).

x 0 0 0 1 1 1 0 1
1 0 0 0 0 0 0 0 1
r = x & 1 0 0 0 0 0 0 0 1

U C programskom jeziku, očitavanje vrednosti pojedinačnog bita rešeno je sledećom linijom: r = a >> (p - 1) & 1;

Invertovanje vrednosti bita

Invertovanje vrednosti pojedinačnog bita je jedna od najjednostavnijih bitovskih operacija. Iako deluje logično, invertovanje pojedinačnog bita ne može se rešiti koriščenjem operatora ~. Kako bismo izolovali pojedinačan bit, kreiraćemo masku, a potom vrednost invertovati korišćenjem operatora ^ (XOR).

m 0 0 0 0 0 0 0 1
p               4
m « (p - 1) 0 0 0 0 1 0 0 0

Generisanje maske m.

a 0 0 0 1 1 1 0 1
m 0 0 0 0 1 0 0 0
a = a ^ m 0 0 0 1 0 1 0 1

Primenom operatora XOR (a = a ^ m) invertovaćemo odabrani bit.

Zadavanje formata

Mnoge ulazno izlazne funkcije u jeziku C (najčešće korišćene printf i scanf), koriste format string da bi se definisao način ispisa ili očekivani format unosa podataka u obliku karaktera (teksta). Neki sa kojima smo se već susretali su:

Ulaz i izlaz moguće je formatirati i prema osnovi brojevnog sistema koji želimo da koristimo. Npr, %d je podrazumevano u dekadnom sistemu, tj. u sistemu sa osnovom 10.

Za oktalni sistem (sa osnovom 8) koristi se %o, dok se za heksadekadni (sa osnovom 16) koristi %x.

#include <stdio.h>

int main() {

    printf("%d %o %x", 25, 25, 25);

    return 0;
}

Rezultat ovog koda biće 25 31 19, zbog različitih osnova.

Sizeof()

Sizeof() je unarni operator koji nam služi da preračuna veličinu datog operanda (tipa podatka ili promenljive).

Sintaksa: sizeof(operand);

U slučaju tipa podatka, vraća količinu alocirane memorije za taj specifični tip.

#include <stdio.h>
int main()
{
    printf("%lu\n", sizeof(char));
    printf("%lu\n", sizeof(int));
    printf("%lu\n", sizeof(float));
    printf("%lu", sizeof(double));
    return 0;
}

Ako kod pokrenemo na 32-bitnom gcc kompajleru (vrednosti mogu da variraju u zavisnosti od kompajlera), dobićemo ispis:

1
4
4
8

Može da se koristiti i sa izrazima:

int main()
{
    int a = 0;
    double d = 10.21;
    printf("%lu", sizeof(a + d));
    return 0;
}

Rezultat sabiranja int i double vrednosti biće double, pa će ispis biti 8.

Napomena: %lu se koristi za long integer vrednosti.

Sizeof je koristan za preračunavanje broja elemenata niza:

#include <stdio.h>
int main()
{
    int arr[] = { 1, 2, 3, 4, 7, 98, 0, 12, 35, 99, 14 };
    printf("%lu ", sizeof(arr) / sizeof(arr[0]));
    return 0;
}

Deljenjem ukupne veličine niza veličinom tipa elemenata niza dobijamo broj elemenata niza, u ovom slučaju 11.

Pored toga, veoma je važan za dinamičku alokaciju memorije, o čemu će biti reči u narednim terminima.

Const

Kvalifikator const se koristi pri deklaraciji varijable kako bi se naglasilo da se vrednost te promenljive neće menjati (da je konstanta). Konstanta jednom dobija svoju vrednost i više se ne može menjati.

int main()
{
    const int var = 100;
    var += 10; //javlja se greška pri kompajliranju (read-only variable)

    return 0;
}

Math.h

Math.h je matematička biblioteka u C programskom jeziku. Kako bismo mogli da je koristimo, potrebno je da je uključimo u kod pomoću #include <math.h>.

Neke od osnovnih funkcija ove biblioteke su:

Kompajliranje sa ovom bibliotekom vrši se komadom gcc -o izv primer.c -lm.

This site is open source. Improve this page.