Reprezentarea numerelor in memorie

1.1      Chestiuni teoretice

1.1.1     Reprezentarea numerelor naturale

Un numar natural se reprezintǎ ca o colectie de cifre intr-o anumita baza. In sistemul pozitional, pozitia unei cifre determina ponderea cifrei in marimea numarului.

Baza 10

In sistemul zecimal (baza 10) cifrele bazei sunt

Baza 10 =

Fie numarul

Un numar cu n cifre in baza 10, are valoarea

Rangul i al coeficientului a_i este exponentul puterii lui 10. a₀ este cifra cea mai putin semnificativa a numarului, a_n-1 este cifra cea semnificativa a numarului.

Baza r

Fie r un numar natural > 1. Cifrele bazei r sunt

Baza r =

Fie numarul natural

unde: r > 1 este baza, n este numarul de cifre, iar a_i este cifra de pe pozitia i Marimea numarului natural corespunzator este

                (1)

unde .

Numerele naturale reprezentate cu n cifre intr-o baza r oarecare au valori cuprinse in intervalul [0  rⁿ-1].

Baza 2

In sistemul binar, (baza 2), cifrele bazei sunt

Baza 2 =

Cifrele sistemului binar, 0 si 1, se numesc biti. Numarul natural

are valoarea

Cifra a_n-1, cel mai semnificativ bit, se noteaza MSB (most significant bit), iar cifra a₀, cel mai putin semnificativ bit, se noteaza LSB (least significant bit). Exista urmatoarele notatii :

2¹⁰ = 1024 = 1K

2²⁰ = 1M

2³⁰ = 1G

In calculatoare, numerele intregi sunt reprezentate in baza 2.

Baza 8

In sistemul octal, (baza 8), cifrele bazei sunt

Baza 8 =

Baza 16

In sistemul hexazecimal (baza 16), cifrele bazei sunt

Baza 16 =

unde: A=10, B=11, C=12, D=13, E=14 si F=15.

Numarul

are valoarea

Conversia unui numar din bazele 2, 8 sau 16 in baza 10 se face aplicand formula (1).

Exemplu. Fie numarul binar N = (101011)₂. Aplicam formula (1) si obtinem

N = 1*2⁵+0*2⁴+1*2³+0*2²+1*2¹+1*2⁰ = (43)₁₀

Exemplu. Fie numarul octal N = (26)₈. Dupa formula (1) avem

N = 2*8¹+6*8⁰ = (22)₁₀

1.1.2     Numararea binara

Fie un numarator binar cu k biti. Numarul N ce se poate reprezenta este cuprins in intervalul [0 2^k-1]. In consecinta, un numarator binar evolueaza dupa regula N modulo 2^k, adica dupa valoarea 2^k-1 urmeaza valoarea 0. De exemplu, un numarator binar cu 2 biti evolueaza astfel

00, 01, 10, 11, 00, 01, .

1.1.3     Conversia zecimal - binara

Fie un numǎr natural reprezentat in sistemul binar

In partea dreapta avem un polinom de puteri ale lui 2. Coeficientul este 0 sau 1. Din expresia de mai sus a numǎrului se observǎ cǎ cifrele , etc., se pot obtine ca resturile impǎrtirilor repetate ale numarului N cu 2. Vom nota cu , , , caturile impartirilor repetate la 2 si cu , , , resturile impartirilor repetare la 2 ale numarului N. Vom nota

si vom scrie numarul N ca

unde este catul impartirii lui la 2, iar este restul impartirii lui la 2. Comparand cu expresia lui N de mai sus deducem:

adica , ultima cifra a numarului N convertit in binar, este chiar primul rest . Vom scrie catul ca

de unde deducem:

Dupǎ n astfel de operatii vom avea:

unde:

Algoritmul se opreste atunci cand . Dupa cum se observǎ, resturile obtinute reprezintǎ chiar cifrele numǎrului binar, primul rest este cifra cea mai putin semnificativa a numarului binar.

Exemplu. Sǎ convertim numarul 14 din baza 10 in baza 2. Prin impartiri repetate la 2 obtinem caturile si resturile din tabelul de mai jos.

Reprezentarea numǎrului 14 in binar este:

Algoritmul de conversie a unui numǎr natural N din baza 10 in baza 2 este urmǎtorul:

1.

2.

3. while

