codificari binare si aritmetica binara a numerelor intregi

CODIFICARI BINARE SI ARITMETICA BINARA A NUMERELOR INTREGI

CODIFICARI BINARE SI ARITMETICA BINARA A NUMERELOR INTREGI

Prin particularitile ei, aritmetica binar se preteaz la automatizare mai bine dect aritmetica n orice alt baz de numeraie. Acesta este motivul pentru care n calculatoare se folosete aritmetica n baza 2. Pentru a valorifica la maximum posibilitile tehnice actuale, pe lng reprezentarea obinuit a numerelor n baza 2, se mai practic, dup cum vom vedea, i alte moduri de reprezentare (alte codificri ale numerelor ntregi).

Dimensiuni i tipuri de reprezenri

Fiind vorba de calcule efectuate cu o main, se impun firesc o serie de condiii. Cea mai important dintre ele este dimensiunea de reprezentare. Numrul de cifre binare din reprezentarea unui numr este o constant a calculatorului, fixat la proiectarea sistemului de calcul respectiv.

Fie n numrul de bii ai unei locaii care conine un numr ntreg. Valorile lui n la calculatoarele actuale pot fi: 8, 16, 32 i 64, respectiv 1 octet, 2 octei, 4 octei i 8 octei. Acestea sunt singurele dimensiuni de locaii cu care se execut operaii binare asupra numerelor ntregi. Excepiile de la aceast regul sunt att de rare, nct nu merit s ne ocupm de ele.

Mai mult, dimensiunile a doi operanzi care particip la o operaie, precum i dimensiunile rezultatului sunt de asemenea constante ale calculatorului, indiferent de tipul de codificare a numerelor. Pentru a preciza regulile de dimensionare n operaiile binare asupra numerelor ntregi, vom folosi sintagma "operaie pe n bii".

R1) Operaiile de adunare pe n bii i scdere pe n bii presupun c ambii termeni sunt reprezenai pe cte n bii, iar rezultatul, suma sau diferena, se va reprezenta tot pe n bii.

R2) Inmulirea pe n bii presupune c ambii factori sunt reprezentai pe cte n bii, iar produsul lor va fi reprezentat pe 2(n bii.

R3) Imprirea pe n bii (oarecum invers fa de nmulire), impune condiia ca dempritul s fie reprezentat pe 2(n bii, iar mpritorul pe n bii. Operaia furnizeaz dou rezultate: ctul reprezentat pe n bii i restul reprezentat tot pe n bii.

Structura unei locaii de n bii, mpreun cu modul de numerotare a biilor, este:

. . .

n-1 n-2 . . . 2 1 0

Postulm faptul c bitul 0 este cel mai puin semnificativ, conine cifra unitilor i se afl la dreapta locaiei. Bitul 1 este urmtorul ca ordin de semnificaie, conine cifra "zecilor" (n baza 2) i se afl la stnga bitului 0 i la dreapta bitului 2. Continund, se ajunge, n final, la bitul n-1, care este bitul cel mai semnificativ i se afl la stnga locaiei de reprezentare. In legtur cu aceast structur, n 4.5 vom reveni pe larg cu o serie de precizri foarte importante.

R4) Dac rezultatul unei operaii nu ncape n locaie (apare depire), atunci se vor pierde biii cei mai semnificativi, rmnnd biii 0, 1, 2 .a.m.d.

In ceea ce privete tipurile de numere ntregi cu care se opereaz, exist dou (clase de) convenii de reprezentare:

- convenia de reprezentare fr semn, n care se opereaz numai cu numere naturale;

- convenii de reprezentare cu semn, n care se opereaz att cu numere pozitive, ct i cu numere negative. (Am folosit pluralul "convenii", deoarece, dup cum vom vedea, exist mai multe astfel de reprezentri).

In seciunile urmtoare vom detalia fiecare dintre acestea. Ca moduri de scriere, vom folosi n principal scrierea binar, dar vom folosi frecvent i scrierea hexazecimal.

