Articole

Operațiile de citire și afișare se realizează de cele mai multe ori aplicându-se niște reguli standard ale limbajului C++, acest lucru fiind de regulă suficient. De exemplu, valorile întregi se afișează în baza 10, valorile reale se afișează de regulă cu 6 cifre (în fața și în spatele punctului zecimal), etc. Uneori este necesar să formatăm mai precis afișările și citirile, aceasta fiind tema prezentului articol.

Introducere

Formatarea citirii și afișării se face prin intermediul unor funcții speciale, numite manipulatori. O parte dintre ele se află în fișierele header fstream și iostream (probabil deja incluse), altele se află în fișierul header iomanip – care trebuie și el inclus.

Afișarea poate fi formatată precizându-se:

• lungimea – setw(int n): numărul n de caractere care vor fi utilizate pentru afișarea valorii dorite – implicit este variabil și egal cu numărul de caractere necesar. Modificând lungimea putem afișa date în format tabelar, distingându-se clar liniile și coloanele;
• alinierea – left, right, internal: în cazul în care valoarea afișată ocupă mai puține caractere decât lungimea, ea poate fi aliniată la dreapta (implicit) sau la stânga (pentru orice fel de date) sau internal, pentru date numerice (întregi sau reale);
• caracterul de umplere – setfill(char f): dacă valoarea afișată ocupă mai puține caractere decât lungimea, pe pozițiile nefolosite se vor scrie caractere de umplere – implicit spații;
• precizia – setprecision(int n): numărul n de cifre folosite pentru afișarea valorilor reale; în funcție de context, poate reprezenta numărul total de cifre sau numărul de cifre de după punctul zecimal
• baza de numerație (dec, oct, hex) în care sunt scrise valorile de tip întreg. Valorile întregi se pot scrie în baza 10 (implicit), baza 8 sau baza 16;
• formatul de afișare (fixed, scientific sau implicit) valorilor reale.

Citirea poate fi formatată precizându-se:

• baza de numerație (dec, oct, hex) în care se consideră valoarea întreagă introdusă. Se pot citi valori în bazele 10, 8 sau 16.
• modul de tratare a caracterelor albe – skipws, noskipws: implicit, la citire se sare peste eventualele caracterele albe aflate înainte de valoarea de citit (skipws). Dacă este setat modul noskipws și înainte de valoarea de citit există caractere albe, citirea va eșua.

Manipulatorii se folosesc ca operanzi în operația de inserare în stream (cout << ) sau extragere din stream (cin >>). Unii dintre ei au efect în mod direct, alții au efect numai în combinație cu alți manipulatori. Unii manipulatori au efect doar asupra următoarei date afișate, alții au efect pentru toate datele care sunt afișate în continuare.

Formatare afișării

Lungimea

Lungimea unei date afișate se referă la numărul de caractere folosite pentru afișarea acelei date. Implicit se folosesc atâtea caractere cât este necesar. De exemplu, pentru a afișa numărul 2019 se folosesc 4 caractere. Acest comportament poate fi modificat cu ajutorul manipulatorului setw(n), unde n reprezintă numărul de caractere folosite pentru afișare:

cout << "|" << 2019 << "|" << endl;
cout << "|" << setw(10) << 2019 << "|" << endl;

Când lungimea de afișare este specificată (și mai mare decât cea ocupată efectiv), data poate fi aliniată la stânga (left) sau la dreapta (right) zonei de afișare.

cout << "|" << setw(10) << 2019 << "|" << endl;
cout << "|" << setw(10) << left << 2019 << "|" << endl;
cout << "|" << setw(10) << right << 2019 << "|" << endl;

La afișarea valorilor numerice, se poate face o aliniere specială: semnul să fie aliniat la stânga, iar valoarea să fie aliniată la dreapta. Se va folosi manipulatorul internal:

cout << setw(10) << internal << -2019 << endl;
cout << setw(10) << internal << 2019 << endl;

