Informatica
Lezione 3
Psicologia dello sviluppo e dell'educazione (laurea
magistrale)
Anno accademico: 2007-2008
Codifica dei numeri
•
•
Il codice ASCII consente di codificare le cifre
decimali da “0” a “9” fornendo in questo modo una
rappresentazione dei numeri
Per esempio: il numero 324 potrebbe essere
rappresentato dalla sequenza di byte:
00110011 00110010 00110100
3
2
4
•
•
Ma questa rappresentazione non è efficiente e
soprattutto non è adatta per eseguire le operazioni
aritmetiche sui numeri
Sono stati pertanto studiati codici alternativi per
rappresentare i numeri in modo efficiente ed
eseguire le usuali operazioni aritmetiche
Codifica dei numeri
(il sistema decimale)
•
La rappresentazione dei numeri con il sistema
decimale può essere utilizzata come spunto per
definire un metodo di codifica dei numeri all’interno
degli elaboratori
–
–
–
Esempio: la sequenza di cifre 324 viene interpretato
come:
3 centinaia + 2 decine + 4 unità
324 = 3 x 100 + 2 x 10
+4x1
324 = 3 x 102
+ 2 x 101 + 4 x 100
3 è la cifra più significativa
4 è la cifra meno significativa
Codifica dei numeri
(il sistema decimale)
•
In generale la sequenza cn cn-1cn-2 … c1c0 (ogni “ci”
è una cifra compresa tra “0” e “9”) viene
interpretata come:
La cifra meno
significativa
La cifra più
significativa
c0 x 100 +
(c0 unità)
c1 x 101 +
(c1 decine)
c2 x 102 +
(c2 centinaia)
…
cn-1 x 10n-1 +
cn x 10n
Codifica dei numeri
(il sistema decimale)
• La numerazione decimale quindi utilizza una
notazione posizionale basata sul numero 10
• La notazione posizionale può essere
utilizzata in qualunque altro sistema di
numerazione con base diversa di 10
– Base: il numero di cifre disponibile nel sistema
– In base 10, usiamo le dieci cifre 0, 1, 2, 3, 4, 5, 6,
7, 8, 9
Codifica dei numeri
• Nel sistema di numerazione binario (base 2) i
numeri vengono codificati utilizzando le due
cifre 0 e 1
• Nel sistema di numerazione ottale (base 8) i
numeri vengono codificati utilizzando le otto
cifre 0, 1, 2, 3, 4, 5, 6, 7
• Nel sistema di numerazione esadecimale
(base 16) i numeri vengono codificati
utilizzando le sedici cifre 0, 1, 2, 3, 4, 5, 6, 7,
8, 9, A, B, C, D, E, F
Codifica dei numeri
(il sistema binario)
• In analogia con il caso decimale la sequenza
cn cn-1cn-2 … c1c0 (ogni “ci” è la cifra “0” o la
cifra “1”) rappresenterà il numero
La cifra meno
significativa
La cifra più
significativa
c0 x 20 +
c1 x 21 +
c2 x 22 +
… +
cn-1 x 2n-1 +
cn x 2n
Codifica dei numeri
• Caso generale: considerare un sistema con base b
• La sequenza cn cn-1cn-2 … c1c0 (ogni “ci” è una cifra
del sistema) rappresenterà il numero
La cifra meno
significativa
La cifra più
significativa
c0 x b0 +
c1 x b1 +
c2 x b2 +
… +
cn-1 x bn-1 +
cn x bn
Codifica dei numeri
• Caso generale: considerare un sistema con base b
• La sequenza cn cn-1cn-2 … c1c0 (ogni “ci” è una cifra
del sistema) rappresenterà il numero
La cifra meno
significativa
La cifra più
significativa
c0 x b0 +
c1 x b1 +
c2 x b2 +
… +
cn-1 x bn-1 +
cn x bn
Se necessario,
convertiamo una
cifra ci in un numero
(per esempio, nel
sistema
esadecimale, “A”
significa “10”, “B”
significa “11”, e così
via)
Codifica dei numeri
(il sistema binario)
• Esempio: la sequenza “1011” in base 2 denota il numero
1 x 23 + 0 x 22 + 1 x 21 + 1 x 20 = 11 (in base 10)
• Esempio: la sequenza “10011” in base 2 denota il numero
1 x 24 + 0 x 23 + 0 x 22 + 1 x 21 + 1 x 20 = 19 (in base 10)
• Per evitare ambiguità si usa la notazione
10112 = 1110, 100112 = 1910
Altri basi: ottale, esadecimale
• Sistema ottale
– Utilizza una notazione posizionale basata su otto
cifre (0,1,…,7) e sulle potenze di 8
– Esempio: 1038 = 1 x 82 + 0 x 81 + 3 x 80 = 6710
• Sistema esadecimale
– Utilizza una notazione posizionale basata su
sedici cifre (0,1,…,9,A,B,C,D,E,F) e sulle potenze
di 16
– Esempio: 10316 = 1 x 162 + 0 x 161 + 3 x 160 = 25910
– Esempio: AC416 = 10 x 162 + 12 x 161 + 4 x 160 = 275610
Esadecimale: esempio
• HTML: il linguaggio principale usato per definire l’aspetto di una
pagina web (il colore dello sfondo, il layout, le tabelle ecc.)
• In HTML, rappresentiamo i codici per i colori rosso, verde e blu
usando le cifre esadecimali tra 00 e FF (0016 = 010 e FF16 =
25610)
• I colori predefiniti di HTML (da
http://en.wikipedia.org/wiki/Web_colors):
Esadecimale: esempio
• Per esempio:
– Blu: 0000FF16 = 0000000000000000111111112
• Si può anche definire altri colori
– Esempio dell’uso:
<font color=#FF8E2A>Ciao</font>
Conversione dalla base 10 alla
base 2
• Dato un numero N rappresentato in base dieci, la sua
rappresentazione in base due sarà del tipo cm cm-1cm-2
… c1c0 (le “ci” sono cifre binarie)
• Per convertire un numero in base dieci nel
corrispondente in base due si devono:
– Trovare i resti delle divisioni successive del numero N per
due
– Leggere i resti in ordine inverso per ottenere la
rappresentazione binaria di N (dalla cifra più significativa alla
cifra meno significativa)
Conversione dalla base 10 alla
base 2
• Intuitivamente: ottenere la rappresentazione
binaria dalla cifra meno significativa alla cifra
più significativa
cm cm-1cm-2 … c1c0
Resto di N/2
Conversione dalla base 10 alla
base 2
• Intuitivamente: ottenere la rappresentazione
binaria dalla cifra meno significativa alla cifra
più significativa
cm cm-1cm-2 … c1c0
Resto di (N/2)/2
Conversione dalla base 10 alla
base 2
• Intuitivamente: ottenere la rappresentazione
binaria dalla cifra meno significativa alla cifra
più significativa
cm cm-1cm-2 … c1c0
Resto di N/(2m-1)
Conversione dalla base 10 alla
base 2
• Intuitivamente: ottenere la rappresentazione
binaria dalla cifra meno significativa alla cifra
più significativa
cm cm-1cm-2 … c1c0
Resto di N/(2m)
Conversione dalla base 10 alla
base 2
• Intuitivamente: ottenere la rappresentazione
binaria dalla cifra meno significativa alla cifra
più significativa
cm cm-1cm-2 … c1c0
Resto di N/(2m+1)
Conversione dalla base 10 alla
base 2
• Esempio: il numero 610:
6/2 = 3 resto 0
3/2 = 1 resto 1
1/2 = 0 resto 1
• Leggendo i resti dal basso verso l’alto, si ha
che la rappresentazione binaria del numero
610 è 1102
• Per una corretta verifica basta riconvertire il
risultato alla base 10
– Cioè, calcolare 1 x 22 + 1 x 21 + 0 x 20
Conversione dalla base 10 alla
base 2
•
Perché 1102 = 610 ?
– Considerare le seguenti equazioni:
• Se b>c, c x b0 = 0 resto c
b
• a1 + a 2 = a1 + a2
b
b
b
• c x bN = c x bN-1
b
Conversione dalla base 10 alla
base 2
•
Perché 1102 = 610 ?
c0 x 20 = 0 resto c0
2
• c x 20 = 0 resto c
2
•a1 + a2 = a1 + a2
b
b
b
• c x bN = c x bN1
c1 x 21 + c0 x 20 = c1 x 20 resto c0
2
b
c2 x 22 + c1 x 21 + c0 x 20 = c2 x 21 + c1 x 20 resto c0
2
…
Conversione dalla base 10 alla
base 2
• Perché 1102 = 610 ?
6/2 = 3 resto 0
3/2 = 1 resto 1
1/2 = 0 resto 1
0 x 20 +
1 x 21 +
1 x 22
=6
1 x 22 + 1 x 21 + 0 x 20
0
2
1 x 21 + 1 x 20
2
1 x 20
2
= 1 x 21 + 1 x 20 con resto
= 1 x 20 con resto 1
= 0 con resto 1
Conversione dalla base 10 alla
base 2
• Perché 1102 = 610 ?
6/2 = 3 resto 0
3/2 = 1 resto 1
1/2 = 0 resto 1
0 x 20 +
1 x 21 +
1 x 22
=6
1 x 22 + 1 x 21 + 0 x 20
0
2
1 x 21 + 1 x 20
2
1 x 20
2
= 1 x 21 + 1 x 20 con resto
= 1 x 20 con resto 1
= 0 con resto 1
Conversione dalla base 10 alla
base 2
• Esempio: il numero 34510:
345/2 = 172 resto 1
172/2 = 86 resto 0
86/2 = 43 resto 0
43/2 = 21 resto 1
21/2 = 10 resto 1
10/2 = 5 resto 0
5/2 = 2 resto 1
2/2 = 1 resto 0
1/2 = 0 resto 1
• Leggendo i resti dal basso verso l’alto (in quanto si
ottengono a partire dalla cifra meno significativa,
l’unità), si ha che rappresentazione binaria del numero
34510 è 1010110012
Conversione dalla base 2 alla
base 10
• Sia cm cm-1cm-2 … c1c0 un numero rappresentato in
base 2, usiamo:
cm x 2m + cm-1 x 2m-1 + cm-2 x 2m-2 + … + c1 x 21 + c0 x 20 = N10
• Esempio: 1010110012
1 x 28 + 0 x 27 + 1 x 26 + 0 x 25 + 1 x 24 + 1 x 23 +
0 x 22 + 0 x 21 + 1 x 20
=
256 + 64 + 16 + 8 + 1
=
34510
Conversione dalla base 10 alla
base 2
• Esempio: il numero 34510:
345/2 = 172 resto 1
172/2 = 86 resto 0
86/2 = 43 resto 0
43/2 = 21 resto 1
21/2 = 10 resto 1
10/2 = 5 resto 0
5/2 = 2 resto 1
2/2 = 1 resto 0
1/2 = 0 resto 1
• Leggendo i resti dal basso verso l’alto (in quanto si
ottengono a partire dalla cifra meno significativa,
l’unità), si ha che rappresentazione binaria del numero
34510 è 1010110012
Conversione dalla base 2 alla
base 10
• Sia cm cm-1cm-2 … c1c0 un numero rappresentato in
base 2, usiamo:
cm x 2m + cm-1 x 2m-1 + cm-2 x 2m-2 + … + c1 x 21 + c0 x 20 = N
• Esempio: 1010110012
1 x 28 + 0 x 27 + 1 x 26 + 0 x 25 + 1 x 24 + 1 x 23 +
0 x 22 + 0 x 21 + 1 x 20
=
256 + 64 + 16 + 8 + 1
=
345
Operazioni su numeri binari
• Vediamo solo il caso della addizione nella
codifica binaria:
– Si mettono in colonna i numeri da sommare
– Si calcola il riporto ogni volta che la somma
parziale supera il valore 1
• Addizione:
0+0=0
0+1=1
1+0=1
1+1=0
con riporto 0
con riporto 0
con riporto 0
con riporto 1
Operazioni su numeri binari
• Addizione:
0+0=0
0+1=1
1+0=1
1+1=0
con riporto 0
con riporto 0
con riporto 0
con riporto 1
• Esempi:
1+
1=
10
101+
11=
1000
Possiamo anche
concludere che, ad
esempio,
1+1+1
= (1 + 1) + 1
= (0 con riporto 1) + 1
= 1 con riporto 1
10110101+
1000110=
11111011
111+
11=
1010
Codici a lunghezza fissa
• Se si usa un numero prestabilito di cifre si ha
un codice a lunghezza fissa
• In questo modo si pone anche un limite al
numero massimo rappresentabile
• Esempio: qual è il numero più grande
rappresentabile con 4 cifre?
–
–
–
–
In base 10:
In base 2:
In base 16:
In base 8:
9999
1111
FFFF
7777
(=1510)
(=6553510)
(=409510)
Codici a lunghezza fissa
• Numeri maggiori di quello massimo
rappresentabile causano problemi di
overflow
– Ovvero per essere rappresentati richiedono più
cifre di quelle a disposizione
• Esempio: 4 cifre
–
–
–
–
In base 10:
In base 2:
In base 16:
In base 8:
9999 + 1
1111 + 1
FFFF + 1
7777 + 1
= 1000010
= 100002 (=1610)
= 1000016 (=6553610)
= 100008 (=409610)
Codici a lunghezza fissa
• In generale, con N cifre a disposizione e base
b il più grande numero (intero positivo)
rappresentabile si può esprimere come
bN – 1
• Esempio: N=4
–
–
–
–
In base 10:
In base 2:
In base 16:
In base 8:
9999
1111
FFFF
7777
= 104 - 1
= 24 - 1
= 164 - 1
= 84 - 1
Codici a lunghezza fissa
•
Esempio di overflow nel sistema binario
dovuto a operazioni aritmetiche:
– 5 + 4 = 9 (in sistema decimale)
– Abbiamo usato solo un cifre decimale per il
risulto
•
Ricordiamo: 510 = 1012
101+
100=
1001
(in sistema binario)
,
410 = 1002
Errore: overflow
(non può essere codificato
910 = 10012 con tre bit)
Codifica dei numeri
• Codificare il numero 13210 nella
corrispondente rappresentazione binaria
• Ordinare in modo crescente i seguente
numeri:
–
–
–
–
–
10410
128
100112
1000100002
1001110