Aritmetica numerelor ntregi fr semnConvenia de reprezentare fr semn

Aceast convenie se rezum la scrierea binar a numrului ntreg i reprezentarea lui pe n bii. Gama numerelor posibile de reprezentat este:

[0, 2n - 1] adic [0...0 ; 1...1] ,

unde apar n zerouri, respectiv n cifre 1. Concret, aceste intervale sunt:

n = 8

[ 0 , 255 ]

n = 16

[ 0 , 65535 ]

n = 32

[ 0 , 4 294 967 295 ]

n = 64

[ 0 , 18 446 824 753 389 551 615 ]

In situaia n care un numr binar necesit mai puin de n cifre binare, restul biilor de la stnga (cei mai semnificativi), vor fi completai cu zerouri.

De exemplu, pentru n = 8, avem reprezentrile:

12 = 00010010 = (18)10

16 2

F3 = 11110011 = (243)10

16 2

Pentru n = 16, avem reprezentrile:

023F = 0000001000111111 = (575)10

16 2

028A = 0000001010001010 = (650)10

16 2

005A = 0000000001011010 = (90)10

16 2

FFFF = 1111111111111111 = (65535)10

16 2

Adunarea i scderea fr semn

Operaiile de adunare i de scdere sunt efectuate de calculator exact dup algoritmii cunoscui din clasa I primar, cu singura deosebire c operaiile sunt efectuate n baza 2. In schimb, datorit regulilor de dimensionare i a faptului c operaia este efectuat de main i nu de om, apar dou excepii:

1) Dac rezultatul adunrii nu ncape pe n bii, depire la adunare, atunci rmn n rezultat numai biii de la ordinul 0 la ordinul n-1, iar bitul de ordin n se pierde.

2) Dac ntr-o operaie de scdere desczutul este mai mic dect scztorul, atunci are loc depire la scdere, dar operaia se execut, fcndu-se "mprumut fictiv" de la un rang inexistent.

Dm, n continuare, cteva exemple de operaii. Pentru fiecare operaie, vom scrie mai nti operanzii n baza 10, apoi n baza 16 i apoi n baza 2. Numrul de bii pe care se lucreaz reiese din context.

18+ 12+ 00010010+

18 12 00010010

-- -- --------

36 24 00100100

243- F3- 11110011-

18 12 00010010

--- -- --------

225 E1 11100001

243+ F3+ 11110011+

18 12 00010010

--- -- --------

261 05 00000101 Depire la adunare!

18- 12- 00010010-

243 F3 11110011

--- -- --------

-225 1F 00011111 Depire la scdere!

575+ 023F+ 0000001000111111+

650 028A 0000001010001010

--- ---- ----------------

1225 04C9 0000010011001001

650- 028A- 0000001010001010-

575 023F 0000001000111111

--- ---- ----------------

75 004B 0000000001001011

65536+ FFFF+ 1111111111111111+

90 005A 0000000001011010

----- ---- ----------------

65626 0059 0000000001011001 Depire la adunare!

575- 023F- 0000001000111111-

650 028A 0000001010001010

--- ---- ----------------

-75 FFB5 1111111111010101 Depire la scdere!

Inmulirea ntregilor fr semn

nmulirea fr semn a numerelor ntregi reprezentate binar se desfoar conform algoritmului cunoscut. S considerm mai nti un exemplu. Pentru comoditate, vom considera n = 4. S nmulim numerele M = (11)10 cu Q = (13)10, adic M = (1011)2 i N = (1101)2.

1011 (

1101

----

1011

0000

1011

1011

---------

100001111

Intr-adevr, 11 ( 13 = 143 = (10001111)2

Plecnd de la acest exemplu, s facem cteva observaii:

1) nmulirea genereaz o serie de produse pariale care sunt adunate. Exist cte un produs parial pentru fiecare cifr a nmulitorului.

2) Produsele pariale sunt fie denmulitul, fie 0.