Implicit, pentru valorile pozitive nu se afișează semnul. Acest lucru poate fi gestionat cu modificatorii showpos și noshowpos:

cout << setw(10) << internal << -2019 << endl;
cout << setw(10) << showpos << internal << 2019 << endl;

Dacă lungimea de afișare este mai mare decât lungimea datei afișate, caracterele suplimentare sunt implicit spații. Putem modifica acest caracter prin intermediul modificatorului setfill(char), de exemplu:

cout << setw(10) << setfill('#') << 2019 << endl;

Afișarea datelor întregi

Valorile întregi pot fi afișate (și citite) în baza 10 (decimal, dec), baza 8 (octal, oct) sau baza 16 (hexadecimal, hex):

int n = 2019;
cout << "implicit:    " << n << endl;
cout << "decimal:     " << dec << n << endl;
cout << "octal:       " << oct << n << endl;
cout << "hexadecimal: " << hex << n << endl;

Implicit, pentru valorile afișate în baza 8 și 16 nu se afișează prefixul care precizează baza (0, respectiv 0x). Aceasta poate fi gestionată cu manipulatorii showbase și noshowbase:

int n = 2019;
cout << "implicit:    " << n << endl;
cout << "decimal:     " << showbase << dec << n << endl;
cout << "octal:       " << oct << n << endl;
cout << "hexadecimal: " << hex << n << endl;

Manipulatorii uppercase și nouppercase stabilesc dacă prefixul (Ox, afișat cu showbase) precum și cifrele a, b, c, d, e, f pentru valorile în baza 16 este scris cu litere mari sau nu: 0X7E3 sau 0x7e3 – pentru valoarea zecimală 2019. Acești manipulatori controlează și modul de afișare în forma științifică a datelor reale.

Afișarea valorilor reale

Valorile reale sunt stocate folosind formatul cu virgulă mobilă, iar valoarea afișată este o aproximare a valorii memorate. Modul în care sunt afișate datele reale depinde de mai mulți factori: precizia, formatul de afișare (fix, științific sau implicit), etc.

Precizia reprezintă numărul de cifre folosite pentru afișare sau numărul de zecimale afișate. Precizia are implicit valoarea 6 și este în strânsă legătură cu formatul de afișare:

• formatul implicit afișează valoarea în forma fixă sau în forma științifică, în funcție de precizie. Fie n numărul de cifre ale părții întregi a valorii de afișat și fie p precizia curentă:
  • dacă n≤p, se va folosi formatul fix de afișare, iar pentru partea zecimală se vor afișa p-n zecimale, cu rotunjire
  • dacă n>p, se va folosi formatul științific de afișare, cu mantisă și caracteristică, iar precizia reprezintă numărul de cifre ale mantisei

double pi = atan(1) * 4; // PI
// afisare implicită, precizie implicită 6
cout << pi << endl;
// format implicit; precizie 7, 3 cifre la partea intreaga, 4 la partea fractionara
cout << setprecision(7) << 100 * pi << endl; 
// format implicit; precizie 7, 7 cifre la partea intreaga, 0 la partea fractionara
cout << setprecision(7) << 1000000 * pi << endl;
// format implicit; precizie 7, 8 cifre la partea intreaga; se afiseaza in format stiintific
cout << setprecision(7) << 10000000 * pi << endl; 

• dacă formatul de afișare precizat este formatul fix, prin intermediul manipulatorului fixed, precizia reprezintă numărul de cifre aflate după punctul zecimal:

double pi = atan(1) * 4; // PI

cout << fixed; // ATENTIE AICI!!
cout << right;
//format fix, precizie implicită 6, 6 cifre zecimale
cout << setw(19) << pi << endl;
// format fix; precizie 7, 7 cifre zecimale
cout << setw(20) << setprecision(7) << 100 * pi << endl; 
cout << setw(20) << setprecision(7) << 1000000 * pi << endl;
cout << setw(20) << setprecision(7) << 10000000 * pi << endl; 

