Rappresentazione
Dati
Rappresentare i dati
• E’ abbastanza semplice usando pochi transistor creare un dispositivo
bistabile.
• Tali dispositivi, sono circuiti elettronici, in grado di ‘ricordare’ il loro ‘stato’
• Sono detti bistabili perché possono avere solo 2 stati.
Acceso, Spento
0, 1
Qualunque calcolatore elettronico memorizza i dati usando dispositivi del
genere.
Rappresentare i dati
• Nella prima lezione abbiamo detto che un calcolatore programmabile
deve memorizzare
• DATI
• ISTRUZIONI
• Abbiamo a disposizione solo due valori!!! 0 e 1. COME SI FA?
• Dobbiamo trovare delle codifiche per memorizzare con lo stesso circuito
numeri interi, positivi e negativi, con la virgola e senza e caratteri.
Codifica di numeri in base 2
• Pensiamo alla base 10, il numero 42 è una sequenza di cifre, la cui posizione indica in realtà l’ordine di
grandezza.
• Di fatto 42 = 10*4 + 1*2 = 4 ⋅ 10! + 2 ⋅ 10" = 4 ⋅ 𝐵! + 2 ⋅ 𝐵" dove con B, in questo caso abbiamo 10.
• Con la stessa strategia possiamo memorizzare numeri usando solo 2 cifre. Convertiamo proprio 42.
• [42]!" = 2# + 2$ + 2! = 32 + 8 + 2 = 101010 %
Codifica di numeri in base 2
• Scelta la base B in cui rappresentiamo il numero posso scrivere, per una codifica posizionale
[𝑎& 𝑎&'! 𝑎&'% … 𝑎" ]( = 0 𝑎& 𝐵&
• Proviamo con B=10
1236 = 1 ⋅ 10$ + 2 ⋅ 10% + 3 ⋅ 10! +6 ⋅ 10" = 1000+200+30+6
Comodità della base 2
• Possiamo contare con una mano fino a 31 e con 2
mani fino a 1023!!
• Non servono le tabelline!!
0*0 = 0
0*1 = 0
1*1 = 1
• Le operazioni si fanno ‘come ci hanno insegnato a
scuola’
Conti in base 2 - Somma
101+11=? Controlliamo se torna!
Abbiamo sommato
101+
101=4+1=5
11 11=2+1 = 3
1000 5+3=8
1000 % = 2$ + 0 ⋅ 2% + 0 ⋅ 2! + 0 ⋅ 2" = 8 !"
• 1+1 fa 10, ovvero 0 con riporto di 1
• 1+0 fa 1, ovvero 1 senza riporto.
Conti in base 2 - Prodotto
101 ⋅ 10=? Controlliamo se torna!
Abbiamo moltiplicato
101x
101=4+1=5
10 10= 2
000+ 5*2=10
101//
1010 % = 2$ + 0 ⋅ 2% + 1 ⋅ 2! + 0 ⋅ 2" = 10 !"
1010
• Ancora più semplice! 0*0, 0*1=0 e 1*1=1
Conversione da base 10 a base 2
• La conversione si può fare usando la regola dei ‘resti successivi’
' '
[𝑎! 𝑎!"# 𝑎!"$ … 𝑎% ]$ = & 𝑎! 2! = 𝑎% + 2 & 𝑎!(# 2!
!&% !&%
• Ricordiamo che la divisione intera è l’operazione che dato un dividendo N e un divisore D definisce due
numeri Q e R tali che:
𝑁 =𝑄⋅𝐷+𝑅
• Nel nostro caso D=2 e R=𝑎"
Conversione da base 10 a base 2
Conversione da base 10 a base 2
• La conversione si può fare usando la regola dei ‘resti successivi’
' '
[𝑎! 𝑎!"# 𝑎!"$ … 𝑎% ]$ = & 𝑎! 2! = 𝑎% + 2 & 𝑎!(# 2!
!&% !&%
• Applichiamo ricorsivamente al quoziente appena ottenuto
' '
& 𝑎!(# 2! = 𝑎# + 2 & 𝑎!($ 2!
!&% !&%
• Ad ogni divisione per la base, cioè 2, il resto è l’ultima cifra nella rappresentazione posizionale.
Conversione da base 10 a base 2
• Organizziamo I quozienti e I resti successivi in una diagonale
125 !" = 1111101 %
Base Esadecimale
• E’ molto complesso memorizzare cifre in rappresentazione binaria.
• La rappresentazione in base 16 ci consente di rappresentare le stringhe di bit in maniera compatta
• Per lavorare in base 16 occorrono 15 simboli oltre lo 0: [0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F]
16 !" = 10 !) = 0001 0000 %
75 !" = 0100 1011 % = 4B !)
Interi senza segno
• Possiamo quindi dato un numero limitato di bit N rappresentare interi senza segno con valori compresi
nell’intervallo 0,2* − 1 .
*'!
0 𝑎& 2&
&+"
• Un intero su 8bit, ovvero su un byte potrà rappresentare numeri tra 0 e 255.
• Come ovvio più bit si avranno a disposizione maggiore sarà l’intervallo di valori rappresentabile
Interi con segno
• Per rappresentare un intero con segno ad esempio -12 occorre codificare questa informazione
aggiuntiva.
• Una soluzione immediata potrebbe essere usare un bit per indicare il segno.
• Così facendo però si avrebbero due valori per lo zero, -0 e +0
Interi con segno
• Per i numeri negativi nella pratica si utilizza il ‘complemento a 2’. Una rappresentazione posizionale in
cui il bit più significativo ha peso negativo
*'%
−𝑎*'! 2*'! + 0 𝑎& 2&
&+"
• In python usiamo questa rappresentazione quando ad esempio scriviamo
>> value = -12
Interi con segno
• Per i numeri negativi nella pratica si utilizza il ‘complemento a 2’. Una rappresentazione posizionale in
cui il bit più significativo ha peso negativo
*'%
−𝑎*'! 2*'! + 0 𝑎& 2&
&+"
• Usando il complemento a 2 si rappresentano I valori tra −2*'! , 2*'! − 1
• Con 8 bit ad esempio avremo valori in [-128,127], mentre se usiamo tutti gli 8 bit per numeri positivi il
range è [0,255]
Interi con segno )"$
−𝑎)"# 2)"# + & 𝑎! 2!
• Il complemento a due si calcola facilmente: !&%
1. Invertire tutti i bit
2. Aggiungere 1
• Rappresentiamo il numero -23. Mi servono almeno 6 bit: [-32,31]
23 !" = 010111 % =
= 101000 ,-! +1=
= 101001 ,-% = −2# + 2$ + 2" = −23
• Rappresentiamo il numero 8. 8 !" = 001000 %
• Come calcolo 8-23?
Interi con segno
• Rappresentiamo in 8 bit il numero -23. 23 !" = − 00010111 % = 11101000 ,-! = 11101001 ,-%
• Rappresentiamo il numero 8. 8 !" = 00001000 %
• Come calcolo 8-23?
1110 1001+
0000 1000
1111 0001
• Risultato negativo come atteso. Proviamo a convertirlo per controllare il risultato:
1111 0001 ,-% − 1 → 1111 0000 ,-! → − 0000 1111 % → − 15 !"
Interi con segno
• Con un circuito sommatore progettato per sommare interi di N bit posso sommare e sottrarre senza
modifiche a patto di usare il complemento a 2 per i numeri negativi.
A
C
B
Overflow e Underflow
• Gli interi così rappresentati hanno un massimo e minimo valore rappresentabile.
• Senza prendere alcuna contromisura non sarebbe possibile fare qualcosa come:
>>2**63+1
In python gli interi (int) sono rappresentati a precisione arbitraria.
• python finché una variabile è mantenibile su 64 bit la rappresenta come visto sinora.
• Se la variabile ‘sfora’ i 64 bit, l’interprete rappresenta l’intero come una sequenza di interi a 30 bit
123456789101112131415 à
Numeri con virgola mobile
• E’ una rappresentazione per modellare i numeri razionali
• L’idea è rappresentare i numeri nella forma (segno) x mantissa x B .
In base 10 avremmo qualcosa del tipo: 0.00121= (+1)x(0.121)*10'%
Secondo lo standard IEEE 754 la rappresentazione a 32 bit di un float è la seguente:
s e m
1 8 23
Usiamo questa rappresentazione in python quando dichiariamo:
pi=3.14
Numeri con virgola mobile
• Il segno si rappresenta con un bit: 1 per i negativi 0 per i positivi.
• La mantissa viene rappresentata con 23 bit
• I numeri vengono portati in forma ‘normalizzata’ per evitare ambiguità al calcolatore.
In base 10 per esempio il numero 234.2 si può vedere come 0.2342 ⋅ 10$ oppure 2342 ⋅ 10'!
In forma normale la mantissa rispetta il vincolo
1≤𝑚<𝐵
Numeri con virgola mobile
• In forma normale la mantissa rispetta il vincolo
1≤𝑚<𝐵
Quindi in base 2 sarà vero che 1 ≤ 𝑚 < 2 e quindi è un numero rappresentabile come:
/
𝑚 = 0 𝑎& 2'&
&+"
Per ottenere la parte frazionaria di un numero reale si può procedere nel seguente modo
0. 𝑎! 𝑎% … 𝑎& % = 𝑎! 2'! + 𝑎% 2'% … 𝑎& 2'&
Moltiplicando iterativamente per 2 ottengo le cifre (0 o 1) della parte frazionaria.
0.625*2=1.250
0.250*2=0.5 0.625 = 0.101 !
0.5*2 =1.0
Numeri con virgola mobile
• Invece che rappresentare la caratteristica direttamente in complemento a due si codifica un intero a 8
bit e detto esponente secondo la seguente
𝑒 = 𝑐 + 20 − 1
Quindi ad esempio e=178 allora c=178-127=51, il numero sarà s ⋅ m ⋅ 2#!
In sintesi
−1 1 ⋅ 1. 𝑚 ⋅ 22'!%0
Possiamo rappresentare caratteristiche tra [-127,128]. Per avere un’idea tenendo conto che
2!" = 1024 ∼ 10$
2!%0 ∼ 2!" !$ = 1000!$
Un valore che supera altamente I limiti di overflow/underflow degli interi.
Numeri con virgola mobile
Conversione del valore -118.625
La parte intera la otteniamo coi resti successivi *
−1 ⋅ 1. 𝑚 ⋅ 2+,-./
118 = 1110110
s e m
La parte frazionaria moltiplicando per due iterativamente 1 10000101 1101101010000000000000
.625 = 0.101
Ricapitolando
• segno: s=1
• mantissa: m=1110110.101, m >2, quindi va normalizzata 1. 110110101⋅ 2)
• esponente: e-127 = 6 –> e = 6+127 = [133]10 = [10000101]2
Errori numeri in virgola mobile
• I numeri in virgola mobile, float, non rappresentano i razionali.
• Gli int non sono un sottoinsieme dei numeri in virgola mobile. Un intero rappresentato su più di 24 bit
non ammette un’esatta rappresentazione in virgola mobile
Caratteri e stringhe
I caratteri sono rappresentati come interi
di 8 bit.
E le stringhe sono sequenze di caratteri:
nome=‘Lorenzo’
Notare come per caratteri maiuscoli e
minuscoli occorrano due codifiche
differenti.
Il carattere ‘3’ è ben diverso dal valore 3,
in particolare il carattere ‘3’ è codificato
con un byte il cui valore visto come
decimale è 51.
ATTENZIONE
• Uno dei più gravi disastri causati da un bug software: ARIANNE 5, 1996 500 Milioni di $ di perdite
• La variabile che teneva traccia
dell’orientazione del razzo era
modellata come un floating point a 64
bit.
• In una routine questo valore veniva
convertito e trasferito su un intero a
16bit causando un overflow.
All’esame….
• Dato il numero decimale 935:
• Convertire il numero in binario mostrando lo svolgimento delle divisioni successive.
• Convertire il numero in esadecimale mostrando i passi della conversione.