Tutorial - Codul complementar

[suri]

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 n-are nevoie (veti vedea ulterior de ce), iar impartirile sunt o adevarata problema.  

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 03 ... 09 10 11 12 ... 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   ):
- codul 00 il alocam numarului 0;
- codurile 01 ... 49 le alocam numerelor 1 ... 49;
- codurile 50 ... 99 le alocam numerelor -50 ... -1 astfel:

Cod:

Numar -50 -49 ... -6  -5  -4  -3  -2  -1   0   1   2   3   4   5   6 ...  48  49
Cod    50  51 ... 94  95  96  97  98  99  00  01  02  03  04  05  06 ...  48  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   )

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 !  :shock: )
     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...  :lol: )
     (-2) x (-3) = 98 x 97 = 9506 (95 din fata se pierde !!) = 6  (wtf, iar s-a facut ceva "pe sub mana", si totusi... )

4. Impartirea se face prin incercari si erori (dar cu un algoritm eficient). Trebuie cunoscut ordinul de marime al catului (nu e greu de determinat), se inmulteste impartitorul cu catul si se compara cu deinmultitul. De aia operatia de impartire a numerelor intregi este mult mai lunga.

Sii... veti spune, bine dar 30 + 40 = 30 + 40 = 70 = -30  (rezultat wrong, wtf ?  :shock: )
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 intro postare ulterioara.

[Agkelos]

Bravo ! Keep it up !

Desi... cam de mult timp astept postul urmator in care explici de ce 30 + 40 = 30 + 40 = 70 = -30 ( :error: ) si cum e faza cu impartirea... sincer, intr-o oarecare masura stiam si inainte cum se fac adunarile, scaderile si inmultirile in cadrul procesorului, dar cu impartirea is cam in ceata... ceva imi scapa... asa ca posteaza odata si nu ma mai tine in suspans !   :mrgreen:

[suri]

Sa facem acum un exemplu de cod complementar in binar pe numere reprezentate pe 1 octet, ca fiind mai usor de prezentat. Logica functioneaza identic 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:

Cod:

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:

Cod:

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 denumit 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 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:

Cod:

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

Cod:

Pozitia    C S1234567
a            00111010
b            00011011
Transport  0 0111010-
a + b        01010101

Exemplu la limita: a = 100,  b = 27,  a + b = 127

Cod:

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

Cod:

Pozitia    C S1234567
a            01100100
b            00111010
Transport  0 1100000-
a + b        10011110

Exemplu la limita: a = 100,  b = 28,  a + b = 128

Cod:

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

Cod:

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

Cod:

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

Cod:

Pozitia    C S1234567
a            11000111
b            11100100
Transport  1 1000100-
a + b        10101011

Exemplu la limita: a = -100,  b = -28,  a + b = -128

Cod:

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

Cod:

Pozitia    C S1234567
a            10011100
b            11000111
Transport  1 0011100-
a + b        01100011

Exemplu la limita: a = -100,  b = -29,  a + b = -129

Cod:

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  

[Scratch]

WoW Suri, Danke mult, foarte interesant !!!! Tine-o tot asa...cat am citit ce ai postat tu nici n-am respirat, foarte inetersant ! ;-)

[DarthSion]

Super tutorial suri. M-ai luminat . Asta a fost foarte bine explicat si am inteles tot... Insa cel cu floating point... Mi-a facut capul mare

[suri]

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, vezi depasirea binara):

Negativul lui 35 este -35:

Cod:

Pozitia    C S1234567
 35        0 00100011
inversare    11011100
+1                  1
Transport  0 0000000-
-35          11011101

Negativul lui -35 este 35:

Cod:

Pozitia    C S1234567
-35        0 11011101
inversare    00100010
+1                  1
Transport  0 0000000-
 35          00100011

Exemple la limita:
Negativul lui 0:

Cod:

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:

Cod:

Pozitia    C S1234567
 127       0 01111111
inversare    10000000
+1                  1
Transport  0 0000000-
-127         10000001

Negativul lui -128 nu este reprezentabil:

Cod:

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.

[suri]

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

Cod:

Pozitia    C S1234567
18           00010010
1<- = 36     00100100

18 deplasat la dreapta este 18 : 2 = 9

Cod:

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

Cod:

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:

Cod:

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:

Cod:

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

Cod:

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

Cod:

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":

Cod:

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.

[Andreya]

superrrrrr..asta fac eu acum la facultate..o sa-mi fie de ajutor!!!!!  

[SkullAds]