• dacă formatul de afișare este cel științific, prin intermediul manipulatorului scientific, precizia reprezintă numărul de zecimale ale mantisei:

double pi = atan(1) * 4; // PI
cout << scientific; // ATENTIE AICI!!
cout << right;
//format fix, precizie implicită 6, 6 zecimale la mantisa
cout << setw(19) << pi << endl;
// format fix; precizie 7, 7 zecimale la mantisa
cout << setw(20) << setprecision(7) << 100 * pi << endl; 
cout << setw(20) << setprecision(7) << 1000000 * pi << endl;
cout << setw(20) << setprecision(7) << 10000000 * pi << endl; 

La afișarea în format implicit, datele de tip real care nu contin zecimale (au partea fracționară nulă, de exemplu 1.0) vor fi afișate fără zecimale și fără punctul zecimal. Acest comportament poate fi gestionat cu ajutorul manipulatorilor showpoint și noshowpoint.

Afișare valorilor de tip bool

Implicit, valorile de tip bool sunt afișate ca valori numerice. Mai precis:

cout << true << endl; // 1
cout << false << endl; // 0

Este însă posibil să se afișeze și literalii true sau false, cu ajutorul manipulatorilor boolalpha și noboolalpha:

cout << boolalpha << true << endl; // true
cout << false << endl; // false
cout << noboolalpha;
cout << true << endl; // 1
cout << false << endl; // 0

Formatarea citirii

Implicit la citire se sare peste caracterele albe aflate înaintea valorii care se citește. Mai precis:

char x,y,z;
cin >> x >> y >> z; // A B C
cout << x << y << z; //ABC

Dacă se introduce șirul A B C, variabila x va avea valoarea 'A', y va avea valoarea 'B', iar z va avea valoarea 'C'. Caracterele spațiu sunt sărite. Acest comportament este gestionat prin manipulatorii skipws și noskipws.

char x,y,z;
cin >> noskipws;
cin >> x >> y >> z; // A B C
cout << x << y << z; //A B

Dacă se introduce șirul A B C, variabila x va avea valoarea 'A', y va avea valoarea ' ', iar z va avea valoarea 'B'. Ultimele două caractere sunt ignorate (rămân în stream).

Dacă variabila citită nu poate memora spații (de exemplu este numerică) dar primele caractere sunt albe, citirea va eșua. Variabila va deveni 0 (începând cu C++11) și se va seta failbit, astfel că următoarele citiri nu vor mai avea loc.

int x = 10, y = 10;
cin >> noskipws;
cin >> x; // "   25"
cout << x << " " << y; // 0 10

La citirea variabilelor întregi se poate preciza baza în care sunt valorile așteptate prin manipulatorii dec, oct sau hex.

int x;
cin >> hex >> x; // ff
cout << x;  // 255

Fie G=(V,E) un graf neorientat conex:

• un nod al grafului se numește punct de articulație sau nod critic dacă subgraful obținut prin eliminarea lui nu este conex;
• o muchie se numește punte sau muchie critică dacă graful parțial obținut prin eliminarea ei nu este conex;
• un graf neorientat se numește biconex dacă nu conține puncte de articulație;
• se numește componentă biconexă un subgraf biconex maximal – prin adăugarea încă unui nod nu mai este biconex.

Exemplu:

Graful inițial	Puncte de articulație	Punți	Componente biconexe

Câteva observații:

• pentru fiecare muchie critică, cel puțin o extremitate este punct de articulație;
• fiecare punct de articulație face parte din cel puțin două componente biconexe;
• nodurile care fac parte dintr-un ciclu aparțin aceleiași componente biconexe;
• fiecare muchie critică reprezintă ea însăși o componentă biconexă;
• o muchie este critică dacă nu face parte dintr-un ciclu;

Pentru a determina punctele de articulație și punțile se poate folosi un algoritm naiv, bazat pe eliminarea succesivă a câte unui nod (muchie) și verificarea conexității. Complexitatea acestor algoritmi este O(n*C), respectiv O(m*C), unde O(C) este complexitatea algoritmului de verificarea a conexității (O(n*n) dacă reprezentăm graful prin matrice de adiacență, O(n+m) dacă reprezentăm graful prin liste de adiacențe).