In algoritmul de mai sus operatorul % calculeaza restul impartirii a doua numere intregi. Resturile obtinute sunt cifrele numǎrului binar, primul rest fiind cifra cea mai putin semnificativǎ

Conversia din baza 10 in baza 8 sau 16 se face prin impǎrtiri repetate cu 8 si respectiv 16.

In acest fel obtinem reprezentarea in bazele 2, 8 si 16 a primelor 16 numere naturale din Tabelul 1.

Tabelul 1 . Reprezentarea primelor 16 numere naturale in bazele 10, 2, 8, 16.

1.1.4     Conversia intre bazele 2, 8 si 16

Avand un numar in baza 2, pentru reprezentarea sa in baza 16 se grupeaza cate 4 cifre binare care se convertesc intr-o cifra hexazecimala.

Exemple.

(1100)₂ = (C )₁₆ = (12)₁₀

Avand un numǎr in baza 2, pentru reprezentarea in baza 8 se grupeaza cate 3 cifre binare care se convertesc intr-o cifra octala.

Exemplu.

Pentru verificare

Conversia unui numar din baza 16 in baza 2 se face reprezentand fiecare cifrǎ hexazecimalǎ prin 4 cifre binare.

Exemplu.

(A4)₁₆ = (1010 0100)₂

Conversia unui numǎr din baza 8 in baza 2 se face convertind fiecare cifrǎ octalǎ in 3 cifre binare.

Exemplu.

(63)₈ = (110 011)₂

1.1.5     Reprezentarea numerelor intregi

In cazul numerelor binare cu semn, bitul cel mai semnificativ este bitul de semn. El este 0 pentru numere pozitive si 1 pentru numere negative, ca mai jos.

Exista trei reprezentǎri ale numerelor binare cu semn, prezentate mai jos.

Reprezentarea in mǎrime si semn

Un numǎr pozitiv  X se reprezintǎ in marime si semn ca:

Un numǎr negativ -X se reprezintǎ in marime si semn ca:

Bitii numarului sunt aceiasi, pentru numar pozitiv sau negativ, difera doar bitul de semn.

Exemple. Vom considera numere intregi reprezentate pe 8 biti in marime si semn, un bit de semn si 7 biti ai numǎrului:

Gama numerelor intregi reprezentabile pe un octet in mǎrime si semn este [-127, 127].

Putem scrie formula de reprezentare a numerelor binare in mǎrime si semn ca:

unde coeficientul are valoarea 0 sau 1. Primul bit va fi interpretat ca si coeficientul lui . Reprezentarea in marime si semn este rar folosita in calculatoare.

Reprezentarea in complement fatǎ de 1

Fie N un numar natural reprezentat in baza r si fie  cifrele numarului. Complementul unei cifre a numarului in baza r - 1 este

r - 1 -

Reamintim ca cifrele bazei r sunt .

Numarul N este reprezentat in complement fata de r - 1 complementand fiecare cifra a numarului fata de r - 1. De exemplu, un numar binar se complementeaza fata de 1 complementand fiecare cifra binara fata de 1, un numar hexazecimal se complementeaza fata de 15 complementand fiecare cifra hexazecimala fata de 15, etc.

Un numǎr pozitiv X se reprezintǎ in complement fatǎ de 1 ca:

Un numǎrul negativ -X se reprezintǎ in complement fatǎ de 1 ca:

unde: este complementul fata de 1 al cifrei . Pentru a reprezenta un numǎr negativ in complement fatǎ de 1 complementǎm toate cifrele numarului pozitiv fata de 1. Complementarea fata de 1 a unei cifre binare inseamna modificarea cifrei 1 in 0 si a cifrei 0 in 1. Reprezentarea unui numar negativ in complement fata de 1 se face modificand toate cifrele numarului pozitiv din 1 in 0 si din 0 in 1, inclusiv bitul de semn.

Exemple de numere reprezentate in complement fatǎ de 1 pe un octet.

Reprezentarea in complement fata de 1 nu se foloseste in calculatoare.

Reprezentarea numerelor binare in complement fatǎ de 2

Fie un numar natural N reprezentat in baza r cu n cifre. Complementul fata de r al numarului N este

In consecinta, complementul fata de 2 al unui numar binar cu n cifre este

iar complementul fata de 16 al unui numar hexazecimal cu n cifre este

Un numar pozitiv X se reprezintǎ in complement fatǎ de 2 ca:

Un numar negativ -X se reprezintǎ in complement fatǎ de 2 ca:

unde:

Complementul fata de doi al unui numar binar se obtine in felul urmator :

toate cifrele nule de la dreapta numarului raman nemodificate,

prima cifra nenula de la dreapta se complementeaza fata de doi,

restul cufrelor numarului se complementeaza fata de 1.

Aceeasi regula se aplica si numerelor reprezentate in baza 16:

toare cifrele nule de la dreapta numarului raman nemodificate,

prima cifra nenula de la dreapta se complementeaza fata de 16,

restul cufrelor numarului se complementeaza fata de 15.

Exemple de numere reprezentate in complement fatǎ de 2 pe un octet.

Mentionǎm cǎ in calculatoare numerele intregi se reprezintǎ, de regula, in complement fatǎ de 2. Consideram formula ce reprezintǎ un numar negativ in complement fatǎ de 2. Avem relatia:

In consecintǎ, putem scrie numarul negative reprezentat in complement fata de 2:

_{deci obtinem valoarea adevarata a numarului.}

Tabelul 2 arata numere intregi cu semn reprezentate pe 3 biti in complement fata de doi si in marime si semn. Bitul cel mai semnificativ este bitul de semn.

Tabelul 2. Numere intregi cu semn pe 3 biti in complement fata de 2 si in marime si semn.

1.1.6     Deplasarea numerelor binare cu semn

Inmultirea unui numǎr binar cu semn cu sau este echivalentǎ cu deplasarea numǎrului binar la stanga sau la dreapta cu o cifra. La deplasarea numarului binar, bitul de semn rǎmane neschimbat.

Cazul numerelor pozitive

Se deplaseazǎ toate cifrele numarului, iar cifrele adaugate sunt zerouri. Regula este evidentǎ din formula de reprezentare a numerelor pozitive. Fie numarul pozitiv

si numarul inmultit cu doi

de unde se deduce:

Am presupus cǎ prin inmultirea cu 2 a numǎrului X nu apare depǎsire. In acelasi fel se aratǎ cǎ regula este valabilǎ pentru impǎrtirea cu 2.

Exemple. Deplasarea numarului 28 cu o cifrǎ binarǎ la dreapta si la stanga.

Numere negative reprezentate in complement fatǎ de 2

Regula de inmultire a acestor numere cu  sau este urmǎtoarea:

• la deplasarea la stanga cifrele adǎugate sunt zerouri,
• la deplasarea la dreapta cifrele adaugate sunt unuri,
• reamintim ca bitul de semn rǎmane neschimbat.

Exemplu. Deplasarea numarului -28 cu o cifrǎ binarǎ la dreapta si la stanga.

1.1.7     Reprezentarea numerelor reale in virgula mobila

Numerele reale se reprezintǎ in calculator in virgulǎ mobilǎ. Numarul real R este pus sub forma

unde: f este un numar subunitar (mantisa), b este baza iar e este exponentul. Pentru exemplificare vom considera baza zece.

Exemple de reprezentare a numerelor reale.

Mantisa f are totdeauna un numar finit de cifre si in plus

In continuare, pentru exemplificare vom considera cǎ mantisa are 8 cifre. Deoarece mantisa are un numǎr finit de cifre, in unele cazuri se pierd cifrele mai putin semnificative din numǎr.

Exemplu. Numǎrul

se reprezintǎ ca:

Pentru mǎrirea preciziei calculelor se cautǎ ca prima cifra din mantisǎ sǎ fie diferitǎ de zero (vezi exemplul de mai sus). Numerele in aceasta forma se numesc normalizate.

1.1.7.1  Reprezentarea numerelor subunitare in baza 2

Cifrele bazei 2 sunt . Numarul subunitar este reprezentat ca o suma de puteri negative ale lui 2.

Exemple.

Conversia numerelor subunitare din baza 10 in baza 2

Regula de convertire a unui numar subunitar din baza 10 in baza 2 este urmatoarea.

Se inmulteste repetat numarul subunitar cu 2 si se retine partea intreaga. (Partea intreaga este 0 sau 1). Cifrele retinute sunt cifrele numarului subunitar in baza 2. Inmultirea se continua pana cand numarul subunitar devine 0, sau pana cand s-a obtinut numarul de cifre necesare.

Exemplu.

