Codul complementar
Scris de Agkelos
Stiati ca un calculator nu stie face decat adunari?
Nu stie face nici scaderi, nici inmultiri, nici impartiri.
Atunci cum se descurca?
Cu scaderile, folosind operatiile in cod complementar.
De inmultiri si împartiri n-are nevoie (veti vedea ulterior de ce).
Aici se va trata codul complementar. Pentru a intelege mai usor principiul, se va da un exemplu in numere zecimale, care insa este tare “handicapat” fata de ce se poate face in binar (daca inca nu stiti de ce, veti intelege intr-o postare ulterioara).
Fie un calculator _zecimal_ cu registre care pot stoca cate doua cifre, deci valorile reprezentabile sunt 00 01 02 … 09 10 11 … 20 21 … 98 99 adica in total 100 de valori.
Aceste valori vor fi considerate _coduri_. Intrucat exista 100 de coduri, acestea pot fi asociate cu 100 de numere intregi. Pentru a putea reprezenta si numerele negative (avem nevoie de ele, nu?), codurile le distribuim in modul urmator (nu e la voia noastra :D ):
- codul 00 il alocam numarului 0;
- codurile 01 … 49 le alocam numerelor 1 … 49;
- codurile 50 … 99 le alocam numerelor -50 … -1 astfel:
Nr. -50 -49 … -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 … 49
Cod 50 51 … 94 95 96 97 98 99 00 01 02 03 04 05 06 … 49
Si acum sa ne jucam. Cand avem de facut o operatie, inlocuim numarul cu codul, apoi facem operatiile cu _codurile_ si convertim rezultatul in numar.
Remember: calculatorul nostru are _doar_ doua cifre zecimale.
1. Adunarea a doua numere pozitive, rezultat pozitiv. Exemplu:
2 + 3 = 02 + 03 = 05 = 5 (frumos, adevarat si la mintea cocosului :D )
2. Scaderea este inlocuita cu _adunarea cu un numar negativ_. Exemple:
5 - 3 = 5 + (-3) = 05 + 97 = 102
(1 din fata nu poate fi stocat si _se pierde_) = 2
(!! in pofida pierderii rezultatul este, totusi, corect! )
3 - 5 = 3 + (-5) = 03 + 95 = 98 = -2
(mda, de data asta nu a fost nicio “scamatorie”, iar rezultatul este
corect.)
3. Inmultirea numerelor pozitive si negative. Exemple:
2 x 3 = 02 x 03 = 06 = 6 (deocamdata am revenit “pe pamant” )
2 x (-3) = 02 x 97 = 194 (1 din fata se pierde) = -6
(iarasi pierderea aia ! rezultatul insa este… )
(-2) x (-3) = 98 x 97 = 9506 (95 din fata se pierde !!) = 6
(wtf, iar s-a facut ceva “pe sub mana”, si totusi… )
Sii… veti spune, bine dar 30 + 40 = 30 + 40 = 70 = -30
(_rezultat wrong_, wtf? )
Ei, deoarece numarul _maxim_ care are cod este 49, aici apare _depasirea_ si se semnaleaza o eroare (calculatorul nu poate face operatia). Cum isi da seama un calculator ca este o depasire? In calculatorul zecimal prezentat nu poate, dar intrunul binar da. _Cum_, se va explica mai jos.
—————————————————————————
Sa facem acum un exemplu de cod complementar in binar pe numere reprezentate pe 1 octet, ca fiind mai usor de prezentat.
Logica functioneaza la fel si la reperezentarile pe 2 sau mai multi octeti.
Pe un octet se pot reprezenta 256 de valori, care in cod complementar se distribuie asa:
zecimal binar
-128 10000000
-127 10000001
-126 10000010
… …
-2 11111110
-1 11111111
0 00000000
1 00000001
2 00000010
… …
126 01111110
127 01111111
In reprezentare binara numerotarea bitilor se face de la stanga la dreapta incepand cu 0, deci numerotarea pozitiei bitilor pe 1 octet este:
Pozitia 01234567
Valoarea xxxxxxxx
De remarcat ca pe prima pozitie (bitul 0) toate valorile pozitive au valoarea 0 si toate cele negative valoarea 1. Deci valoarea din bitul 0 poate indica semnul numarului si de aceea acest bit este numit chiar “bit semn”.
In hardware-ul procesorului acest bit are o functie suplimentara, de _indicator_ (flag), indicatorul “Semn” (Sign flag), notat S. Prin testarea acestui indicator se stabileste daca un numar este pozitiv (S = 0) sau negativ (S = 1). Acesta este unul din argumentele de baza pentru utilizarea codului complementar in forma prezentata.
Orice operatie aritmetica intr-un procesor se face in registrul “acumulator” (A), eventual in extensiile lui la dreapta. Hardware-ul procesorului pozitioneaza la stanga registrului A un registru de 1 bit, numit “Transport” (Carry), care este si el un indicator (Carry flag), notat cu C. A nu se confunda _indicatorul_ C cu _registrul_ C al procesorului. Ca urmare, situatia hardware este asa: C Sxxxxxxx
Notiunea de transport
=====================
Exemplu in sistemul zecimal. Sa se adune numerele 37 cu 45.
“In mintea noastra” (adica algoritmul) este asa:7 + 5 = 12, “scriem 2″ si “tinem 1″. Acest 1 “tinut” este “transportul”.
Transportul se adauga la unitatea de rang superior. Ca urmare, adunarea noastra continua cu:3 + 4 + 1 = 8, deci rezultatul este 37 + 45 = 82.
Cat poate fi transportul?
Exemplu zecimal (la limita) cu doua pozitii: 99 + 99 = 198, pe pozitia unitatilor avem 9+9=18, unde 1 este transportul, iar pe pozitia zecilor avem 9 + 9 + 1 = 19, unde 1 este din nou transportul.
Datorita faptului ca in orice sistem de numeratie suma a doua numere de pe o pozitie impreuna cu transportul din pozitia precedenta este mai mica decat doua unitati de ordin superior transportul nu poate fi decat 0 sau 1.
Acesta este un alt argument pentru utilizarea sistemului de numeratie binar (transportul este saturat).
Cu transportul (valorile T), logica hardware a unui procesor este:
Pozitia 01234567
Transportul T TTTTTTT-
Valoarea C Sxxxxxxx
De remarcat ca pe ultima pozitie (aici 7) nu poate exista transport.
Depasirea binara
================
Daca in timpul unei operatii de adunare binara rezultatul nu poate fi reprezentat in acumulator se spune ca apare “depasirea binara”.
Sa vedem cum functioneaza operatia de adunare si cum se depisteaza erorile de depasire binara.
In relatiile urmatoare:
” < ” inseamna “mai mic”
” <= ” inseamna “mai mic sau egal”
” >= ” inseamna “mai mare sau egal”
” > ” inseamna “mai mare”.
La adunarea a doua numere a si b sunt posibile 6 cazuri (toate exemplele pe 1 octet):
Cazul 1. a >= 0, b >= 0, a + b < 128, suma este reprezentabila, nu exista depasire.
Exemplu: a = 58, b = 27, a + b = 85
Pozitia C S1234567
a 00111010
b 00011011
Transport 0 0111010-
a + b 01010101
Exemplu la limita: a = 100, b = 27, a + b = 127
Pozitia C S1234567
a 01100100
b 00011011
Transport 0 0000000-
a + b 01111111
In ambele cazuri transporturile in C si S sunt 0 (nu exista transport nici in S, nici in C).
Cazul 2. a > 0, b > 0, a + b >= 128, suma NU este reprezentabila, exista depasire.
Exemplu: a = 100, b = 58, a + b = 158
Pozitia C S1234567
a 01100100
b 00111010
Transport 0 1100000-
a + b 10011110
Exemplu la limita: a = 100, b = 28, a + b = 128
Pozitia C S1234567
a 01100100
b 00011100
Transport 0 1111100-
a + b 10000000
In ambele cazuri transporturile in C sunt 0 si in S sunt 1 (exista transport in S, dar nu si in C).
Cazul 3. a >= 0, b < 0, 0 <= a + b < 128, suma este reprezentabila, nu exista depasire.
Exemplu: a = 100, b = -27, a + b = 73
Pozitia C S1234567
a 01100100
b 11100101
Transport 1 1100100-
a + b 01001001
Transporturile in C si S sunt 1 (exista transport si in S, si in C).
Cazul 4. a >= 0, b < 0, -128 <= a + b < 0, suma este reprezentabila, nu exista depasire.
Exemplu: a = 27, b = -100, a + b = -73
Pozitia C S1234567
a 00011011
b 10011100
Transport 0 0011000-
a + b 10110111
Transporturile in C si S sunt 0 (nu exista transport nici in S, nici in C).
Cazul 5. a < 0, b < 0, a + b >= -128, suma este reprezentabila, nu exista depasire.
Exemplu: a = -57, b = -28, a + b = -85
Pozitia C S1234567
a 11000111
b 11100100
Transport 1 1000100-
a + b 10101011
Exemplu la limita: a = -100, b = -28, a + b = -128
Pozitia C S1234567
a 10011100
b 11100100
Transport 1 1111100-
a + b 10000000
In ambele cazuri transporturile in C si in S sunt 1 (exista transport si in S, si in C).
Cazul 6. a < 0, b < 0, a + b < -128, suma NU este reprezentabila, exista depasire.
Exemplu: a = -100, b = -57, a + b = -157
Pozitia C S1234567
a 10011100
b 11000111
Transport 1 0011100-
a + b 01100011
Exemplu la limita: a = -100, b = -29, a + b = -129
Pozitia C S1234567
a 10011100
b 11100011
Transport 1 0000000-
a + b 01111111
In ambele cazuri transporturile in C sunt 1 si in S sunt 0 (nu exista transport in S, dar exista in C).
Analizand cele 6 cazuri de mai sus rezulta ca depasirea binara poate fi depistata analizand transporturile in indicatorii C si S printr-o operatie de “sau exclusiv” (XOR):
- daca transportul in C XOR transportul in S = 0 nu exista depasire;
- daca transportul in C XOR transportul in S = 1 exista depasire.
Toate aceste verificari se realizeaza prin hardware.
La reprezentarea pe 2 sau mai multi octeti urmatorii octeti largesc doar domeniul valorilor reprezentabile, dar nu aduc nimic in plus la logica depasirii binare.
Teoria matematica a codului complementar, in limba romana, o gasiti formalizata perfect (si de neinteles) in cartea:
Al. Teodorescu, I. Catona, C. Popescu - “Sistemul FELIX C-256 - limbajul ASSIRIS”, Editura Academiei RSR (Wow !), Bucuresti 1974.Este singura parte a cartii care mai este de actualitate. Din pacate cartea nu contine exemple, asa ca aici v-am facut sistematizarea materiei si exemplele.
Pentru curiosi, limbajul ASSIRIS inseamna ASamblorul Sistemului (de calcul,
francez) IRIS.
IRIS inseamna “Informatique et Réseaux pour l’Industrie et les Services” (Informatica si Retele pentru Industrie si Servicii).
Sistemele de calcul IRIS au fost fabricate in Romania sub numele “FELIX C-32″, “FELIX C-256″ si “FELIX C-512″.
—-
Ei, acum sper ca sunteti de acord cu mine ca sistemul de numeratie binar
este o minune si cel zecimal o idiotie provenita din cele 10 degete ale
noastre. Mai bine aveam 8, cate 4 la fiecare mana :D
—————————————————————————
Complementarea
==============
Scopul acestei postari este fixarea terminologiei, de care vom avea nevoie.
Din examinarea reprezentarii dintr-o postare anterioara se constata ca negativul unui numar se obtine prin inversarea bitilor si adunarea cifrei 1 pe ultima pozitie.
Prin inversarea bitilor se obtine “complementul fata de 1″, care, in paranteza fie spus, nu ne este util.
Prin adunarea la complementul fata de 1 a cifrei 1 pe ultima pozitie se obtine “complementul fata de 2″, in continuare “complement”.
In cod complementar complementul unui numar este negativul numarului.
Exemple - este figurat si indicatorul Carry (esential, v. depasirea binara)
Negativul lui 35 este -35:
Pozitia C S1234567
35 0 00100011
inversare 11011100
+1 1
Transport 0 0000000-
-35 11011101
Negativul lui -35 este 35:
Pozitia C S1234567
-35 0 11011101
inversare 00100010
+1 1
Transport 0 0000000-
35 00100011
Exemple la limita:
Negativul lui 0:
Pozitia C S1234567
0 0 00000000
inversare 11111111
+1 1
Transport 1 1111111-
-0 00000000
Deci negativul lui 0 este chiar 0, in binar (spre deosebire de virgula mobila) nu se poate face diferenta intre +0 si -0.
Negativul lui 127 este -127:
Pozitia C S1234567
127 0 01111111
inversare 10000000
+1 1
Transport 0 0000000-
-127 10000001
Negativul lui -128 nu este reprezentabil:
Pozitia C S1234567
-128 0 10000000
inversare 01111111
+1 1
Transport 0 1111111-
Depasire 10000000
Deoarece transporturile in S si C difera, apare depasirea binara.
—————————————————————————
Inainte de a aborda operatiile binare de inmultire si de impartire, vom examina un caz particular, inmultirea si impartirea cu 2.
=============================
In sistemul zecimal inmultirea cu 10 se face “adaugand un zero in coada”, iar impartirea cu 10 “taind un zero din coada”. De fapt, nu se adauga sau se taie, ci numarul este _deplasat_ cu o pozitie la stanga pentru inmultire, respectiv cu o pozitie la dreapta pentru impartire.
In sistemul binar lucrurile se petrec la fel. Baza de numeratie fiind 2, deplasarea unui numar binar la stanga cu o pozitie este echivalenta cu inmultirea cu 2, iar deplasarea la dreapta cu o pozitie este echivalenta cu impartirea cu 2.
Exemple cu numere pozitive ( p<- si p-> inseamna deplasat la stanga/dreapta p pozitii):
18 deplasat la stanga este 18 x 2 = 36
Pozitia C S1234567
18 00010010
1< - = 36 00100100
18 deplasat la dreapta este 18 : 2 = 9
Pozitia C S1234567
18 00010010
1-> = 9 00001001
O deplasare cu p pozitii este, bineinteles, egala cu inmultirea/impartirea cu 2^p.
Exemplu: 9 deplasat cu 2 pozitii la stanga este 9 x 2^2 = 9 x 4 = 36
Pozitia C S1234567
9 00001001
2< - = 36 00100100
Bineinteles ca la deplasarea la stanga pot aparea rezultate aiurea, de exemplu 9 deplasat la stanga 4 pozitii este 9 x 2^4 = 9 x 16 = 144:
Pozitia C S1234567
9 00001001
4<- = -112 10010000
La exemplul de mai sus s-ar mai putea sesiza anomalia in stil “depasire”.
Si mai rau insa este de exemplu 9 deplasat la stanga 5 pozitii, 9 x 2^5 = 9 x 32 = 288, cand nici macar in stil “depasire” nu se mai poate sesiza anomalia:
Pozitia C S1234567
9 00001001
5<- = 32 00100000
Din aceasta cauza ramane in sarcina programatorului sa se asigure ca rezultatul poate fi reprezentat (la deplasare nu se face nicio verificare privind rezultatul aritmetic).
Inmultirea cu 2 sau cu o putere a lui 2 a unui numar negativ nu ridica probleme.
Exemplu: -9 x 2^2 = -9 x 4 = -36
Pozitia C S1234567
-9 11110111
2<- = -36 11011100
La impartirea cu 2 sau cu o putere a lui 2 a unui numar negativ apare insa o problema.
Exemplu: -36 : 2^2 = -36 : 4 = -9
Pozitia C S1234567
-36 11011100
2-> = 55 00110111
Rezultatul de mai sus este gresit. Rezultatul ar fi fost corect daca pe primele doua pozitii ar fi intrat cate un 1 in loc de 0.
Observatia este ca la impartiri prin deplasare, ca rezultatul sa fie corect, la stanga registrului/acumulatorului trebuie sa se reproduca valoarea din bitul semn. De aceea exista doua tipuri de deplasari:
- deplasare “logica” stanga/dreapta, in care valorile care intra
la dreapta/stanga in urma deplasarii sunt 0 si
- deplasare “aritmetica” stanga/dreapta, in care la deplasarea la stanga, in dreapta intra 0, iar la deplasarea la dreapta se reproduce valoarea din bitul semn.
Exemplul precedent cu deplasarea “aritmetica”:
Pozitia C S1234567
-36 11011100
2-> = -9 11110111
De remarcat ca efectul deplasarilor la stanga este acelasi, indiferent ca deplasarea este logica sau aritmetica.
Exista si alte tipuri de deplasari (circulare = rotiri, impreuna cu bitul Carry), insa pentru operatii aritmetice cele prezentate mai sus sunt suficiente.
(C) 2006 suri
===========================================================================
Articolul a fost scris initial de suri, dar cum e prea ocupat cu studentii ca sa mai dea tarcoale pe forum mi-am permis sa public eu articolul.
Categoria: Programare