În cele ce urmează vom prezentat un algoritm bazat pe parcurgerea în adâncime a grafului. Complexitatea sa este aceeași cu a parcurgerii în adâncime.

Considerăm G=(V,E) graful dat și A arborele de parcurgere în adâncime. Reamintim că muchiile graful pot fi doar:

• muchii de parcurgere, folosite la înaintarea în arbore
• muchii de întoarcere; o muchie (k,x) este de întoarcere dacă x este ascendent al lui k în arborele A – nodul x a fost descoperit anterior nodului k

Pentru graful de mai sus, arborele de parcurgere este următorul – muchiile de parcurgere sunt desenate cu linii continue, cele de întoarcere cu linii întrerupte.

Observăm următoarele:

• un nod k al grafului, diferit de rădăcina arborelui DFS, este punct de articulație dacă și numai dacă are un descendent direct x în arborele A cu proprietatea că de la niciun descendent al lui x sau de la x nu există muchie de întoarcere la niciun ascendent al lui k;
• rădăcina arborelui DFS este punct de articulație dacă și numai dacă are în acest arbore cel puțin doi descendenți direcți.

Pentru a determina punctele de articulație, punțile și componentele biconexe vom determina pentru fiecare nod k următoarele informații:

• nivel[k] – nivelul pe care se află nodul k în arborele DFS;
  • nivel[rădăcină] = 1;
  • nivel[k] = nivel[tata[k]] + 1;
• nma[k] – nivelul minim la care se poate ajunge din k, mergând numai pe muchii de arbore și folosind ca ultimă muchie o muchie de întoarcere. Îl vom numi nivelul minim accesibil și este egal cu minimul dintre următoarele 3 valori :
  • nivelul nodului curent
  • minimul dintre nivelurile nodurilor cu care este legat nodul curent printr-o muchie de întoarcere
  • minimul dintre nivelurile minime accesibile ale fiilor nodului curent din cadrul arborelui DFS

Pentru graful de mai sus aceste valori sunt următoarele:

k	1	2	3	4	5	6	7	8
nivel[k]	1	2	3	4	3	5	4	6
nma[k]	1	1	3	1	1	4	4	4

Cu ajutorul acestor valori, un nod k care nu este rădăcina arborelui este punct de articulație dacă și numai dacă are cel puțin un fiu x pentru care nivelul minim accesibil este mai mare sau egal cu nivelul nodului (nivel[k] <= nma[x]). Să analizăm nodurile:

• 1 nu este punct de articulație, deoarece este rădăcina arborelui și are un singur descendent direct
• 2 este punct de articulație, deoarece 3 este fiu al lui 2 și nivel[2] <= nma[3]
• 3 nu este punct de articulație, deoarece nu are niciun fiu
• 4 nu este punct de articulație, deoarece nu are niciun fiu
• 5 este punct de articulație deoarece 7 este fiu al lui 5 și nivel[5] <= nma[7]
• 6 nu este punct de articulație; pentru singurul fiu al lui 6, 8 relația este nivel[6] > nma[8]
• 7 este punct de articulație deoarece 6 este fiu al lui 7 și nivel[7] <= nma[6]
• 8 nu este punct de articulație deoarece nu are fii

Fie (k,x) o muchie de arbore, în care k este tatăl lui x. Această muchie este critică dacă și numai dacă (nivel[k] < nma[x]). Muchiile de întoarcere nu sunt niciodată muchii critice, deoarece aparțin întotdeauna unor cicluri.

Cele două șiruri de valori se construiesc în timpul parcurgerii DFS. Fie k nodul curent în parcurgerea DFS:

