Codifica binaria, esadecimale, complemento a 2

Abbiamo pensato che per alcuni di voi la conoscenza della codifica binaria e esadecimale sia un must da sapere, poiché vi permetterà di capire meglio come funziona un calcolatore. Infatti in un calcolatore, i dati e le istruzioni di un programma sono codificate in forma binaria, ossia in una sequenza finita di 0 e 1. La più piccola unità d’informazione memorizzabile o elaborabile da un calcolatore è il bit (binary digit); otto bit corrispondono a un byte. Ogni tipo di dato , qualunque esso sia: numeri (naturali, interi, reali, frazionari), testi, immagini, suoni, ecc. devono essere trasformati in sequenze di bit per essere elaborati. Noi, in particolare, ci occuperemo di tutta quella parte che riguarda la codifica dei numeri.

Codifica binaria
Il sistema binario si basa su un sistema di numerazione posizionale con base 2. Un sistema di numerazione posizionale è definito da una successione di moltiplicatori b1, b2, b3, … che corrispondono al rapporto tra il valore che una cifra assume in una data posizione e quello che assume nella posizione successiva. In formula si può scrivere (limitandosi per semplicità a un numero di quattro cifre):

c4c3c2c1 = c4×b^3 + c3×b^2 + c2×b^1 + c1×b^0

Il numero b si dice base del sistema di numerazione. Il sistema arabo è quello in base 10 (perciò viene detto anche sistema numerico decimale).

Passiamo subito agli esempi. Se volessimo sapere a che numero decimale corrisponde questa sequenza di bit 101001011 dovremmo moltiplicare ogni bit per (2 ^ x) dove x corrisponde alla posizione del bit. Vedendo l’esempio sarà più semplice comprendere come fare.
(n.b. nei linguaggi informatici la numerazione inizia da 0 e non da 1)
Posizione: 8 7 6 5 4 3 2 1 0 (ottavo bit, settimo bit, etc..)
Cifra: 1 0 1 0 0 1 0 1 1

101001011 = 1×2^8 + 0x2^7 + 1×2^6 + 0x2^5 + 0x2^4 + 1×2^3 + 0x2^2 + 1×2^1 + 1×2^0 = 256 + 64 + 8+ 2 + 1 = 331

Dunque abbiamo visto come trasformare un binario in un numero decimale… ma il contrario, come si fa? Mostreremo il modo più semplice per convertire un numero in base dieci in forma binaria. Per ottenere questo risultato, è sufficiente operare divisioni per due del numero decimale fino a raggiungere lo zero. Da qui prenderemo nota del resto di ogni singola divisione andando a formare così il nostro numero binario. Per esempio prendiamo il numero 28 e eseguiamo le divisioni

Div 1: 28 / 2 = 14 con resto 0
Div 2: 14 / 2 = 7 con resto 0
Div 3: 7 / 2 = 3 con resto 1
Div 4: 3 / 2 = 1 con resto 1
Div 5: 1 / 2 = 0 con resto 1

Una volta terminate le divisioni basterà ricomporre i resti partendo dal basso verso l’alto ottenendo così il numero binario corrispondente. Quindi procedendo dal resto della div 5, poi della div 4 e così via ricaveremo 11100. Esattamente il numero binario relativo al numero decimale 28.

Le codifiche ottale e esadecimale risultano interessanti per la semplicità di conversioni dalla base 2 alla base 8 oppure 16. Questa conversione può essere fatta per parti , considerando volta per volta un numero di (tre o quattro) cifre binarie. Vi illustriamo questo metodo con un esempio. Il numero 1010110111 coincide con il numero 1267 (base 8) e con il numero 2B7 (base 16). Infatti:
– Possiamo dividere il numero in triple (aggiungendo a sinistra un numero sufficiente di zeri affinché ci sia un numero di bit multiplo di 3): 001 010 110 111 e tradurre ciascuna tripla nella corrispondente cifra ottale. 001 corrisponde a 1 , 010 a 2, 110 a 6 e 111 corrisponde a 7, così da avere 1267.
– possiamo invece dividere il numero in quadruple: 0010 1011 0111 e tradurre ciascuna quadrupla nella corrispondente cifra esadecimale. Nella codifica esadecimale i numeri vanno da 0 a F nel seguente ordine : 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , A , B , C , D , E , F. 0010 sarà 2, 1011 sarà B e 0111 sarà 7, quindi 2B7.

