>> Inapoi <<
========
Capitolul 7
========
=========================================
Tipurile enumerare, "typedef", si operatori pentru biti
=========================================
--------------------------
Tipurile enumerare
-------------------------
Pentru declararea tipurilor enumerare se foloseste cuvantul rezervat "enum".
Acesta va implica denumirea multimii, enumerarea elementelor (numite
enumeratori), ca elemente ale multimii.
-----------
Exemplu:
-----------
enum zile {luni, marti, miercuri, joi, vineri, sambata, duminica};
Aceasta declaratie creeaza tipul utilizator "enum zile". Cuvantul rezervat
"enum" este urmat de identificatorul "zile". Enumeratorii sunt identificatorii
luni, marti, ... . Acestea sunt constante de tip "int". Prin conventie, primul
este 0, si apoi restul sunt incrementati. Declararea variabilelor de tip
"enum zile" se face astfel:
enum zile zi1, zi2;
Variabilele "zi1" si "zi2" pot lua ca valori elemente ale acestui tip.
De exemplu,
zi1 = miercuri;
va asigna variabilei "zi1" valoarea miercuri. Instructiunea
if (zi1 == zi2)
{
...
}
va testa daca valoarea variabilei "zi1" este egala cu valoarea variabilei "zi2".
Enumeratorii pot fi initializati. De asemeni, putem declara variabilele in
timpul definirii tipului "enum".
-----------
Exemplu:
-----------
enum carti {trefla = 1, caro, frunza, inima} a, b, c;
Din moment ce "trefla" este initializata cu 1, rezulta ca "caro", "frunza" si
"inima" sunt initializate cu 2, 3, respectiv 4.
-----------
Exemplu:
-----------
enum fructe {mere = 7, pere, portocale = 3, lamai} nr_frct;
Este clar ca "pere" va fi initializat cu 8, iar "lamai" cu 4.
Numele tipului enumerare poate lipsi, insa atunci nu mai putem declara alte
variabile de acel tip.
-----------
Exemplu:
-----------
enum {plop, molid, brad} copaci;
Singura variabila de tip "enum {plop, molid, brad}" este copaci (nu se mai
poate declara alta).
-----------------------------
Folosirea lui "typedef"
-----------------------------
C pune la dispozitie facilitatea "typedef" pentru redenumirea tipurilor deja
existente.
-----------
Exemplu: typedef int culoare;
----------- culoare rosu, verde, albastru;
Acesta defineste tipul "culoare" ca fiind un sinonim al lui "int". Apoi
declaram trei variabile de tipul "culoare".
-----------
Exemplu:
-----------
Vom ilustra folosirea lui "typedef" pentru un tip enumerare (creand o functie
ce returneaza ziua urmatoare).
enum zile {duminica, luni, marti, miercuri, joi, vineri, sambata};
typedef enum zile zi;
zi gaseste_ziua_urmatoare(zi z)
{
zi ziua_urmatoare;
switch(z)
{
case duminica:
ziua_urmatoare = luni;
break;
case luni:
ziua_urmatoare = marti;
break;
...
case sambata:
ziua_urmatoare = duminica;
break;
}
return ziua_urmatoare;
}
O alta versiune (mai succinta) folosind "cast" este:
enum zile {duminica, luni, marti, miercuri, joi, vineri, sambata};
typedef enum zile zi;
zi gaseste_urmatoarea_zi(zi z)
{
return ((zi)(((int) z + 1) % 7));
}
-----------------------------------
Expresii si operatori pe biti
-----------------------------------
Operatorii pe biti lucreaza cu expresii integrale reprezentate ca siruri de
cifre binare. Acesti operatori sunt dependenti de sistem.
Operatorii pe biti sunt:
Operatori logici
--------------------
1. Complement pe bit (unar): ~
2. Si pe bit : &
3. Sau exclusiv pe bit : ^
4. Sau inclusiv pe bit : |
Operatori de deplasare
--------------------------
1. Deplasare stanga : <<
2. Deplasare dreapta : >>
Ca si ceilalti operatori, operatorii pe biti au reguli de precedenta si
asociativitate care determina precis cum se evalueaza expresiile ce contin
astfel de operatori. Operatorul ~ este unar, restul operatorilor sunt binari
si lucreaza cu tipuri integrale.
-------------------------
Complement pe bit
-------------------------
Operatorul ~ se numeste operator de complement (sau operator de complement pe
bit). Acesta inverseaza reprezentarea sirului pe biti, adica 0 devine 1 si 1
devine 0.
-----------
Exemplu: Fie declaratia
-----------
int a = 5171;
Reprezentarea binara a lui a este:
00010100 00110011
Expresia ~a este:
11101011 11001100
Aceasta are valoarea intreaga
- 5172
-------------------------------
Complement fata de doi
-------------------------------
Reprezentarea complementului fata de doi a unui numar natural este un sir de
biti obtinut prin complementarierea scrierii lui n in baza 2. Considerand
complementul pe biti al lui n la care adunam 1, obtinem reprezentarea
complementului fata de doi a lui -n.
O masina care utilizeaza reprezentarea complementului fata de doi ca
reprezentare binara in memorie pentru valori integrale se numeste masina
complement fata de doi. Reprezentarile complement fata de doi ale lui 0 si -1
sunt speciale. Astfel valoarea 0 are toti bitii "off", pe cand valoarea -1 are
toti bitii "on". Numerele negative sunt caracterizate prin aceea ca au bitul
cel mai semnificativ 1. Pe masinile care utilizeaza complementul fata de doi,
hard-ul permite implementarea scaderii ca o adunare si un complement pe biti.
Operatia a - b este aceeasi cu a + (-b), unde -b se obtine considerand
complementul pe biti al lui b la care adunam 1.
---------------------------------------
Operatori logici binari pe biti
---------------------------------------
Cei trei operatori & (si), ^ (sau exclusiv) si | (sau inclusiv) sunt binari
si au operanzi integrali. Operanzii sunt operati bit cu bit. Tabelul de mai
jos contine semantica lor:
a b a & b a ^ b a | b
-----------------------------------------------
0 0 0 0 0
1 0 0 1 1
0 1 0 1 1
1 1 1 0 1
-----------
Exemplu: Presupunem ca avem declaratiile si initializarile
-----------
int a = 3333, b = 7777;
Expresie Reprezentare Valoare
-----------------------------------------------------------
a 00001101 00000101 3333
b 00011110 01100001 7777
a & b 00001100 00000001 3073
a ^ b 00010011 01100100 4964
a | b 00011111 01100101 8037
~(a | b) 11100000 10011010 -8038
(~a & ~b) 11100000 10011010 -8038
----------------------------------------------------------
----------------------------------------------------
Operatori de deplasare stanga si dreapta
----------------------------------------------------
Cei doi operanzi ai unui operator de deplasare trebuie sa fie expresii
integrale. Tipul returnat de expresie este dat de operandul din stanga. O
expresie de forma
expresie1 << expresie2
implica reprezentarea pe bit a lui "expresie1" sa fie deplasata catre stanga
cu un numar de pozitii specificat de "expresie2". In capatul din dreapta, vor
fi adaugate 0-uri.
-----------
Exemplu: char c = 'Z';
-----------
------------------------------------------------------------------------
Expresie Reprezentare Actiune
------------------------------------------------------------------------
c 01011010 nedeplasat
c << 1 10110100 deplasare la stanga cu 1
c << 4 10100000 deplasare la stanga cu 4
c << 15 00000000 deplasare la stanga cu 15
------------------------------------------------------------------------
Chiar daca valoarea lui "c" se memoreaza pe un octet, intr-o expresie aceasta
ia tipul "int". Deci valoarea expresiilor "c << 1", "c << 4" si "c << 15" se
memoreaza pe doi octeti.
Operatorul de deplasare la dreapta ">>" nu este chiar simetric cu "<<". Pentru
expresiile integrale fara semn, din stanga se va deplasa 0, iar pentru cele cu
semn 1.
-----------
Exemplu:
-----------
Presupunem ca avem declaratiile:
int a = 1 << 15;
unsigned b = 1 << 15;
---------------------------------------------------------------------------
Expresie Reprezentare Actiune
---------------------------------------------------------------------------
a 10000000 00000000 nedeplasat
a >> 3 11110000 00000000 deplasare la dreapta cu 3
b 10000000 00000000 nedeplasat
b >> 3 00010000 00000000 deplasare la dreapta cu 3
--------------------------------------------------------------------------
Ca valoare intreaga, a >> 3 este -4096, iar b >> 3 este 4096, lucru care este
in concordanta cu notiunea de numar negativ si pozitiv din matematica.
Daca operandul din dreapta a operatorului de deplasare este negativ sau are o
valoare care este egala sau depaseste numarul de biti folositi pentru
reprezentarea operandului din stanga, atunci comportarea este nedefinita.
Tabelul de mai jos ilustreaza regulile de precedenta (+ este mai prioritar) si
asociativitate (de la stanga la dreapta) referitoare la operatorii de deplasare.
-----------
Exemplu: Presupunem ca avem: unsigned a = 1, b = 2;
-----------
------------------------------------------------------------------------------
Expresie Expresie echivalenta Reprezentare Valoare
------------------------------------------------------------------------------
a << b >> 1 | (a << b) >> 1 | 00000000 00000010 2
a << 1 + 2 << 3 | (a << (1 + 2)) << 3 | 00000000 01000000 64
a + b << 12 * a >> b | ((a + b)<<(12 * a))>>b | 00001100 00000000 3072
------------------------------------------------------------------------------
--------
Masti
--------
O "masca" este o constanta sau variabila folosita pentru extragerea bitilor
doriti dintr-o alta variabila sau expresie. Din moment ce constanta "int" 1
are reprezentarea pe biti:
00000000 00000001
aceasta poate fi folosita pentru determinarea bitului cel mai nesemnificativ
dintr-o expresie "int". Codul de mai jos foloseste aceasta masca si tipareste
o secventa alternativa de 0 si 1:
int i, masca = 1;
for (i = 0; i < 10; ++ i)
printf("%d", i & masca);
Daca dorim sa gasim valoarea unui anume bit dintr-o expresie, putem folosi o
masca care este 1 in acea pozitie si 0 in rest.
-----------
Exemplu:
-----------
Putem folosi expresia 1 << 2 pentru a vedea al treilea bit (numarand de la
dreapta). Expresia
(v & (1 << 2)) ? 1 : 0
are valoarea 1 sau 0 dupa cum este al treilea bit din "v".
Alt exemplu de masca este valoarea constanta 255 (adica 2^8 -1). Ea are
reprezentarea
00000000 11111111
Deoarece doar octetul din dreapta este plasat pe "on", atunci expresia
v & 255
va intoarce o valoare ce are reprezentare pe biti cu toti bitii din octetul
din stanga "off" si cel din dreapta identic cu octetul din dreapta a lui "v".
Spunem ca 255 este o masca pentru octetul din dreapta.
-------------------------------------------------------------------------
Un program de impachetare si despachetare a cuvintelor
-------------------------------------------------------------------------
Stim ca un caracter se memoreaza pe un octet, pe cand un intreg pe doi octeti. Folosind operatorii de deplasare, putem comprima
doua caractere intr-un intreg.
#include
#include
#include
void bit_print(int a)
{
int i;
int n = sizeof(int) * CHAR_BIT;
int masca = 1 << (n-1);
for (i = 1; i <= n; ++i)
{
putchar(((a & masca) == 0) ? '0' : '1');
a <<= 1;
if (i % CHAR_BIT == 0 && i < n)
putchar(' ');
}
}
int pack(char a, char b)
{
int p = a;
p = (p << CHAR_BIT) | b;
return p;
}
char unpack(int p, int k) /* k = 0, 1 */
{
int n = k * CHAR_BIT; /* n = 0, 8 */
unsigned masca = 255;
masca <<= n;
return((p & masca) >> n);
}
void main()
{
clrscr();
bit_print(65);
printf("\nab = ");
bit_print(pack('a', 'b'));
putchar('\n');
getch();
printf("Numarul 24930 este impachetarea caracterelor %c si %c",
unpack(24930,1), unpack(24930,0));
getch();
}
--------------------------------
Litere mari -> litere mici
--------------------------------
Reluam un exemplu dintr-un capitol precedent si anume transformarea literelor
mari in mici folosind operatori de deplasare.
#include
#include
#include
void main()
{
clrscr();
int c;
while ((c = getchar()) != EOF)
{
if (isupper(c)) // sau (c>='A' && c<='Z')
putchar(c | (1 << 5));
else
putchar(c);
}
}
-----------------
Recapitulare
-----------------
In cele ce urmeaza, vom preciza cum se calculeaza valoarea unui numar pozitiv,
respectiv negativ (in memoria calculatorului).
Fie declaratia
int a;
Consideram reprezentarea sa in baza 2
____________________________________________________________
|______|______|______________|___| |___|___|____________|___|
b_{16} b_{15} . . . . . . . b_9 b_8 b_7 . . . . b_1
Daca b_{16} = 0 atunci
a = suma_{j=1}^{15} b_j*2^j
altfel
consideram reprezentarea in baza 2 a complementului lui a (~a)
__________________________________________________________________
|_______|______|____________|____| |____|____|_______________|____|
b'_{16} b'_{15} . . . . . b'_9 b'_8 b'_7 . . . . b'_1
unde b'_j = 1 - b_j;
~a = suma_{j=1}^{15} b'_j*2^j;
-a = ~a + 1;
a = -(~a + 1);
sfarsit.
-----------------------------------------------
Exercitii propuse spre implementare
-----------------------------------------------
1. (Jocul hartie, pumn, farfece)
Presupunem ca avem doi jucatori care folosesc mana dreapta pentru reprezentarea
a trei obiecte:
hartie = palma intinsa
pumn = mana stransa sub forma de pumn
foarfece = doua degete departate (semnul Victoriei)
Ei isi arata simultan mana dreapta in una din aceste configuratii (de mai multe
ori). Daca ei arata acelasi lucru, este remiza (nu castiga nimeni). Daca nu se
aplica una din urmatoarele trei reguli:
a) Hartia acopera pumnul. (deci palma intinsa castiga fata de pumn)
b) Pumnul sparge foarfecele.
c) Foarfecele taie hartia.
Sa se simuleze acest joc, facand un numar arbitrar de evenimente precizand
scorul final. Se cere sa se joace persoana-calculator, si varianta a doua
calculator-calculator.
2. O ruleta este o masina care selecteaza la intamplare un numar intre 0 si 35
la intamplare. Jucatorul poate paria pe un numar par/impar sau poate paria pe
un numar oarecare. Castigul unui pariu par/impar se premiaza cu 2/1 dolari, cu
exceptia celor in care ruleta alege 0. Daca jucatorul "prinde" numarul selectat
de ruleta, atunci este platit cu 35 ... 1 dolari. Intrebare: Considerand ca
jucam pariuri de 1 dolar, cate parieri trebuie sa facem astfel incat sa pierdem
10 dolari ?
3. Folosind functia "bit_print" construiti un tabel (cu trei coloane) care sa
contina n, reprezentarea binara a lui 2^n, reprezentarea binara a lui 2^n-1,
pentru n = 0, 1, 2, ..., 32. Apoi, afisati un tabel (tot cu trei coloane) care
sa contina n, 10^n si 10^n-1 pentru n = 0, 1, 2, ..., 7 (in baza zece). Ce
asemanare observati ?
4. Zilele secolului 20 pot fi notate folosind intregi in forma "zi/luna/an".
De exemplu, 1/7/93 inseamna 1 iulie 1993. Scrieti o functie care memoreaza
ziua, luna si anul compact, astfel:
a) pentru zile (maxim 31) sunt suficienti 5 biti;
b) pentru luna (12) sunt suficienti 4 biti;
c) pentru ani (100) sunt suficienti 7 biti;
Functia trebuie sa aiba la intrare ziua, luna si anul ca intregi si trebuie sa
returneze data "impachetata" pe un "intreg" pe 16 biti.
Scrieti inca o functie care face "despachetarea".
5. Folosind operatori pe biti, scrieti programe C care:
a) testeaza daca un numar de tip "int" sau "long" este divizibil cu
8. Generalizare (divizibilitate cu 2^n);
b) testeaza daca un numar este pozitiv sau negativ;
c) calculeaza pentru un n dat, multiplii de 2, 4, ... Generalizare;
d) calculeaza pentru un n dat, [n/2], [n/4], ... Generalizare;
e) calculeaza m^n, folosind reprezentarea in baza 2 a lui n si
metoda "divide et impera" (vezi exercitiul 2 din capitolul 6).
6. Sa se calculeze suma cifrelor unui numar cu n cifre.