• stabilim nivel[k] = nivel[tata[k]] + 1 – această valoare va rămâne neschimbată până la final;
• inițializăm nma[k] = nivel[k]
• parcurgem nodurile adiacente cu k. Fie x un asemenea nod:
  • dacă x a fost deja parcurs și nu este tatăl lui k, muchia (k,x) este muchie de întoarcere. Dacă este cazul actualizăm nma[k] la valoarea nivel[x] (dacă nivel[x] este mai mic decât valoarea actuală a lui nma[k]);
  • dacă x nu a fost încă parcurs, continuăm parcurgerea din x – îl adăugăm pe stivă/apel recursiv. La eliminarea de pe stivă/ revenirea din autoapel, actualizăm valoarea nma[k] la valoarea nma[x] (dacă nma[k] este mai mare decât nma[x], acesta din urmă este calculat deja)

Următorul pseudocod descrie cum se calculează pentru fiecare nod al grafului nivelul și nivelul minim accesibil, folosind parcurgerea în adâncime:

subprogram DFS(k, tata)
    V[k] ← true
    nivel[k] ← nivel[tata] + 1
    nma[k] ← nivel[k]
    pentru x - nod adiacent cu k
        dacă x ≠ tata
            dacă V[x] = true atunci
                dacă nma[k] > nivel[x] atunci
                    nma[k] ← nivel[x]
                sf_dacă
            altfel
                DFS(x,k)
                dacă nma[k] > nma[x] atunci
                    nma[k] ← nma[x]
                sf_dacă

                // determinare puncte de articulație

                // determinare punți

                // determinare componente biconexe

            sf_dacă
        sf_dacă
    sf_pentru
sf_subprogram

Pentru a determina punctele de articulație:

• la eliminarea de pe stivă a nodului x (revenirea din autoapel) verificăm dacă acest și nodul părinte k verifică relația nivel[k] <= nma[x]; în caz afirmativ, decidem că nodul k este critic;
• pentru a stabili dacă rădăcina este punct de articulație trebuie să-i numărăm descendenții direcți în arbore.
• Observație: un punct de articulație poate fi descoperit de mai multe ori – dacă există mai mulți fii ai săi care respectă relația de mai sus.

//determinare puncte de articulație
dacă nivel[k] ≤ nma[x] și nod ≠ rădăcină atunci
    //nodul k este punct de articulație
sf_dacă

Pentru a determina punțile:

• la eliminare de pe stivă a nodului x/revenirea din autoapel vom determina muchiile de parcurgere (k,x) pentru care nivelul lui k este mai mic decât nivelul minim accesibil al lui x: nivel[k] < nma[x].

//determinare punți
dacă nivel[k] < nma[x] atunci
    //muchia (k,x) este punte
sf_dacă

Pentru a determina componentele biconexe:

• utilizăm o stivă suplimentară S, pe care adaugăm noduri la vizitarea lor conform parcurgerii și le eliminăm la determinarea unei componente biconexe;
  • ordinea nodurilor din stiva S este cea a parcurgerii în adâncime;
• dacă pentru nodul curent k avem un descendent direct x pentru care nivel[k] <= nma[x], vom elimina de pe stivă nodurile până la nodul x, inclusiv acesta;
  • nodurile eliminate, împreună cu nodul k reprezintă o componentă biconexă;
  • eliminarea se face până la x, nu până la k, deoarece între acestea, pe stivă, pot fi noduri din altă componentă biconexă.
• Observație: condiția nivel[k] <= nma[x] are loc întotdeauna pentru rădăcina arborelui DFS, chiar dacă acesta nu este punct de articulație. În acest caz se determină o componentă biconexă din care face rădăcina. Acest lucru se întâmplă și când graful dat este biconex: determinarea componentei biconexe se face la revenirea în rădăcină.

...
V[k] ← true
Adaugă(S,k)
....
//determinare componente biconexe
dacă nivel[x] ≤ nma[k] atunci
    câttimp Vârf(S) ≠ x execută
        Vârf(S) se adugă la componenta curentă
        Elimină(S)
    sf_câttimp
    x se adaugă la componenta curentă
    Elimină(S)
    k se adaugă la componenta curentă