Numeri interi
I numeri interi si differenziano dai numeri naturali perché includono, altre allo zero e ai numeri positivi, anche i numeri negativi. Pertanto nella codifica binaria, dovrà essere rappresentato il segno dei numeri , oltre al suo valore. Prendiamo in considerazione due diverse codifiche binarie di numeri interi: la prima, detta rappresentazione in modulo e segno, risulta molto più intuitiva, la seconda, detta rappresentazione in complemento a 2, è ampiamente utilizzata per semplificare l’esecuzione di operazioni matematiche tra numeri interi. Se m bit sono disponibili per rappresentare un intero, la rappresentazione in modulo e segno utilizza il primo bit (la posizione più a sinistra) come bit di segno; per convezione , 0 indica un numero positivo e 1 un numero negativo. Con questa notazione possiamo rappresentare gli interi compresi tra -( 2^(m-1) -1 ) e +( 2^(m-1) -1 ). Mediante un byte, perciò è possibile rappresentare i numeri compresi tra -127 e 127.
La rappresentazione in complemento a 2 di un numero negativo -N mediante m bit, si attua invertendone i bit del valore assoluto e sommando 1 al valore risultante. Con questa convenzione, quando sono disponibili m bit, possono essere rappresentati gli interi compresi tra -2^(m-1) e +( 2^(m-1) -1 ). Sempre con un byte possiamo scrivere i numeri che vanno da -128 a 127.

Esempio
Per rappresentare l’opposto di un numero binario in complemento se ne invertono, o negano, i singoli bit: si applica cioè l’operazione logica NOT. Si aggiunge infine 1 al valore del numero trovato con questa operazione.
Facciamo un esempio rappresentando il numero -10 con 8 bit in complemento a 2.
Partiamo convertendo il valore assoluto in numero binario
10 = 0000 1010
La prima cifra è 0, quindi il numero è sicuramente positivo. Invertiamo i bit: 0 diventa 1, e 1 diventa 0:
1111 0101
A questo punto abbiamo ottenuto il complemento a uno del numero 10; per ottenere il complemento a due sommiamo 1 a questo numero:

1111 0101 +
0000 0001 =
===========
1111 0110 risultato -10

Il risultato è un numero binario con segno che rappresenta il numero negativo -10 secondo il complemento a due. Il primo bit, pari a 1, evidenzia che il numero è negativo.

Il complemento a due di un numero negativo ne restituisce il numero positivo pari al valore assoluto: invertendo i bit della rappresentazione del numero -10 (sopra) otteniamo:

0000 1001

Sommando 1 otteniamo:

0000 1001 +
0000 0001 =
==========
0000 1010 (10)

Somma binaria

L’addizione tra due o più numeri in forma binaria si esegue come una normale addizione. Bisogna però ricordare che i valori che possono assumere i bit sono solo 0 e 1, quindi in caso di somma di 1 + 1 non si otterrà 2 bensì 0 con il riporto (carry) di 1.
Consideriamo la generica cifra di posto i: Ai e Bi. Le possibili combinazioni che possono assumere le cifre sono:
Ai Bi Somma Riporto
0 0 0 0 0 + 0 = 0, riporto 0
0 1 1 0 0 + 1 = 1, riporto 0
1 0 1 0 1 + 0 = 1, riporto 0
1 1 0 1 1 + 1 = 0, riporto 1

Esempio
Vogliamo sommare tra loro i numeri binari 10011 e 10001 che indicano, rispettivamente, i numeri decimali 19 e 17 in 8 bit.

10 0110 riporto
0001 0011 + (19)
0001 0001 = (17)
===========
0010 0100 (36)

Adesso proviamo a sommare 15 + (-5)
11111 1110 riporto
0000 1111 (15)
+ 1111 1011 (-5)
============
0000 1010 (10)
Questo processo gioca sulla lunghezza fissa di 8 bit della rappresentazione: viene ignorato un riporto di 1 che causerebbe un overflow, e rimane il risultato corretto dell’operazione (10).