3) Produsele pariale nenule pot fi adunate unul cte unul. Ele sunt obinute deplasnd denmulitul spre stnga cu cte o poziie.

4) nmulirea a dou numere de cte n bii genereaz un produs care ocup 2(n bii.

S notm prin M denmulitul i prin Q nmulitorul. S considerm nc dou locaii (doi regitri) notate C i A. Presupunem c M,Q i A se reprezint pe cte n bii iar C are capacitatea de 1 bit.

DEFINITIA 4.1 Operaia de deplasare logic spre dreapta cu o poziie a unei configuraii de n bii nseamn transformarea unei configuraii:

xn-1xn-2...x1x0

n configuraia:

0 xn-1...x2x1

Deci, bitul de ordin 0 se pierde, toi ceilali bii i micoreaz ordinul de mrime cu cte o unitate, iar bitul de ordin n-1, rmas liber, devine 0. Cu alte cuvinte, deplasarea spre dreapta a reprezentrii binare a unui ntreg fr semn d ctul mpririi la 2 a numrului iniial.

Cu aceste notaii, descrierea din fig. 4.1 prezint algoritmul de nmulire a numerelor fr semn. Prin CA, AQ i CAQ s-a notat concatenarea (alipirea) locaiilor respective.

DATE denmulitul M i nmulitorul Q

CA := 0;

PENTRU i:= 1 , n EXECUT

DAC Q0 = 1 ATUNCI

CA := A + M

SF_DACA

CAQ se deplaseaz spre dreapta cu 1 poziie

SF_PENTRU

REZULTATE AQ

Figura 4.1 Inmulirea ntreag fr semn

S aplicm acest algoritm pentru exemplul de mai sus:

M C A Q

|

1011 0 0000 1101 valorile iniiale

0 1011 1101 adunare i=1

0 0101 1110 deplasare

0 0010 1111 deplasare i=2

0 1101 1111 adunare i=3


1 0001 1111 adunare i=4


Imprirea ntregilor fr semn

mprirea fr semn se efectueaz, de asemenea, dup regulile cunoscute ale aritmeticii. S lum mai nti un exemplu:

100100111011

1011

=1110 1101

1011

=0111

0000

=1111

1011

----

=100

Intr-adevr, 147 mprit la 11 d ctul 13 i restul 4.

Ca i la nmulire, putem face o serie de observaii. Acestea evideniaz faptul c, n ultim instan, mprirea n baza 2 se reduce la o succesiune de scderi succesive combinate cu operaii de deplasare.

S notm prin M mpritorul reprezentat pe n bii. Aa cum am spus n 4.1, dempritul l vom reprezenta pe 2(n bii i anume n succesiunea AQ a doi regitri de cte n bii. Vom considera nc registrul C de 1 bit.

DEFINITIA 4.2 Operaia de deplasare logic spre stnga cu o poziie a unei configuraii de n bii nseamn transformarea unei configuraii:

xn-1xn-2...x1x0

n configuraia:

Deci, bitul de ordin n-1 se pierde, toi ceilali bii i mresc ordinul de mrime cu cte o unitate, iar bitul de ordin 0, rmas liber, devine 0. Cu alte cuvinte, deplasarea spre stnga a reprezentrii binare a unui ntreg fr semn d produsul nmulirii cu 2 a numrului iniial.

Cu aceste notaii, descrierea din fig. 4.2 prezint algoritmul de mprire a doi ntregi fr semn.

DATE dempritul AQ i mpritorul M;

PENTRU i := 1, n EXECUT

CAQ deplasare stnga cu o poziie

DAC CA ( M ATUNCI

Q0 := 1

CA := CA - M

ALTFEL

Q0 := 0

SF_DAC

SF_PENTRU

REZULTATE ctul n Q, restul n A

Figura 4.2 Imprirea ntreag fr semn

S aplicm acest algoritm pentru exemplul de mai sus:

M C A Q

1011 ? 1001 0011 valori iniiale


0 0111 0111 scdere i 1 la ct


0 0011 1111 scdere i 1 la ct



0 0100 1101 scdere i 1 la ct

restul ctul

Reprezentri ale ntregilor cu semnParticularizri ale reprezentrii n virgul fix

Principala cauz care a impus standarde speciale de reprezentare a numerelor ntregi a fost existena numerelor negative. Aceste standarde asigur simplificarea operaiilor aritmetice. Astfel, prin codurile de reprezentare pe care le vom descrie, se elimin operaia de scdere, ea fiind nlocuit de o operaie de adunare.

Ca regul general, bitul cel mai semnificativ din reprezentare, n-1, este rezervat semnului. Vom nota cu s acest bit. Dac s = 0, atunci este vorba de un numr pozitiv, iar dac s = 1, este vorba de un numr negativ.

- Reprezentarea n convenie strict subunitar, n care nu este rezervat nici un bit pentru partea ntreag , deci virgula se afl imediat dup bitul de semn:

- Reprezentarea n convenie ntreag, n care nu este rezervat nici un bit pentru partea fracionar , deci virgula se afl n dreapta bitului 0:

In convenia subunitar, se lucreaz cu numere reale strict subunitare, avnd maximum n-1 cifre binare dup virgul. In convenia ntreag, se lucreaz cu numere ntregi avnd valoarea absolut de maximum 2n-1 - 1.

Aceste dou particularizri ale reprezentrii n virgul fix stau la baza reprezentrii cu semn a numerelor ntregi, dup cum se va vedea n continuare.

Coduri de reprezentare a ntregilor cu semn

n practica construciei sistemelor de calcul sunt folosite trei coduri de reprezentare. Le vom prezenta pe fiecare, att n convenia strict subunitar, ct i n convenia ntreag. Vom descrie legtura dintre convenia subunitar i convenia ntreag, vom da reguli practice de obinere a codificrii, situaii de excepie i exemple.

Codul direct

Fie x ( R, (x( < 1, cu maxim n-1 cifre binare dup virgul.

DEFINITIA 4.3 Numrul x reprezentat n cod direct n convenie subunitar nseamn:

Fie x un numr ntreg, (x( < 2n-1.

DEFINITIA 4.4 Numrul x reprezentat n cod direct n convenie ntreag nseamn:

REGULA PRACTICA: Un numr ntreg x, -2n-1 < x < 0, se reprezint n cod direct astfel. Se pstreaz cei n-1 bii de la reprezentarea lui (x(, adic biii de la rangul 0 la rangul n-2, iar bitul de rang n-1 se pune pe 1.

Regul este corect, deoarece opernd pe n bii avem:

2n = 10...0 ==> 2n - x = 2n + (-x) = 2n + (x( ==>

[x]D = 10...0 + (x( ,

deci pe poziia n-1 va apare 1, iar cele n-1 cifre ale lui (x( rmn nemodificate.

Atunci cnd reprezentarea este scris n hexazecimal, pentru codificare se adaug (80)16 la octetul cel mai semnificativ al reprezentrii.

Vom reprezenta acum numerele (18)10 i (-18)10 n cod direct pentru n = 8.

[18] = 12 = 00010010

D 16 2

[-18] = 92 = 10010010

D 16 2

Situaie de excepie. n reprezentarea numerelor ntregi folosind codul direct, numrul 0 are dou reprezentri i anume:

[0] = +0 = 00...0 i [0] = -0 = 10...0

D D

Codul invers


DEFINITIA 4.5 Numrul x reprezentat n cod invers n convenie subunitar nseamn:


DEFINITIA 4.6 Numrul x reprezentat n cod invers n convenie ntreag nseamn:

REGULA PRACTICA: Un numr ntreg x, -2n-1 < x < 0, se reprezint n cod invers inversnd valorile tuturor celor n bii care reprezint numrul (x(.

Regula este corect, deoarece opernd pe n bii, avem:

2n-1 = 11...1 ==> 2n-1+x = 2n-1+(-x) = 2n-1-(x( ==>

[x]I = 11...1 - (x(i se tie c un bit sczut din 1 d ca rezultat valoarea invers.

Atunci cnd reprezentarea este scris n hexazecimal, pentru codificare fiecare cifr va fi nlocuit cu cifra diferen pn la 15.

Regula de mai sus este aplicabil la orice configuraie de n bii. In literatur ea este cunoscut sub numele de complementare fa de 1, iar inversnd toi biii reprezentrii unui numr x se obine complementul fa de 1 al lui x.

Vom reprezenta acum numerele (18)10 i (-18)10 n cod invers pentru n = 8.

[18] = 12 = 00010010

I 16 2

[-18] = ED = 11101101

I 16 2

Situaie de excepie. n reprezentarea numerelor ntregi folosind codul invers, numrul 0 are dou reprezentri i anume:

[0] = +0 = 00...0 i [0] = -0 = 11...1

I I

Codul complementar


DEFINITIA 4.7 Numrul x reprezentat n cod complementar n convenie subunitar nseamn:


DEFINITIA 4.8 Numrul x reprezentat n cod complementar n convenie ntreag nseamn:

REGULA PRACTICA: Un numr ntreg x, -2n-1 < x < 0, se reprezint n cod complementar astfel: ncepnd de la bitul 0, spre stnga, se pstreaz biii de la reprezentarea lui (x( pn la ntlnirea primului bit de valoare 1, care se pstreaz i el. Incepnd de la stnga acestuia, toi ceilali bii i inverseaz valorile.

Regula este corect, deoarece opernd pe n bii, avem:

2n = 10...0 ==> 2n + x = 2n - (-x) = 2n - (x( ==>

[x]C = 10...0 - (xn-2...10...0)2 ,

deci efectund scderea se va face mprumut la bitul din stnga al lui 2n abia la ntlnirea cifrei 1 la scztor. Continund scderea, toi ceilali bii se vor inversa.

In specificarea hexazecimal, cele mai din dreapta cifre zero se vor pstra, prima cifr diferit de zero va fi nlocuit cu diferena ei pn la 16, iar restul vor fi nlocuite cu diferenele lor pn la 15.

Regula de mai sus este aplicabil la orice configuraie de n bii. In literatur ea este cunoscut sub numele de complementare fa de 2, iar inversnd spre stnga toi biii ncepnd cu primul bit 1 exclusiv ai reprezentrii unui numr x se obine complementul fa de 2 al lui x. Denumirea s-a ncetenit de la convenia subunitar, unde apare numrul 2. Deoarece la calculatoarele actuale se folosete practic numai codul complemtar, se mai spune simplu, complementare respectiv complement.

Vom reprezenta acum numerele (18)10 i (-18)10 n cod complementar pentru n = 8.

[18] = 12 = 00010010

C 16 2

[-18] = EE = 11101110

C 16 2

S remarcm un rezultat simplu care leag codul invers de cel complementar. Are loc:

TEOREMA 4.4 Dac x < 0, atunci [x]C = [x]I + 1

Intr-adevr, [x]C = 2n + x = 2n-1 + x + 1 = [x]I + 1.

Situaie de excepie. n reprezentarea numerelor ntregi folosind codul complementar, numrul 0 are reprezentare unic!

n schimb exist o configuraie de bii care nu reprezint nici un numr:

10...0

Pentru pstrarea consistenei n reprezentare, unele implementri atribuie acestei configuraii valoarea -2n-1.

ntr-adevr, n baza relaiei x

codificari binare si aritmetica binara a numerelor intregi

Documents