Operatii aritmetice; conceptul de depasire

Operatii aritmetice; conceptul de depasire

1. De ce codul complementar?

Spuneam intr-o sectiune precedenta ca implementarile operatiilor peste intregi trebuie, pe de o parte sa fie eficiente, iar pe de alta parte sa se foloseasca, pe cat posibil, algoritmi comuni de evaluare a operatiilor fundamentale peste numere intregi, indiferent de conventia de reprezentare.

Pana in prezent reprezentarea in cod complementar raspunde cel mai bine cerintelor de mai sus. Principalele motive sunt urmatoarele doua:

Operatia de adunare se executa la fel, indiferent de faptul ca avem de-a face cu conventia de reprezentare fara semn sau cea de reprezentare cu semn. Operatia executata este o adunare simpla, pe n biti (n - dimensiunea locatiei), cu ignorarea ultimului transport.

Operatia de scadere se reduce la operatia de adunare a descazutului cu complementul scazatorului.

Dupa cum se apreciaza, procentul operatiilor aditive - adunari si scaderi este mult mai mare in aplicatii decat cel al operatiilor multiplicative. De aici si preferinta proiectantilor pentru adoptarea codului complementar pentru reprezentarea intregilor cu semn. In schimb, operatiile de inmultire si impartire sunt efectuate cu algoritmi separati pentru reprezentarile fara semn si reprezentarile cu semn.

In consecinta, programatorul isi alege conventia cu semn sau fara semn in functie de specificul problemei. El utilizeaza aceleasi operatii pentru adunari si scaderi si operatii specifice cu semn sau fara semn pentru operatiile de inmultire si impartire.

2. Conceptul de depasire

Asa dupa cum am aratat mai sus, reprezentarea numerelor intregi se face in locatii cu dimensiune fixata apriori. In mod natural, trebuie sa ne punem problema: ce se intampla cand rezultatul nu incape in spatiul care-i este rezervat?

Generic vorbind, depasirea apare atunci cand rezultatul unui calcul nu incape in spatiul care-i este rezervat.

Specific vorbind, conditiile de aparitie a unei depasiri apar in mod diferit in functie de context. Contextul depinde, pe de o parte daca se utilizeaza conventia fara semn sau conventia cu semn. Pe de alta parte, contextul depinde de tipul operatiei: aditiva sau multiplicativa.

Procesoarele sunt astfel construite incat sa semnaleze, in mod specific, fiecare situatie de depasire. Ramane in sarcina utilizatorului daca ia in calcul semnalele procesorului si pe care anume.

In cele ce urmeaza vom aborda, pe rand tipurile de operatii si in cadrul acestora vom semnala situatiile de depasire.

3. Adunari si scaderi

Operatiile de adunare si de scadere sunt efectuate de calculator exact dupa algoritmii cunoscuti din clasa I primara, cu singura deosebire ca operatiile sunt efectuate in baza 2. In schimb, datorita regulilor de dimensionare si a faptului ca operatia este efectuata de masina si nu de om, exista posibilitatea de aparitie a depasirilor.

Pentru cazul operatiilor fara semn, exista doua reguli care provoaca depasire:

R1) Daca rezultatul adunarii nu incape pe n biti, atunci apare depasire la adunare si raman in rezultat numai bitii de la ordinul 0 la ordinul n-1, iar bitul de ordin n se pierde.

R2) Daca intr-o operatie de scadere descazutul este mai mic decat scazatorul, atunci are loc depasire la scadere, dar operatia se executa, facandu-se 'imprumut fictiv' de la un rang inexistent.

Aceste reguli sunt intuitiv clare (justificabile) si se pot aplica si tehnic ca atare.

Dam, in continuare, cateva exemple de operatii de adunare si scadere analizate in conventia fara semn. Pentru fiecare operatie, vom scrie mai intai operanzii in baza 10, apoi in baza 16 si apoi in baza 2. Dimensiunea locatiilor este fie de un octet, fie de doi octeti.

Sa ne ocupam in continuare de operatiile de adunare si scadere in conventia cu semn. Toate numerele se vor considera ca fiind reprezentate in cod complementar.

Mai intai trebuie sa reamintim faptul ca in cod complementar scaderea inseamna, de fapt, adunarea descazutului cu complementul scazatorului (vezi sectiunea 1.). Pentru a surprinde situatiile de depasire este suficient sa studiem efectuarea de sume ale unor numere din intervalul [-2^n-1 , 2^n-1-1] si de a depista aici situatiile in care poate sa apara depasire, adica neincadrarea sumei in intervalul admis [-2^n-1 , 2^n-1-1] pentru suma pe n biti.

Sa consideram doua numere x , y din intervalul [-2^n-1 , 2^n-1-1] si sa consideram suma lor algebrica x + y. Este suficient sa studiem urmatoarele trei cazuri:

x <0 si y ≥ 0. Din apartenenta la interval avem ca -2^n-1 ≤ x < 0 si 0 ≤ y ≤ 2^n-1-1.

x ≥ 0 si y ≥ 0. Din apartenenta la interval avem ca 0 ≤ x ≤ 2^n-1-1 si 0 ≤ y ≤ 2^n-1-1.

x < 0 si y < 0. Din apartenenta la interval avem ca -2^n-1 ≤ x < 0 si -2^n-1 ≤ y < 0.

Inegalitatile din cazul 1) ne asigura ca in primul caz suma algebrica apartine aceluiasi interval. Intr-adevar, din inegalitatile: -2^n-1 ≤ x < 0 si 0 ≤ y ≤ 2^n-1-1 avem, pe de o parte, ca x ≤ x + y, deci -2^n-1 ≤ x + y. Pe de alta parte, din aceleasi inegalitati rezulta ca x + y ≤ y, deci x + y ≤ 2^n-1-1. In concluzie, x + y apartine intervalului [-2^n-1 , 2^n-1-1]. De aici se deduce ca daca doua numere sunt de semne contrare, atunci suma lor nu poate produce depasire. Asa cum se va vedea din exemplele care urmeaza, atunci cand se face suma codurilor complementare este posibil sa apara transport de cifra semnificativa, dar acest fapt este ignorat, deoarece nu produce depasire.

In cazurile 2) si 3) este posibila aparitia depasirii. In cazul 2) x + y poate avea valoarea maxima 2ⁿ-2, iar depasire apare daca x + y > 2^n-1-1. Deoarece codurile complementare se aduna ca si numere fara semn, rezulta ca depasire apare atunci cand pe pozitia bitului de semn apare cifra 1, ceea ce in cod complementar inseamna numar negativ!

In cazul 3) x + y poate avea valoarea minima -2ⁿ, iar depasire apare daca x + y < -2^n-1. Analog ca mai sus, rezulta depasire daca pe pozitia bitului de semn apare cifra 0, ceea ce in cod complementar inseamna numar pozitiv!

Din studiul celor trei cazuri rezulta o regula simpla a depasirii la adunare in cod complementar:

R3) Suma a doua numere reprezentate in cod complementar provoaca depasire daca si numai daca sunt de acelasi semn si rezultatul sumei lor este de semn contrar.

Din aceasta regula se poate deduce si regula depasirii la scaderea cu semn. Avand in vedere faptul ca o scadere a - b = c este echivalenta cu adunarea a = b + c, din regula R3 rezulta ca:

R4) Diferenta a doua numere reprezentate in cod complementar provoaca depasire daca si numai daca scazatorul si diferenta sunt de acelasi semn si descazutul este de semn contrar.

Practic, putem identifica doua tipuri de situatii ce vor semnala depasire la scaderea cu semn, in situatia b) fiind necesar un 'imprumut fictiv'.

Intuitiv, in cazul a) depasirea se justifica prin imposibilitatea obtinerii unui numar pozitiv ca rezultat al scaderii unui numar pozitiv dintr-unul negativ. In cazul b) depasirea se justifica intuitiv daca facem referire la adunarea echivalenta (a-b = c a = b+c); aici diferenta si scazatorul negative nu pot furniza descazut pozitiv.

Asa cum se va vedea din exemplele care urmeaza, atunci cand se face diferenta codurilor complementare este posibil sa apara imprumut fictiv de cifra semnificativa, dar acest fapt este ignorat, deoarece nu produce depasire.

In continuare prezentam cateva exemple de adunari si scaderi ale unor numere reprezentate in cod complementar. Pentru simplitatea expunerii, vom utiliza operanzii reprezentati in cod complementar pe 4 biti. Conform celor de mai sus, pentru patru biti intervalul de reprezentare este [-2³ , 2³-1], adica [-8 , 7]. Operanzii ii vom transcrie din baza 10 direct in cod complementar. Vom semnala cazurile de transport, imprumut fictiv si depasire.

Inmultiri si impartiri

Inmultirea si impartirea pe n biti impun urmatoarele restrictii de dimensiune a locatiilor:

Inmultirea pe n biti presupune ca ambii factori sunt reprezentati pe cate n biti, iar produsul lor va fi reprezentat pe 2 * n biti. In cazul conventiei cu semn, factorii inmultirii vor fi reprezentati in cod complementar. Produsul va fi reprezentat tot in cod complementar si va respecta regula semnelor.

Ca o consecinta imediata a acestei dimensionari, rezulta ca operatia de inmultire nu provoaca depasire! Intr-adevar, in conventia fara semn cea mai mare valoare posibila pe n biti este 2ⁿ-1, patratul acestei valori este 2²ⁿ- 2ⁿ⁺¹+1, numar care incape pe 2n biti. In conventia cu semn, numarul -2^n-1 are valoarea absoluta cea mai mare, iar patratul acesteia este 2^2n-2, numar care se poate reprezenta pe 2n-1 biti, deci in cod complementar acest numar se poate reprezenta pe 2n biti.