sf_dacă

Teoreme fundamentală a aritmeticii:

Orice număr natural \(n\) mai mare decât \(1\) se poate scrie în mod unic sub forma \( n = p_{1}^{e_1} \cdot p_{2}^{e_2} \cdot … \cdot p_{k}^{e_k} \), unde \( p_1 < p_2 < … < p_k \) sunt numere prime, iar \( e_i > 0, i=1..k \)

V-ați întrebat de ce numărul \( 1 \) nu este prim? Dacă ar fi, teorema de mai sus ar fi falsă! Pentru numărul \(12\), ar fi valabile descompunerile:

• \( 12 = 2^2 \cdot 3\)
• \( 12 = 1 \cdot 2^2 \cdot 3\)
• \( 12 = 1^7 \cdot 2^2 \cdot 3\)
• ș.a.m.d.

Iată trei aplicații interesante ale descompunerii în factori primi. Lăsăm demonstrarea lor în sarcina cititorului!

Numărul de divizori

Numărul de divizori ai lui \(n\) poate fi determinat prin numărarea acestora: parcurgerea intervalului de divizori posibili și numărarea valorilor care sunt divizori ai lui \(n\).

O altă soluție este folosirea următoarei proprietăți.

Proprietate: Pentru un număr natural care are descompunerea în factori primi: \( n = p_{1}^{e_1} \cdot p_{2}^{e_2} \cdot … \cdot p_{k}^{e_k} \), numărul de divizori este: \( (e_1 + 1) \cdot (e_2 + 1) \cdot … \cdot (e_k + 1) \).

Exemplu: Fie \( n = 12\). Divizorii sunt \( 1, 2, 3, 4, 6, 12\) – 6 divizori.
Descompunerea în factori este: \( n = 12 = 2^2 \cdot 3^1 \).
Aplicând formula de mai sus obținem \( (2+1) \cdot (1+1) = 3 \cdot 2 = 6 \).

Suma divizorilor

Proprietate: Pentru un număr natural care are descompunerea în factori primi: \( n = p_{1}^{e_1} \cdot p_{2}^{e_2} \cdot … \cdot p_{k}^{e_k} \), suma divizorilor este: \( { {p_1^{e_1+1} -1 } \over {p_1 – 1} } \cdot { {p_2^{e_2+1} -1 } \over {p_2 – 1} } \cdot … \cdot { {p_k^{e_k+1} -1 } \over {p_k – 1} } \).

Exemplu: Fie \( n = 12\). Suma divizorilor este \(1 + 2 + 3 + 4 + 6 + 12 = 28\).
Descompunerea în factori este: \( n = 12 = 2^2 \cdot 3^1 \).
Aplicând formula de mai sus obținem \( { {2^{2+1} -1 } \over {2 – 1} } \cdot { {3^{1+1} -1 } \over {3 – 1} } = { {2^3 -1 } \over {1} } \cdot { {3^{2} -1 } \over {2} } = { {8 -1 } \over {1} } \cdot { {9 -1 } \over {2} } = { {7 } \over {1} } \cdot { {8 } \over {2} } = {7 } \cdot {4} = 28 \).

Indicatorul lui Euler

Indicatorul lui Euler sau funcția lui Euler, sau totient se notează cu \( \varphi(n) \) (unde \(n\) este un număr natural nenul ) și \( \varphi(n) \) reprezintă numărul de numere mai mici sau egale cu \(n\) și prime cu acesta.

Valoarea lui \( \varphi(n) \) poate fi determinată prin numărarea valorilor prime cu \(n\), sau putem aplica următoarea proprietate:

Proprietate: Pentru un număr natural \(n\) care are descompunerea în factori primi: \( n = p_{1}^{e_1} \cdot p_{2}^{e_2} \cdot … \cdot p_{k}^{e_k} \), are loc relația: \( \varphi(n)=(p_{1}-1)p_{1}^{e_{1}-1} \cdot(p_{2}-1)p_{2}^{e_{2}-1} \cdot \cdots \cdot (p_{k}-1)p_{k}^{e_{k}-1} \).
O scriere echivalentă este: \(\varphi(n)=n \left(1-\frac{1}{p_{1}}\right) \cdot \left(1-\frac{1}{p_{2}}\right) \cdot \cdots \cdot \left(1-\frac{1}{p_{k}}\right) \)