Aplicam regula de mai sus

0.375 * 2 = 0.75

0.75 * 2 = 1.5

0.5 * 2 = 1.0

Exista numere subunitare cu un numar finit de cifre in baza 10 care nu se pot reprezenta exact cu un numar finit de cifre in baza 2.

Exemplu. Fie numarul (0.4)₁₀

0.4 * 2 = 0.8

0.8 * 2 = 1.6

0.6 * 2 = 1.2

0.2 * 2 = 0.4

0.4 * 2 = 0.8

0.8 * 2 = 1.6

deci numarul (0.4)₁₀ se reprezinta in baza 2 ca un numar periodic cu perioada 0110. Deoarece in calculator se retine un  umar finit de cifre, (0.4)₁₀ nu se poate reprezenta exact in baza 2.

Conversia numerelor subunitare din baza 10 in baza 16 se face prin inmultirea repetata cu 16 si retinem partea intreaga intr-o cifra hexazecimala.

Exemplu. Fie din nou numarul (0.4)₁₀

0.4 * 16 = 6.4

0.4 * 16 = 6.4

Avem

(0.4)₁₀ = (0.6666...)₁₆

1.1.7.2  Reprezentarea numerelor reale in virgula fixa

Numerelor reale se pot reprezenta in virgula fixa considerand o virgula fictiva ce desparte partea intreaga de cea fractionara.  Fie de exemplu numere reale reprezentate pe 8 biti. Bitul cel mai semnificativ este bit de semn.

Numarul R = 01011.101 este 11.625

1.1.7.3  Reprezentarea numerelor reale in virgula mobila in baza 2

Reprezentarea numerelor in virgula mobila In baza 2 se face convertind numarul in baza 2 (partea intreaga si cea subunitara se convertesc separat, ca mai sus) si se pune numarul sub forma

unde mantisa m este un numar subunitar, iar exponentul e este putera lui e ce inmulteste mantisa. De regula, se cauta ca primul bit din mantisa sa fie 1. In acest caz avem

0.5 <= m < 1

In acesta reprezentare exista un bit de semn pentru mantisa si unul pentru exponent. Fie de exemplu numere reprezentate pe un octet, cu mantisa 5 biti si exponentul 3 biti.

Numarul

este

Exponentul arata cu cate pozitii va fi deplasat punctul binar la dreapta (e > 0) sau stanga (e < 0) pentru a obtine numarul binar initial fara exponent. Presupunem ca mantisa are m biti, inclusiv semnul, iar exponentul e biti (inclusiv semnul). Numarul maxim ce se poate reprezenta este

iar numarul minim este

1.1.7.4  Standardul IEEE de reprezentare a numerelor reale in virgula mobila

In calculatoarele personale numerele reale se reprezintǎ in virgulǎ mobilǎ in felul urmǎtor

R = ± 1.m * 2 ^c

Valoarea subunitara m va fi numita mantisa. Notam exponentul numarului real cu e. Domeniul exponentului este [-127, 127]. La exponent se adaugǎ totdeauna valoarea 127, pentru a nu avea doua semne, unul pentru mantisa si altul pentru exponent. Notam e + 127 = c. Valoarea c  se numeste caracteristica si are domeniul [0,254].

Bitul de semn are totdeauna valoarea 0 pentru numere pozitive si 1 pentru cele negative.

In reprezentarea in virgulǎ mobila scurtǎ (simpla precizie) numǎrul se reprezinta pe 32 biti. Bitul de semn ocupa bitul 31, exponentul ocupǎ bitii 23-30 iar mantisa bitii 0-22. Gama numerelor reale ce se pot reprezenta in acest format este

iar mantisa corespunde la opt cifre zecimale.

Exemple. Fie numarul . Bitul de semn este zero, m = 0, iar c = 0+127. In consecinta, primii noua biti din numar sunt

001111111

Numarul R va fi reprezentat in hexazecimal ca 3F800000.

Fir numarul . Bitul de semn este zero, m = 0, iar c = -1+127=126. Primii noua biti din numar sunt

001111110

Numarul se reprezinta in hexazecimal ca 3F000000.

Mentionǎm cǎ dacǎ exponentul este 255 iar mantisa este 0, numarul este Dacǎ exponentul este 255 si mantisa este diferitǎ de zero numarul este NaN (not a number). Valoarea NaN apare atunci cand efectuǎm urmatoarele operatii :