Impartirea pe n biti (oarecum invers fata de inmultire), impune conditia ca deimpartitul sa fie reprezentat pe 2 * n biti, iar impartitorul pe n biti. Operatia furnizeaza doua rezultate: catul reprezentat pe n biti si restul reprezentat tot pe n biti. In cazul conventiei cu semn, deimpartitul si impartitorul se vor reprezenta in cod complementar. Atat catul, cat si restul vor fi, de asemenea, reprezentate in cod complementar. Catul impartirii va respecta regula semnelor. Important! Restul impartirii va fi, in valoare absoluta mai mic decat valoarea absoluta a impartitorului si va avea acelasi semn ca si deimpartitul! De exemplu, -7 : 3 da catul -2 si restul -1, adica -7 = (-2) * 3 + (-1). Rugam cititorul sa compare acest rezultat cu cel impus de teorema impartirii cu rest din aritmetica, care impune ca restul sa fie un numar pozitiv, deci in aritmetica avem (-7) = (-3) * 3 + 2, deci catul -3 si restul 2!

Operatia de impartire semnaleaza eroare la impartitor zero (Divide by zero!). In cazul neincadrarii in dimensiuni semnaleaza depasire! Spre exemplu, impartirea fara semn 1000 : 3 se poate, formal, efectua, deoarece deimpartitul se poate reprezenta pe 16 biti si impartitorul se poate reprezenta pe 8 biti. La aceasta operatie va apare depasire, deoarece catul este 333 si nu se poate reprezenta pe 8 biti. Restul impartirii este 1 si se poate reprezenta pe un octet. Pentru a evita o astfel de situatie, programatorul poate decide sa faca operatia pe 16 biti, adica sa reprezinte deimpartitul pe 32 de biti si impartitorul pe 16 biti, urmand sa obtina catul si restul pe cate 16 biti (333 incape pe 16 biti si astfel nu vom mai avea depasire).

Sa exemplificam mai intai operatiile de inmultire si impartire fara semn.

Inmultirea fara semn a numerelor intregi reprezentate binar se desfasoara conform algoritmului cunoscut, doar ca se foloseste baza 2. Pentru comoditate, vom considera n = 4. Sa consideram factorii 11 si 13. Inmultirea lor in baza 2 este:

1011

1101

1011

0000

1011

1011

10001111

Intr-adevar, 11

Plecand de la acest exemplu, se poate observa ca:

Inmultirea genereaza o serie de produse partiale care sunt adunate. Exista cate un produs partial pentru fiecare cifra a inmultitorului.

Produsele partiale sunt fie deinmultitul, fie 0.

Produsele partiale nenule pot fi adunate unul cate unul. Ele sunt obtinute deplasand deinmultitul spre stanga cu cate o pozitie.

Inmultirea a doua numere de cate n biti genereaza un produs care ocupa 2*n biti (motiv pentru care s-a impus restrictia de dimensiune amintita mai sus).

Impartirea fara semn se efectueaza, de asemenea, dupa regulile cunoscute ale aritmeticii. Sa impartim pe 147 la 11. Impartirea in baza 2 este:

├────

|1101

1011

=0111

0000

=1111

1011

=100

Intr-adevar, 147 impartit la 11 da catul 13 si restul 4.

Ca si la inmultire, putem face o serie de observatii. Acestea evidentiaza faptul ca, in ultima instanta, impartirea in baza 2 se reduce la o succesiune de scaderi succesive combinate cu operatii de deplasare.

Sa reamintim cateva observatii privind inmultirile si impartirile cu semn.

Toti operanzii implicati in operatii sunt reprezentati in cod complementar, in conformitate cu cerintele de dimensionare expuse mai sus.

Atat la inmultirea cu semn cat si la impartirea cu semn, se respecta regula semnelor.

Pentru operatia de impartire, restul este in modul mai mic decat modulul impartitorului, iar semnul restului este acelasi cu semnul deimpartitului.

Algoritmii de inmultire si impartire in cod complementar nu pot fi preluati natural de la cei fara semn, asa cum stau lucrurile la adunare si scadere. Daca ar fi asa, atunci in exemplul de mai sus, interpretand 1011 ca -5 si 1101 ca -3 ar rezulta produsul -113 in loc de -15! Normal, deoarece configuratia de biti 10001111 care este rezultatul inmultirii binare, este reprezentarea in cod complementar a numarului -113! La fel, daca interpretam cu semn exemplul dat la impartirea fara semn, avem 'egalitatea' in cod complementar:

adica -109 = (-5) * (-3) + 4 !

Nu vom detalia algoritmii specifici inmultirii si impartirii cu semn. Cititorii pot obtine detalii din [Boian96].