Exemplu: Pentru \( n = 12\), numerele mai mici decât \( n \), prime cu acesta sunt: \( \text 1, 5, 7, 11\), adică \( 4 \) numere.
Descompunerea în factori este: \( n = 12 = 2^2 \cdot 3^1 \).
Aplicând formula de mai sus obținem \( \varphi(12) = (2-1) \cdot 2^{2-1} \cdot (3-1) \cdot 3^{1-1} = 1 \cdot 2^1 \cdot 2 \cdot 3^0 = 2 \cdot 2 = 4 \).

Observaţie: Dacă \( n \) este număr prim, atunci \( \varphi(n) = n – 1 \).

Teorema lui Euler:

Dacă \(a, n\) sunt două numere naturale prime între ele, atunci:
$$ a^{ \varphi (n) } \equiv 1 \left(\mod n \right) $$

Operațiile pe biți sunt operații foarte eficiente, deoarece ele lucrează direct cu biții din reprezentările în memorie ale operanzilor. Înțelegerea lor presupune înțelegerea reprezentării în memorie a datelor întregi.

Reprezentarea în memorie a valorilor întregi

Valorile întregi se reprezintă în memorie ca o secvență de biți (cifre binare, 0 și 1). Acestă secvență poate avea 8, 16, 32 sau 64 de biți.

Reprezentarea în memorie a datelor de tip întreg se face în mod similar pentru toate tipurile cu semn (char, short int, int, long long int) și similar pentru toate tipurile fără semn (unsigned char, unsigned short int, unsigned int, unsigned long long int).

În exemplele care urmează vom folosi tipurile reprezentate pe 16 biți: unsigned short int, respectiv short int.

Reprezentarea în memorie a valorilor de tip unsigned short int

Tipul unsigned short int memorează valori mai mari sau egale cu 0. Acestea se reprezintă în memorie astfel:

• se transformă numărul în baza 2 și se memorează, adăugând la început cifre de 0 nesemnificative, atâtea câte sunt necesare până la completarea celor 16 biți.
• dacă reprezentarea în baza 2 a numărului are mai mult de 16 cifre, se vor memora numai ultimele 16 cifre – numărul se va trunchia.

Astfel, valorile fără semn care se pot reprezenta pe 16 biți sunt cuprinse între 0 și 216-1, adică 0 și 65535.

• 0 se reprezintă 0000000000000000
• 65535 se reprezintă 1111111111111111
• 5 se reprezintă 0000000000000101
• 133 se reprezintă 0000000010000101

Reprezentarea în memorie a valorilor de tip short int

Tipul short int memorează atât valori pozitive, cât și valori negative. Astfel, dintre cei 16 biți disponibili, cel mai din stânga (numit bit de semn) stabilește semnul numărului. Dacă acest bit este 0, numărul este pozitiv, dacă acest bit este 1, numărul este negativ. Astfel, se pot memora 32768 valori negative, de la -32768 la -1, și 32768 pozitive sau zero, de la 0 la 32767.

Reprezentarea numerelor pozitive se face exact ca mai sus: se transformă numărul în baza 2 și se completează cu zerouri nesemnificative.

Nu la fel se face reprezentarea numerelor întregi negative. Această reprezentare se face conform pașilor următori, numită reprezentare în cod complementar:

1. se determină reprezentarea în memorie a numărului ce reprezintă valoarea absolută a numărului inițial. Aceasta are bitul de semn 0.
2. se determină complementul față de 1 a reprezentării de la pasul anterior – fiecare bit 1 devine 0 și fiecare bit 0 devine 1.
3. se adună 1 la valoarea obținută

De exemplu, pentru reprezentarea în memorie a numărului -133 (considerat de tip short int) se procedează astfel:

1. se determină reprezentarea în memorie a lui 133 și se obține:
   0000000010000101
2. se obține complementul față de 1:
   1111111101111010
3. se adună 1 și se obține:
   1111111101111011

Mecanismul de memorare numerelor este același pentru toate tipurile întregi. Diferă numai numărul de biți folosiți pentru reprezentare și implicit intervalul din care fac parte valorile reprezentate.

Operatori pe biți

Operațiile pe biți se aplică numai datelor de tip întreg, și presupun manipularea directă a biților din reprezentarea în memorie a operanzilor.

Operatorul de negație ~

Este un operator unar care are ca rezultat numărul obținut prin complementarea față de 1 a biților din reprezentarea numărului inițial (biții 0 devin 1, biții 1 devin 0).

Exemplu:

~ 133 == -134

Reprezentarea lui 133 este 0000000010000101. Prin complementare se obține 1111111101111010. Aceasta este reprezentarea în memorie a lui -134.

Pentru a verifica, îl reprezentăm conform celor de mai sus pe -134:

1. reprezentarea lui 134 este 0000000010000110
2. prin complementare se obține 1111111101111001
3. adunăm 1 și obținem 1111111101111010

Operatorul de conjuncție biți &

Este un operator binar care are ca rezultat numărul obținut prin conjuncția fiecărei perechi de biți ce apar în reprezentare în memorie a operanzilor:

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

Exemplu:

Să calculăm 13 & 151.

Reprezentarea lui 13 este 0000000000001101. Reprezentarea lui 151 este 0000000010010111:

0000000000001101 &
0000000010010111

Se obține:

0000000000000101, adică 5

Deci: 13 & 151 == 5

Operatorul de disjuncție pe biți |

Este un operator binar care are ca rezultat numărul obținut prin disjuncția fiecărei perechi de biți ce apar în reprezentare în memorie a operanzilor:

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

Exemplu:

Să calculăm 13 | 151.

Reprezentarea lui 13 este 0000000000001101. Reprezentarea lui 151 este 0000000010010111:

0000000000001101 |
0000000010010111

Se obține:

0000000010011111, adică 159

Deci: 13 | 151 == 159

Operatorul de disjuncție exclusivă ^

Este un operator binar care are ca rezultat numărul obținut prin disjuncția exclusivă fiecărei perechi de biți ce apar în reprezentare în memorie a operanzilor:

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

Exemplu:

Să calculăm 13 ^ 151.

Reprezentarea lui 13 este 0000000000001101. Reprezentarea lui 151 este 0000000010010111:

0000000000001101 ^
0000000010010111

Se obține:

0000000010011010, adică 2 + 8 + 16 + 128 = 154.

Deci: 13 ^ 151 == 154

Operatorul de deplasare spre stânga – shift left <<

Este un operator binar care are ca rezultat numărul obținut prin deplasare spre stânga a biților din reprezentarea în memorie a primului operand cu un număr de poziții egal cu al doilea operand.

Să calculăm 13 << 3.

Reprezentarea lui 13 este 0000000000001101. Deplasând toți biții spre stânga cu 3 poziții se obține: 0000000001101000, adică 104.

Să observăm că 104 este egal cu 13 * 23. În general n << k este n * 2k.

Pentru a calcula 2n putem folosi operația 1 << n.

Operatorul de deplasare spre dreapta – shift right >>

Este un operator binar care are ca rezultat numărul obținut prin deplasare spre dreapta a biților din reprezentarea în memorie a primului operand cu un număr de poziții egal cu al doilea operand.

Să calculăm 133 >> 3.

Reprezentarea lui 133 este 0000000010000101. Deplasând toți biții spre dreapta cu 3 poziții se obține: 0000000000010000 adică 16.

Să observăm că 16 este egal cu 133 / 23. În general n >> k este n / 2k.

Vezi și

• Aplicații ale operațiilor pe biți