Rappresentazione dei numeri naturali e interi in un computer
Sistemi di numerazione
Nella vita di tutti i giorni siamo abituati a pensare ai numeri da \(0\) a \(9\) e a scrivere numeri più grandi combinando queste cifre. Il sistema che usiamo, in modo ormai naturale, è il sistema indo-arabo di numerazione posizionale in base 10. Questo però è solo uno dei modi di scrivere i numeri. Ad esempio, a tutti sarà familiare il sistema di numerazione romano: I, II, III, IV, V, VI, VII, VIII, IX, X, etc. Questo è un altro insieme di regole per scrivere i numeri. La prima cosa che dobbiamo chiarirci quindi è che una cosa sono i numeri, ed un altra i sistemi di numerazione, che sono insiemi di regole che ci diamo per rappresentare i numeri stessi tramite simboli. I simboli che usiamo per rappresentare i numeri si chiamano numerali. Ad esempio 1, I, 一, uno, ena, sono diversi numerali che rappresentano lo stesso numero, rispettivamente nel sistema indo-arabo, romano, cinese tradizionale, in italiano e in sloveno.
Indipendentemente dal simbolo usato, il numero resta lo stesso. Alcuni sistemi di numerazione rendono però molto più semplice effettuare le operazioni aritmetiche. È questo il caso del sistema indo-arabo, specialmente in confronto con quello romano. Non è un caso difatti che la traduzione in latino del trattato "sul calcolo con i numeri hindi" di Al-Khwārizmī (sempre lui) nel XII secolo, e la forte promozione del sistema arabo ad opera di Fibonacci nel XIII siano collegati ad uno sviluppo della matematica in Europa.
Gli ingredienti di un sistema di numerazione sono un insieme finito di simboli, le cifre, ed un'insieme di regole che faccia corrispondere un numero alla disposizione di questi simboli. Nei sistemi posizionali come quello indo-arabo, i numeri si ottengono mettendo in ordine le cifre finché non sono esaurite e poi aggiungendo la seconda più piccola a sinistra per far continuare la successione. Quando si esauriscono nuovamente le cifre a destra, si passa al simbolo seguente a sinistra, fino a finire nuovamente tutte le cifre. A quel punto si ripete il procedimento aggiungendo un altro simbolo a sinistra, e via così.
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
...
90 91 92 93 94 95 96 97 98 99
100 101 102 103 104 105 106 107 108 109
Sistemi posizionali
Il sistema indo-arabo che usiamo per scrivere i numeri è un sistema posizionale. Il valore di un numerale dipende dalla posizione relativa delle cifre, con le cifre a sinistra che hanno più "peso" di quelle a destra (questa convenzione è stata introdotto perché il latino ed i linguaggi europei si scrivono da sinistra a destra, nel sistema originale, scrivendosi l'arabo da destra a sinistra, era il contrario). Siccome il sistema è in base 10, abbiamo 10 cifre, da 0 a 9, e per ogni posizione la cifra corrispondente moltiplica una potenza di 10: \(10^0\) per la cifra più a destra, \(10^1\) la seconda da destra, \(10^2\) la successiva, e così via. Il numerale 1023 per esempio rappresenta l'espressione
Più in generale, un numerale composto di \(m\) cifre \((a_0, a_1,\ldots,a_{m-1})\) rappresenta il numero
Oltre a rendere estremamente facile scrivere i numeri, i sistemi posizionali rendono immediato anche sommarli. Diciamo di avere due numeri \(A\) e \(B\) di \(m\) cifre (il caso in cui abbiano un numero diverso di cifre dovrebbe essere ovvio). La somma dei si può scrivere facilmente come
facendo attenzione al fatto che \(a_i + c_i\) possono risultare in un valore \(d_i >9\), nel qual caso si riporta un \(1\) a sinistra, per indicare che la cifra associata alla potenza di \(10\) successiva è aumentata.
Quanto visto sopra resta valido indipendentemente dal numero di cifre, la base, usata dal nostro sistema posizionale. Se abbiamo \(b\) cifre, con \(b\geq 2\) possiamo comunque scrivere qualsiasi numero come una serie di potenze di \(b\):
dove usiamo il pedice \(b\) per indicare in che base è espresso il numerale.
Due basi che vedremo e che si usano comunemente sia in elettronica che in informatica sono la base 2, cioè i numeri binari e la base 16, o esadecimale. La loro comodità deriva dal fatto che, come abbiamo visto, i calcolatori elettronici sono digitali e binari: i loro componenti elettronici possono rappresentare solo due stati discreti, lo \(0\) e l' \(1\).
Il sistema binario
Se \(b=2\) ho solo due cifre possibili: \(0\) e \(1\). I primi 10 numeri diventano quindi:
I numeri in base 2, naturalmente, rappresentano l'espressione
Questa ci permette di esprimere immediatamente i numeri binari in base decimale. Poiché 10>2, è immediato esprimere le potenze \(2^i\) in questa base. Per esempio:
Cambiare base
La questione è leggermente più complicata se vogliamo passare da una base più grande ad una più piccola, ad esempio se vogliamo esprimere il numero \(A_{10} = 41\) in base 2.
C'è un semplice algoritmo che ci permette di ottenere il numero che desideriamo. Proviamo a scomporre il numero direttamente in potenze di 2:
Per numeri piccoli, ricordarsi le potenze di 2 è banale e quindi è facile fare il conto. Come facciamo però a cambiar base nel caso di un numero qualsiasi?
L'algoritmo di cambio base è il seguente. Vogliamo trovare i coefficienti \(c_0,\ldots,c_{m-1}\) che ci permettano di scrivere il numero \(A_{10}\) in base \(2\):
con \(b=2\). L'algoritmo resta valido per altre basi \(b \lt 10\)
Definiamo, in base 10, \(N_0 \equiv A\) e \(N_{i+1}\equiv \lfloor\frac{N_i}{b}\rfloor\) è il risultato della divisione intera di \(N_i\) per \(b\). Sia \(r_i = N_i - N_{i+1}b\) il resto di questa divisione.
Notiamo che i resti in questo approccio sono sempre minori di \(b\):
Se \(b=2\), gli \(r_i\) possono prendere solo come valori \(0\) e \(1\), se \(b=3\) possono assumere valori \(0,1,2\), etc.
L'algoritmo procede calcolando \(N_1,\ldots,\) finché non si raggiunge un valore \(N_{m-1} \in \{0,1\}\). Iterando, notiamo che possiamo scrivere:
I resti sono quindi i nostri coefficienti \(c_i\), e ricordando che si scrivono dal più piccolo al più grande da destra verso sinistra, il numero risultante è
Applichiamolo per calcolare il numero \(41_{10}\) in base 2.
- \(N_0\) = 41;
- \(N_1 = 41 / 2 = 20\), \(r_0 = 1\);
- \(N_2 = 20/2 = 10\), \(r_1 = 0\);
- \(N_3 = 10/2 = 5\), \(r_2 = 0\);
- \(N_4 = 5/2 = 2\); \(r_3 =1\);
- \(N_5 = 2/2 = 1\); \(r_4 = 0\);
- \(N_6 = 1/2 = 0\); \(r_5 = 1\).
Il risultato finale è
come trovato in precedenza.
La base esadecimale
In informatica si usano spesso tre basi per scrivere i numeri (e qualunque altra cosa). Quella binaria, quella ottale (base 8), e quella esadecimale (base 16). Qui ci limiteremo a vedere la base esadecimale, ma le stesse considerazioni valgono per la base 8. Il vantaggio di queste due basi, soprattutto della base 16, è che ci permettono di scrivere numeri molto grandi usando molti meno simboli della base 2. Sono quindi più comodi da leggere per noi utenti. Il loro utilizzo è anche collegato al fatto che, storicamente, la memoria dei computer è suddivisa in unità di 8 bit ciascuna, chiamate byte. Un byte contiene \(2^8 = 256\) diversi stati, e rappresentare il contenuto di uno o due byte in notazione binaria diventa piuttosto ingombrante:
Rappresentare questi numeri in base 10 ci costringerebbe a continui cambi di base piuttosto dispendiosi. La soluzione consiste nell'usare una base che sia una potenza di 2, come la base 8 o la base 16. Vediamo quest'ultima. Le cifre possibili sono:
base 16 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
base 10 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
Per distinguere i numeri esadecimali da quelli decimali, in Unix si indicano con il prefisso 0x. Per cui 0x51 vale \(41_{16} = 4\cdot16_{10}^1 + 1\cdot16_{10}^0 = 65_{10}\) e 51 vale \(51_{10}\).
La conversione da binario a esadecimale è immediata, perché le cifre esadecimali rappresentano \(2^4\) possibili valori e si possono quindi rappresentare con \(4\) bit:
base 16 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
base 2 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111
Di fatto, se chiamiamo \(B\) la base esadecimale e \(b\) quella binaria, vale \(B=b^4\), quindi un numero di 4 bits si può scrivere come una sola cifra esadecimale:
Se abbiamo 8 bits per le potenze da \(4\) a \(7\) vale:
e così via. In sostanza, per passare da base 16 a base 2, basta rappresentare le cifre in base 16 come numeri di 4 bit, come fatto sopra, mentre per passare da base 2 a base 16 basta raggruppare le cifre binarie, da destra verso sinistra, in gruppi di 4, aggiungendo degli zeri a sinistra per arrivare a completare l'ultimo gruppo. Ad ogni gruppo di 4 bits si associa poi la cifra esadecimale corrispondente.
Question
Provare che per passare da base 2 a base 8 basta raggruppare i bits in gruppi di 3.
Addizioni e le sottrazioni
Addizioni e sottrazioni si fanno in colonna, seguendo lo stesso algoritmo a cui siamo abituati, in base 10, dalle elementari. Si scrivono i due addendi uno sopra l'altro, facendo combaciare le cifre corrispondenti alle stesse potenze di \(b\) e si sommano le cifre a iniziare da quella più a destra. Se la somma è più grande di \(b\), si scrive il risultato modulo \(b\) e si riporta un \(1\) a sinistra. Per la base \(b=2\) quindi si seguono queste regole:
Vediamo un esempio nell'immagine qui sotto: \(11011_2 + 101_2 = 27_{10} + 5_{10}\)
In effetti la loro somma fa \(32_{10} = 100000_2\). Notare che stiamo usando un bit in più.
Le sottrazioni seguono anch'esse lo schema noto per quelle in base 10, ma dobbiamo fare attenzione al fatto che abbiamo solo \(b=2\) cifre. Le regole quindi sono:
Nel caso del riporto, va aggiunto un uno in tutte le colonne tra quella da cui abbiamo riportato e quella dove stiamo riportando, come si vede nell'immagine qui sotto.
Di nuovo, \(1100_2 - 11_2 = 12_{10} - 3_{10} = 9_{10}\), il conto fatto in base 2 è quindi corretto.
Rappresentazioni dei numeri naturali su un computer
Breve intermezzo: la memoria
Nell'esempio della somma visto poco sopra, abbiamo visto che è necessario aggiungere un bit per rappresentare il risultato. Tuttavia, nei computer reali questo in genere non è possibile. Questo per due motivi. Il primo è che la memoria di una macchina è una risorsa finita, per quanto ampia; ed il secondo è il fatto che, per motivi di progettazione dei microprocessori, i bit in cui sono salvati dati e operazioni sono raggruppati in unità minime dette parole (words).
La dimensione delle parole, in sostanza, è fissata dalla dimensione dei registri del microprocessore. Questi sono unità di memoria estremamente veloci, presenti direttamente sulla CPU, in cui vengono salvati i dati e le operazioni da eseguire al prossimo step. Nei computer moderni le parole sono sempre di 64 bit. La dimensione delle parole limita la quantità di numeri che possiamo salvare in una di queste. In questo caso, saranno \(2^{64}\) valori diversi. In linguaggi come il C, come vedremo, sono possibili tipi di dato di dimensione più piccola, cioè 4,8,16,32 bit, così come più grandi, 128.
Overflow
Lavorare su parole di dimensioni variabili sarebbe estremamente complicato, quindi si preferisce considerare parole di dimensione \(w\) fissa. Quale che sia questa dimensione, la questione fondamentale è che in una parola di \(w\) bits possiamo rappresentare al massimo \(2^w\) elementi diversi. Se consideriamo numeri naturali, questi corrispondono ai numeri compresi tra \(0\) e \(2^{w} - 1\). Questo vuol dire che se sommiamo ad esempio \(2^w-1 + 1\) il risultato non sarà rappresentabile. Si verifica un overflow.
Consideriamo il seguente esempio, in cui i numeri sono rappresentati con parole di 4 bit. Queste permetteno di rappresentare \(2^4 = 16\) stati, e quindi i numeri tra \(0\) e \(15\). Sommando \(1011_2 = 11_{10}\) e \(1001_2 = 9_{10}\) otteniamo chiaramente un numero più grande di 15. Il risultato si può scrivere solo con 5 bit, ma le nostre parole ne misurano 4. Di conseguenza, il bit più significativo viene perso, perché va oltre le dimensioni della parola:
Nel caso della somma qui sopra quindi, abbiamo che \(1011_2 + 1001_2 = 0100_2 = 4_{10}\). In generale, il risultato della somma di due addendi \(a\) e \(b\) scritti in parole di \(w\) bits valedove $ n \mod m $ è quel numero naturale tale che
cioè il resto della divisione euclidea tra numeri naturali.
Rappresentazione dei numeri interi
Abbiamo visto come rappresentare i numeri naturali, incluso lo zero, in parole di \(w\) bits. In generale però vogliamo rappresentare i numeri interi, inclusi quindi valori minori di 0. Resta sempre vero il fatto che con parole di \(w\) bits possiamo rappresentare al massimo \(2^w\) stati e dobbiamo scegliere quanti di questi saranno numeri negativi e quanti numeri positivi. Come vedremo, questo cambia a seconda di come decidiamo di rappresentare i nostri interi. Ci sono vari modi possibili, ma le tre rappresentazioni più comuni sono la sign-magnitude, quella in complemento e quella in eccesso a N .
Notazione sign-magnitude
Questa notazione si basa sull'idea intuitiva che un numero negativo \(-n\) si può rappresentare come \(-1\cdot n\), dove \(n > 0\). In parole di \(w\) bits, il primo (più significativo) bit rappresenta il segno (0 per positivo, 1 per negativo), mentre i rimanenti \(w-1\) bits rappresentano la magnitudine (il valore assoluto del numero).
Per esempio, con parole di 4 bit: - \(0101_2\) rappresenta \(+5\) (bit di segno 0, magnitudine 101 = 5) - \(1101_2\) rappresenta \(-5\) (bit di segno 1, magnitudine 101 = 5)
Vantaggi: - Semplice e intuitiva da comprendere - La magnitudine si legge facilmente
Svantaggi: - Esiste lo zero negativo (\(1000_2 = -0\)) oltre allo zero positivo (\(0000_2 = +0\)), due rappresentazioni dello stesso numero - L'aritmetica è complicata: somma e sottrazione richiedono logica speciale per il segno - Con \(w=4\) bits possiamo rappresentare solo i numeri da \(-7\) a \(+7\) (16 stati, due rappresentano lo zero)
Intervallo: Con \(w\) bits, si possono rappresentare numeri da \(-(2^{w-1}-1)\) a \(+(2^{w-1}-1)\).
Notazione in complemento a 2
La rappresentazione in complemento a 2 è quella più utilizzata nei computer moderni. L'idea è di pensare ai numeri negativi come il "complemento" dei positivi rispetto a \(2^w\).
In complemento a 2 con \(w\) bits: - I numeri positivi si rappresentano normalmente: il bit più significativo è 0 - Per rappresentare \(-n\) (con \(n > 0\)), si calcola \(2^w - n\)
Alternativamente (e più semplicemente), il complemento a 2 di un numero si ottiene: 1. Invertendo tutti i bit (0 diventa 1 e 1 diventa 0) 2. Aggiungendo 1 al risultato
Esempio con 4 bits:
Vogliamo rappresentare \(-5\). Sappiamo che \(5 = 0101_2\).
- Invertiamo i bit: \(0101_2 \rightarrow 1010_2\)
- Aggiungiamo 1: \(1010_2 + 1 = 1011_2\)
Quindi \(-5\) in complemento a 2 su 4 bits è \(1011_2\).
Verifichiamo: interpretando \(1011_2\) come complemento a 2, il suo valore è: $\(-(1 \cdot 2^3) + (0 \cdot 2^2) + (1 \cdot 2^1) + (1 \cdot 2^0) = -8 + 2 + 1 = -5 \checkmark\)$
Più in generale, un numero rappresentato in complemento a 2 come \((b_{w-1}, b_{w-2}, \ldots, b_1, b_0)\) ha valore:
Notare che il bit più significativo ha peso negativo.
Vantaggi: - Una sola rappresentazione dello zero: \(0000_2 = 0\) - L'aritmetica è semplice: la somma si fa normalmente, anche con numeri negativi - Non serve logica speciale per gestire il segno - Con \(w=4\) bits possiamo rappresentare tutti i 16 numeri da \(-8\) a \(+7\)
Intervallo: Con \(w\) bits, si possono rappresentare numeri da \(-2^{w-1}\) a \(+(2^{w-1}-1)\).
Esempio di somma in complemento a 2 (4 bits):
Calcoliamo \(5 + (-3)\):
- \(5 = 0101_2\)
- \(-3\): complemento a 2 di \(3 = 0011_2\) è: \(1111_2 - 0011_2 + 1 = 1101_2\)
Somma:
Scartando il bit di riporto oltre \(w=4\) bits, abbiamo \(0010_2 = 2_{10}\), che è corretto!
Overflow nel complemento a 2
L'overflow si verifica quando il risultato di un'operazione non rientra nell'intervallo rappresentabile. In complemento a 2, l'overflow si verifica quando: - Sommando due numeri positivi il risultato ha il bit di segno pari a 1 (risultato negativo) - Sommando due numeri negativi il risultato ha il bit di segno pari a 0 (risultato positivo)
Esempio (4 bits): \(7 + 1\)
- \(7 = 0111_2\)
- \(1 = 0001_2\)
Somma:
Risultato: \(1000_2 = -8\) (in complemento a 2), mentre il risultato vero sarebbe \(8\). Poiché stiamo sommando due numeri positivi ma il risultato è negativo, si è verificato un overflow. Il bit di segno ha "cambiato segno" inaspettatamente.
Notazione in eccesso a N
La notazione in eccesso a N (o bias) è un'altra rappresentazione dei numeri interi. In questa notazione, a ogni valore binario si associa il numero ottenuto sottraendo un valore fisso detto eccesso o bias.
Con \(w\) bits e bias \(N = 2^{w-1}\), un numero rappresentato come \((b_{w-1}, \ldots, b_0)\) ha valore:
Esempio con 4 bits (bias = \(2^3 = 8\)):
- \(0000_2 = 0_{10} - 8 = -8\)
- \(0001_2 = 1_{10} - 8 = -7\)
- \(0111_2 = 7_{10} - 8 = -1\)
- \(1000_2 = 8_{10} - 8 = 0\)
- \(1111_2 = 15_{10} - 8 = +7\)
Intervallo: Con \(w\) bits e bias \(2^{w-1}\), si possono rappresentare numeri da \(-2^{w-1}\) a \(+(2^{w-1}-1)\), uguale al complemento a 2!
Vantaggi: - Una sola rappresentazione dello zero - Il confronto tra numeri è semplice: basta confrontare le stringhe binarie (il numero più grande ha la rappresentazione binaria più grande) - Semplice nel confronto ordinale
Svantaggi: - L'aritmetica è meno naturale (bisogna aggiustare il bias dopo le operazioni) - Non è comoda come il complemento a 2 per le operazioni aritmetiche
Utilizzo: La notazione in eccesso è utilizzata principalmente negli esponenti dei numeri in virgola mobile (standard IEEE 754).
Comparazione delle tre notazioni (4 bits)
| Valore binario | Sign-magnitude | Complemento a 2 | Eccesso a 8 |
|---|---|---|---|
| 0000 | 0 | 0 | -8 |
| 0001 | 1 | 1 | -7 |
| 0010 | 2 | 2 | -6 |
| 0011 | 3 | 3 | -5 |
| 0100 | 4 | 4 | -4 |
| 0101 | 5 | 5 | -3 |
| 0110 | 6 | 6 | -2 |
| 0111 | 7 | 7 | -1 |
| 1000 | -0 | -8 | 0 |
| 1001 | -1 | -7 | 1 |
| 1010 | -2 | -6 | 2 |
| 1011 | -3 | -5 | 3 |
| 1100 | -4 | -4 | 4 |
| 1101 | -5 | -3 | 5 |
| 1110 | -6 | -2 | 6 |
| 1111 | -7 | -1 | 7 |
Esercizi
Esercizio - Conversione Sign-Magnitude
Rappresentare i seguenti numeri in notazione sign-magnitude con 8 bits:
- \(+42\)
- \(-17\)
- \(-128\)
- \(+127\)
Esercizio - Conversione Complemento a 2
Rappresentare i seguenti numeri in complemento a 2 con 8 bits:
- \(+42\)
- \(-17\)
- \(-128\)
- \(+127\)
Qual è il massimo e il minimo valore rappresentabile?
Esercizio - Somma in Complemento a 2
Eseguire le seguenti somme in complemento a 2 con 8 bits. Indicare se si verifica overflow:
- \(100 + 27\)
- \(-50 + 30\)
- \(100 + (-20)\)
- \(127 + 1\)
- \(-128 + (-1)\)
Esercizio - Conversione tra notazioni
Per il numero \(11010101_2\) (8 bits), determinare il valore in:
- Notazione sign-magnitude
- Notazione complemento a 2
- Notazione eccesso a 128
Esercizio - Aritmetica in eccesso a N
Con 4 bits in eccesso a 8, eseguire:
- Rappresentare \(-3\) e \(+2\)
- Quale è la loro somma in binario (senza aggiustamenti)?
- Aggiustare il risultato sottraendo il bias due volte per ottenere il risultato corretto
Challenge
Ricerca: In quali linguaggi di programmazione è usato il complemento a 2? Esiste ancora qualche sistema che usa sign-magnitude?