L’overflow è un problema relativo alle operazioni sui numeri all’interno di un computer. Il problema è dovuto al fatto che il computer non è in grado di memorizzare un qualsiasi numero di cifre, ma solo tante quante sono i bit a disposizione nella memoria per quel tipo di dato. Ogni bit può assumere due soli valori, 1 e 0; se abbiamo a disposizione n bit (per esempio 4), possiamo memorizzare un numero massimo pari a (2^n)-1 (nell’esempio 1111, ovvero 15 nel sistema decimale). Se cercassimo di modificare questo numero aggiungendo 1 il numero diventerebbe 10000(16 in decimale), ma la macchina può memorizzare solo 4 bit, quindi memorizzerebbe il numero 0000 il che non corrisponde a quanto avremmo voluto.

Tornando all’esempio precedente, gli ultimi due bit (da destra a sinistra), ovvero i più significativi, della riga dei riporti contengono importanti informazioni sulla validità dell’operazione: se il risultato è compreso o non è compreso nell’intervallo dei numeri rappresentabili. Si verifica se il riporto è stato eseguito sul bit del segno ma non è stato portato fuori, o viceversa; più semplicemente, se i due bit più a sinistra sulla riga dei riporti non sono entrambi 0 o 1

Vediamo un esempio di addizione a 4 bit di 7 e 3:

01110 (riporto)
0111 + (7)
0011 = (3)
=============
1010 (-6)
In questo caso, come si può notare dal riporto presente solo sul bit più significativo, si è in presenza di overflow, per cui il risultato non è 10 (come sarebbe corretto) ma -6, infatti il massimo numero positivo rappresentabile in complemento a due su quattro bit è 7 (con n=4: (2^(n-1) – 1) = 7).

Rappresentazione dei numeri razionali
I numeri razionali sono dotati di una parte intera (prima della virgola) e una parte frazionaria (dopo la virgola).
Per esempio, il numero 00101001011.10110, ove la parte intera consta di 11 bit e la parte frazionaria di 5, corrisponde al numero reale 331.6875. Questa rappresentazione viene detta in virgola fissa, perché un numero fisso di cifre viene dedicato, rispettivamente alla parte intera e a quella frazionaria.

Conversione di numeri frazionari da base 2 a base 10: come per gli interi

101.01 = 1×2^2 + 0x2^1 + 1×2^0 + 0x2^(-1) + 1×2^(-2) = 4 + 0 + 1 + 0 + 0.25 = 5.25

perché 2^(-1) = 1/2 = 0.5, 2^(-2) = 1/22 = 0.25 e in generale 2^(-n) = 1/2^n

Conversione di numeri frazionari da base 10 a base 2:
Per la parte intera si fa la solita codifica binaria; invece, per la parte frazionaria si effettuano delle moltiplicazioni in sequenza. Lo vedrete meglio con un esempio
es: 5.125
Parte intera: 101
Parte decimale:
0.125 * 2 = 0.25 => 0 riporto 0.25
0.25 * 2 = 0.5 => 0 riporto 0.5
0.5 * 2 = 1 => 1
Quindi 5.125 => 101.001

9.0625 (per la parte frazionaria ci fermiamo al 4 bit effettuando se necessario un troncamento che porterebbe ad un errore)
Parte intera: 1001
Parte decimale:
0.0625 * 2 = 0.125 => 0 riporto 0.125
0.125 * 2 = 0.25 => 0 riporto 0.25
0.25 * 2 = 0.5 => 0 riporto 0.5
0.5 * 2 = 1 => 1 riporto 0

Quindi 9.2486 = 1001.0001

Una seconda rappresentazione, detta in virgola mobile (floating point), utilizza la notazione esponenziale per la codifica dei numeri reali. In questa rappresentazione vengono associati a ciascun numero reale due numeri; il primo numero, m, è detto mantissa; esso viene interpretato come numero frazionario, cioè definito nell’intervallo compreso tra -1 e 1 , in aggiunta un bit separato consente di rappresentare il segno della mantissa. Il secondo numero, n, rappresentato come un intero con segno, è detto caratteristica, e viene usato come esponente e indica la posizione della virgola. La formula che esprime il numero r in funzione di m e di n è la seguente:
r = m * b^n
dove b è la base utilizzata nella notazione esponenziale.

