Post on 01-May-2015
1
Corso di Informatica
(Programmazione)Lezione 1 (8 ottobre 2008)
Sistemi numerici posizionali
Codifica binaria degli interi senza segno
Codifica binaria degli interi con segnoin Modulo e Segno
2
Sistemi numerici posizionali
Un sistema numerico si dice posizionale se le cifre
(o simboli) usate per scrivere i numeri assumono
un valore che dipende dalla posizione in cui si trovano.
In un sistema numerico posizionale di base b, un
numero Nb è espresso come somma di potenze di b
moltiplicate per un coefficiente intero:1
0
ni
b ii
N C b
n è il numerodi cifre di Nb
3
Sistemi numerici posizionali
Esempio: sistema numerico decimale (b=10)
cifre usate {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
N10 = 135410
Si può scrivere anche:
N10 = 4 x 100 + 5 x 101 + 3 x 102 + 1 x 103
4 unità5 decine
3 centinaia1 migliaia
4
Sistemi numerici posizionali
Esempio: sistema numerico decimale (b=10)
indicando con Ci la cifra in posizione i a
partire da quella meno significativa (il 4)
che ha posizione 0:
N10 = 1 3 5 4
C3 C2 C1 C0
si può scrivere:
N10 = C0 x 100 + C1 x 101 + C2 x 102 + C3 x 103
5
3
100
10iii
N C
Esempio: sistema numerico decimale (b=10)
quindi si ha:
per un numero in base decimale di n cifre si ha:1
100
10n
ii
i
N C
Sistemi numerici posizionali
6
L’estensione della sommatoria precedente ad un
numero di qualsivoglia cifre (n) in una generica
base b è perciò immediata:
1
0
ni
b ii
N C b
Sistemi numerici posizionali
7
Un sistema numerico posizionale di base b utilizza
le cifre
da 0 a b-1 se b <= 10:
esempio:
b=2 {0, 1} 0 e 1 sono i cosiddetti bit
b=8 {0, 1, 2, 3, 4, 5, 6, 7}
b=10 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Sistemi numerici posizionali
8
Un sistema numerico posizionale di base b utilizza
le cifre
da 0 a b-1 e simboli aggiuntivi se b > 10:
esempio:
b=16 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
A, B, C, D, E, F}
A 10, B 11, C 12, D 13,
E 14, F 15
Sistemi numerici posizionali
9
Sistemi numerici posizionali
Esempio: sistema numerico ottale (b=8)
N8 = 13548
si può scrivere:
N8 = 4 x 80 + 5 x 81 + 3 x 82 + 1 x 83 = 60410
Attenzione: numerale è la sequenza di cifreche rappresenta un numero. Quindi 13548 e 135410 sono
due numeri diversi che hanno lo stesso numerale
10
Sistemi numerici posizionali
Esempio: sistema numerico esadecimale (b=16)
N16 = 4F16
si può scrivere:
N16 = F x 160 + 4 x 161 = 15 x 1 + 4 x 16 = 7910
11
Sistemi numerici posizionali
Esempio: sistema numerico binario (b=2)
N2 = 1 1 0 1 02
si può scrivere:
N2 = 0 x 20 + 1 x 21 + 0 x 22 + 1 x 23 + 1 x 24
= 0 + 2 + 0 + 8 + 16 = 2610
12
Sistemi numerici posizionali
Conversione da base 10 a base b
dato un numero N10 in base 10 si effettuano
successive divisioni intere per b fino
ad ottenere un risultato nullo. I resti,
elencati a partire da quello ottenuto per
l’ultima divisione effettuata, forniscono
il numerale che rappresenta, in base b,
il numero decimale dato.
13
Sistemi numerici posizionali
Esempio: conversione da base 10 a base 2
N10 = 610
6 / 2 resto = 0
3 / 2 resto = 1
1 / 2 resto = 1
0
1 1 02
14
Codifica binaria degli interi senza segno
Problema: quanti e quali interi senza segno si possono
rappresentare con un numero prefissato n
di bit?
n bit
Con n bit si possono avere 2n disposizioni
(con ripetizione) di 0 e 1 in n posizioni
gli interi che si possono rappresentare sono
quindi 2n
15
Codifica binaria degli interi senza segno
L’intervallo degli interi che si possono rappresentare
in n bit va da 0
0 0 0 0 0 0 00 n bit
a 1 x 20 + 1 x 21 + … + 1 x 2n-1 = (2n-1)
1 1 1 1 1 1 11 n bit
16
Codifica binaria degli interi senza segno
Esempio: per n=8 bit si possono rappresentare 256
interi che vanno da 0
0 0 0 0 0 0 00 8 bit
1 1 1 1 1 1 11 8 bit
8 bit = 1 byte1 KiloByte (kb) = 103 bytes
1 MegaByte (MB) = 106 bytes1 GigaByte (GB) = 109 bytes
a 255
17
1) 1 + 1 = 0 con riporto 1
2) 0 + 0 = 0
3) 0 + 1 = 1
4) 1 + 0 = 1
Regole della somma bit a bit
18
Codifica binaria degli interi senza segno
Esempio: somma di due interi senza segno in 8 bit
0 1 1 1 1 1 11 12710
0 1 1 0 1 0 11 10910
1 1 1 0 1 0 01 23610
111111
19
Codifica binaria degli interi senza segno
Esempio: somma di due interi senza segno in 8 bit
0 1 1 1 1 1 11 12710
1 0 1 1 1 0 11 18910
0 0 1 1 1 0 01 6010
111111
1
Overflow
11
Il risultato è errato in quanto31610 (=12710+18910) non è
rappresentabile in 8 bit
20
Codifica binaria degli interi con segno
Problema: rappresentare un intero con segno
con un prefissato numero n di bit
n bit
Un intero con segno è un “oggetto” composto da:
- segno
- modulo Esempio:+5 ha segno + e modulo 5
21
Codifica binaria degli interi con segno
Rappresentazione del segno
n bit
Il segno viene rappresentato dal bit più significativo
(quello più a sinistra):
- bit a 1 segno negativo
- bit a 0 segno positivo
22
Codifica binaria degli interi con segno
Rappresentazione del modulo
n bit
Il modulo viene rappresentato negli (n-1) restanti bit
secondo tre possibili codifiche:
- Modulo e Segno
- Complemento a 1
- Complemento a 2
23
Codifica binaria degli interi con segno
Codifica in “Modulo e Segno”
n bit
La sequenza dei bit del modulo è semplicemente
quella che fornisce (come somma di potenze) il
modulo dell’intero da rappresentare.
24
Codifica binaria degli interi con segno
Esempio: codifica in “Modulo e Segno” (n=8 bit)
+50 0 0 0 1 0 10
-51 0 0 0 1 0 10
25
Codifica binaria degli interi con segno
Intervallo di rappresentazione della codifica
in “Modulo e Segno”
n bit
Gli interi con segno rappresentabili in “Modulo e
Segno” vanno da (-2n-1+1) a (2n-1-1). Ad esempio
per n=8 bit l’intervallo va da -127 a 127.
26
Codifica binaria degli interi con segno
Vantaggio della codifica in “Modulo e Segno”
- semplice rappresentazione
Svantaggi della codifica in “Modulo e Segno”
- difficile implementazione della somma (non
si possono applicare le regole viste in precedenza)
- doppia rappresentazione dello 0
(1|00…00 e 0|00…00)
27
Codifica binaria degli interi senza segno
Esempio: somma di due interi in “Modulo e Segno”
0 1 00 +2
0 1 11 -3
1 0 11 -5
Errato!