sau cand un operand este NaN.

In reprezentarea in virgulǎ mobila lungǎ (dublǎ precizie) numǎrul se reprezinta pe 64 biti. Domeniul exponentului este [-1023, 1023]. La exponent se adaugǎ cantitatea 1023, deci exponentul are domeniul [0, 2046]. Bitul de semn este bitul 63, exponentul ocupǎ bitii 52-62 iar mantisa ocupa bitii 0-51. Gama numerelor reale ce se pot reprezenta in dubla precizie este

1.1.8     Alte coduri binare

1.1.8.1  Codul BCD

In codul BCD fiecare cifra zecimala este codificata in binar pe 4 biti.

Exemplu.

1.1.8.2  Codul Gray

Fie numere in cod binary pe 3 biti

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

....

Se observa ca, la adunarea unei unitati la un numar, mai multi biti isi schimba starea. De exemplu, la trecerea de la numarul 0 1 1 la numarul 1 0 0 toti cei 3 biti isi schimba starea. In anumite dispozitive este imposibil ca doi sau mai multi biti sa-si schimbe starea simultan. Este nevoie de un alt cod, la care la adunarea unei unitati sa se modifica un singur bit. Acest cod este codul Gray. Pentru 3 biti avem cifrele

0 0 0

0 0 1

0 1 1

0 1 0

1 1 0

1 1 1

1 0 1

1 0 1

Codul Gray se pe n biti se genereaza din codul Gray pe n - 1 biti.

Fie codul Gray pe 1 bit

0

1

Codul Gray pe 2 biti se genereaza din codul Gray pe un bit prin reflexive si apoi se adauga ca prim bit un bit 0 la codul pe un bit si un bit 1 la codul reflectat.

0 0 0

1 0 1

.. ..

1 1 1

0 1 0

Codul Gray pe trei biti se genereaza din codul pe doi biti astfel:

0 0 0 0 0

0 1 0 0 1

1 1 0 1 1

1 0 0 1 0

... ..

1 0 1 1 0

1 1 1 1 1

0 1 1 0 1

0 0 1 0 1

1.2      Chestiuni de studiat

1. Sa se reprezinte urmatoarele numere intregi in baza 2 in marime si semn, complement fata de 1 si complement fata de 2 pe 8 biti:

107, 125, -107, -125, 31, 61, -2, -9, -1, 805

2. Sa reprezinte urmatoarele numere intregi in baza 2 in marime si semn, complement fata de 1 si complement fata de 2 pe 16 biti:
     -1, 1023, -255, 724, 61, -61
3. Sa se converteasca urmatoarele numere naturale in baza 10:

(101110)₂                       (1111)₈

(11111110)₂ (7777)₈

(ABCD)₁₆                         (1110)₁₆

(F0F0)₁₆              (10101)₂

4. Sa se converteasca in baza 10 numerele de mai jos. Primul bit este bitul de semn. Numerele sunt reprezentate in marime si semn.

11011011.0

0101.1111

001101011.011

0.1011101

0.1101

5. Sa se converteasca in virgula mobila pe 8 biti numerele de mai jos. Mantisa va ocupa 5 biti, cu primul bit de semn, iar exponentul 3 biti si primul bit de semn.
     -6.72, 15.54, 4.227, -2.55, 0.465, -3.85
   Se va preciza care este gama numerelor ce se pot reprezenta.
6. Sa se converteasca in virgula mobila pe 16 biti numerele de mai jos. Mantisa va ocupa 12 biti, primul bit este bitul de semn. Exponentul va ocupa 4 biti, 1 bit de semn si 3 biti valoarea absoluta.
          12.25, 48.375, -18.3, 74.8, -93.25
   Se va preciza care este gama numerelor ce se pot reprezenta.
7. Sa se converteasca urmatoarele numere reale pozitive din baza 2 in baza 10:

101.1111

10101.010101               
11011011.011

8. Sa se adune urmatoarele numere naturale:

(7777)₁₆ + (1111)₁₆ (7A2B)₁₆ + (5F4C)₁₆

(ABCD)₁₆ + (8DCB)₁₆       (ADEF)₁₆ + (1725)₁₆

(765)₈ + (423)₈               (235)₈ + (543)₈

(1101)₂ + (1101)₂                       (1011)₂ + (111)₂