Esempio in base 10 : il numero 331.256 può essere rappresentato in più modi
(0.331256, 3) cioè 0.331256 * 10^3 forma normalizzata
(0.0331256, 4) cioè 0.0331256 * 10^4
(33125.6, -2) cioè 33125.6 * 10^(-2)
Nella forma normalizzata, la mantissa ha la prima cifra significativa (diversa da zero) subito dopo la virgola.

In base 2 la situazione è del tutto analoga.
Es: in base 2, il numero positivo 101.011 (che vale 5.375 in base 10) ha varie rappresentazioni in virgola mobile, come:
(0.101011,+3), cioè 0.101011*2^3 forma normalizzata
(0.0101011,+4), cioè 0.0101011*2^4
(101011.0,-3), cioè 101011.0*2^(-3)

Ora, per rappresentare numeri in virgola mobile su un calcolatore dobbiamo fissare un numero di bit per il valore assoluto della mantissa e un numero di bit per l’esponente in complemento a 2.
Se volessimo rappresentare un numero negativo ricordiamoci che un bit è riservato per questo compito e si trova all’inizio.
Dunque se volessimo rappresentare un numero, con 8 bit a disposizione, useremo 3 bit per l’esponente e 4 per la mantissa, più uno che viene lasciato per il segno .

_ / _ _ _ / _ _ _ _ (8bit)
segno esponente mantissa

Come ricavare un numero in base 10 da una rappresentazione in virgola mobile?
Tenendo ancora buona la suddivisione degli 8 bit, con 3 bit per esponente e 4 per mantissa, consideriamo questo esempio.
Es: 1 010 1010 (segno 1, esponente 010, mantissa 1010)
1) Converto l’esponente (in complemento a 2 su tre bit) in base 10: 010 vale +2;
2)Aggiungo 0. (0 virgola) prima della mantissa (che deve cominciare con 1). Quindi 1010 diventa 0.1010;
3) Sposto la virgola di un numero di posizioni pari all’esponente verso destra se positivo, verso sinistra se negativo. Quindi poiché l’esponente è +2, 0.1010 diventa 10.10;
4) Converto il numero frazionario in base 10: 10.10 vale 2.5;
5) Se il bit del segno è 1, prendo l’opposto: 1 010 1010 è -2.5.

Altro esempio, con mantissa = 6 e caratteristica = 4.
Es: 0 1001 101111 (segno1, esponente 1101, mantissa 101111)
1) L’esponente (in complemento a 2 su quattro bit) vale -3;
2) La mantissa con virgola diventa 0.101111;
3) Sposto la virgola di 3 posizioni verso sinistra: diventa 0.000101111; 1/16 + 1/64 + 1/128 + 1/256 + 1/512
4) Converto in base 10: 0.000101111 = 1/16 + 1/64 + 1/128 + 1/256 + 1/ 512 = 0.091796875
5) Il bit del segno è 0, quindi 1 010 1010 vale 0.091796875

Per rappresentare invece un numero decimale con la notazione in virgola mobile bisogna seguire questi passaggi.
Fissiamo mantissa = 4 e caratteristica = 3
Prendiamo come numero -0.3125
1) Se il numero è negativo, metto 1 nel bit del segno e considero il valore assoluto. Quindi continuo con 0.3125.
2) Converto il numero razionale in base 2: 0.3125 diventa 0.0101 in base 2;
3) Prendo come mantissa i primi 4 bit a partire da quello più significativo (il primo 1 da sinistra); aggiungo zeri se necessario; eventuali 1 dopo i primi 4 bit vengono persi con conseguenti errori di troncamento. Quindi la mantissa di 0.0101 è 1010.
4) Per l’esponente: conto di quante posizioni devo spostare la virgola verso sinistra per arrivare a sinistra del primo 1. L’esponente di 0.0101 è -1 perché devo spostare la virgola a destra di una posizione. In complemento a 2 su 3 bit, -1 vale 111.
5) Quindi -0.3125 viene rappresentato come 1 111 1010.

Per oggi è tutto. Speriamo che questa spiegazione possa servirvi nel futuro per gli esami. Se avete qualche dubbio non esitate a contattarci.

Please follow and like us: