Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 1
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 1
Sistemi di Numerazione e Rappresentazione interna di Numeri
La rappresentazione interna dei numeri richiede:
• una codifica, ovvero la definizione di un alfabeto in codice e di un codice
• la definizione di operazioni ed algoritmi che consentano di realizzare
sulle rappresentazioni dei numeri le operazioni del tipo di numero
codificato
Un sistema di numerazione è definito da:
• alfabeto codice: ovvero l’insieme dei simboli base, le CIFRE
• un codice: un insieme di regole che permettono di definire la
rappresentazione di un numero mediante una stringa di cifre
• un insieme di operazioni che realizzano sulla rappresentazione dei
numeri le operazioni previste per i numeri stessi
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 2
il sistema di numerazione decimale
• l’alfabeto codice è costituito da dieci cifre
• ciascuna cifra nella parola codice rappresenta un
numero dipendente dalla cifra stessa e dalla posizione
occupata dalla cifra nella parola codice in cui si trova
• una parola codice rappresenta un numero dato dalla
somma pesata dei numeri rappresentati dalle singole
cifre che lo compongono
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 2
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 3
• alle cifre (0,1,2,3,4,5,6,7,8,9) vengono associati
nell’ordine i primi 10 numeri Naturali
• detto i il posto occupato dalla cifra ci in una stringa (il
primo posto a partire da destra è il posto 0), il numero
rappresentato da tale cifra è: ci *10i
esempio: la stringa 3542 rappresenta il numero:
3*103 + 5*102 + 4*101 + 2*100 = 3452
• il sistema viene detto POSIZIONALE e PESATO
• 10 è detta la BASE del sistema
il sistema di numerazione decimale
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 4
cambiando l’alfabeto codice e la base, si possono costruire sistemi posizionali e pesati diversi da quello decimale
un numero X >0 è rappresentato mediante la stringa di cifre:
Cn-1 Cn-2 .........C1 C0 . C-1 C-2...... C-m
con in
mi
i bCX
1
… ovviamente nelle operazioni aritmetiche bisogna tener presente la base b della numerazione ...
…in generale ...
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 3
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 5
Il sistema decimale
• Base: b = 10
• Cifre: (0,1,2,3,4,5,6,7,8,9)
• Pesi: i pesi sono potenze delle base 10
… 10 4 10 3 10 2 10 1 10 0
… 10.000 1000 100 10 1
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 6
Il sistema ottale • Base: b = 8
• Cifre: (0,1,2,3,4,5,6,7)
• Pesi: i pesi sono potenze delle base 8
Alcune corrispondenze tra numeri in base 8 e 10
68 = 610 108 = 810 118 = 910 128 = 1010 138 =... .… = 1910
778 = 6310 1008 = 6410 7778= …. 10008 = ….
0.18 = 1/810 0.018 = 1/6410 0.0018 0.778
… 84 83 82 81 80
… 4.096 512 64 8 1
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 4
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 7
Il sistema esadecimale
• Base = 16
• Cifre: (0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F)
• Pesi: … potenze della base 16
1016 = 1610 16C16 = 36410
0.1 0.01
… 164 163 162 161 16 0
… 65.536 4.096
256 16 1
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 8
Il sistema binario
• Base = 2
• Cifre: (0,1)
• Pesi: ...potenze della base 2
102 = 210 1002 = 410 1110102 = 5810
0.12 = 1/210 0.012 = 1/410 0.112 = 3/410
220
… 211
210 29 28 27 26 25 24 23 22 21 2 0
1048576 … 2048 1024 512 256 128 64 32 16 8 4 2 1
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 5
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 9
Tabella
riassuntiva
F 17 1111 15
E 16 1110 14
D 15 1101 13
C 14 1100 12
B 13 1011 11
A 12 1010 10
9 11 1001 9
8 10 1000 8
7 07 0111 7
6 06 0110 6
5 05 0101 5
4 04 0100 4
3 03 0011 3
2 02 0010 2
1 01 0001 1
0 00 0000 0
Esadecimale Ottale Binario Decimale
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 10
… una caratteristica dei sistemi a base 2k
se adottiamo per ciascuna cifra dell’alfabeto codice una codifica
in numerazione binaria
– ad esempio ottale: (0,1,2,3,4,5,6,7)
000, 001, 010, 011, 100, 101, 110, 111
si ha che la codifica binaria indiretta coincide con quella diretta
– ad esempio: 778 = 111 1112 348= 011 1002
idem se codice esadecimale: (0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F)
– (0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001,
1010, 1011, 1100, 1101, 1110, 1111)
– A916 = 1010 10012 FF16 = 1111 11112
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 6
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 11
i numeri periodici:
• il concetto di numero periodico è del tutto dipendente dalla base
di numerazione
• un numero periodico in una determinata base può non esserlo in
un’altra
• esempio: 1/3 è periodico nella base decimale ma nella base 3 è
esattamente rappresentato da 0.1;
0.110 è periodico in binario
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 12
CONVERSIONE DA BASE DECIMALE A BASE b Dato N>0 intero, in base decimale, convertirlo in base b:
• dividiamo N per b, otteniamo un quoto Q0 ed un resto R0 : N=Q0b+R0 • dividiamo Q0 per b, otteniamo un quoto Q1 ed un resto R1 :Q0=Q1b+R • Continuiamo a dividere Q0 finché Qn < b, o finchè dividendo Qn per b
il quoto è zero :
• Q1= Q2b+R2 • …………. • Qn-1= Qnb+Rn dove Qn < b
• Qn= 0 + Qn
… quindi:
N = Qnbn+1 + Rnb
n + Rn-1bn-1 + … + R1b +R0b
0
e quindi N nella base b la rappresentazione è:
QnRnRn-1 ........R1R0
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 7
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 13
Esempio:
conversione di 10268 decimale in base ottale
10268 : 8 1283 resto 4
1283 : 8 160 resto 3
160 : 8 20 resto 0
20 : 8 2 resto 4
2 : 8 0 resto 2
1026810 = 240348
cifra più significativa cifra meno significativa
Dividendo base Quoto Resto
10268 8 1283 4
1283 8 160 3
160 8 20 0
20 8 2 4
2 8 0 2
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 14
conversione in base binaria di 123 decimale
123 : 2 61 resto 1
61 : 2 30 resto 1
30 : 2 15 resto 0
15 : 2 7 resto 1
7 : 2 3 resto 1
3 : 2 1 resto 1
1 : 2 0 resto 1
12310 = 11110112
Esempio:
123 : 2
61 : 2
30 : 2
15 : 2
7 : 2
1 : 2
1
1
0
1
1
3 : 2
1
1 0
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 8
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 15
Aritmetica dei numeri naturali
• Algoritmi classici per la realizzazione delle operazioni
aritmetiche (noti dalle scuole elementari)
• le regole sono le stesse per tutti i sistemi di numerazione
posizionali (non solo quello decimale):
– per addizione e sottrazione numeri in colonna e riporto …,
– per moltiplicazione e divisione uso di tavole pitagoriche per
le singole cifre …
– un esempio … in decimale ... 1 1
4987 + 3232
8219
riporti
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 16
Aritmetica binaria
• Un numero viene rappresentato da una stringa di n bit
• L’intervallo rappresentato è: 0 y < 2n
ad esempio se n = 16 l'intervallo è [0, 65536)
Per le operazioni valgono le stesse regole della base decimale
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 9
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 17
Aritmetica binaria
• Addizione
• Stesse regole della aritmetica decimale
r a b s r'
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
r: riporto
a,b: addendi
s: somma
r’: nuovo riporto
1 1
0110 + 0111 =
1101
riporti
Somma Binaria
610 + 710 =
1310
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 18
Aritmetica binaria
• Sottrazione
• Stesse regole della aritmetica decimale
0 1 1 1 1
1 0 1 0 0 1 - 0 0 1 1 1 1 =
0 1 1 0 1 0
prestito
Sottrazione
Binaria
Minuendo Sottraendo Differenza Prestito
0 0 0
1 0 1
1 1 0
0 1 1 1
4110 - 1510 =
2610
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 10
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 19
Aritmetica binaria
110 101 = 110 000 110 11110
Prodotto Binario
• Prodotto
• Stesse regole della aritmetica decimale
a b prodotto
0 0 0
0 1 0
1 0 0
1 1 1
610 510 =
3010
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 20
• nei calcolatori la rappresentazione interna di un numero
è finalizzata a rendere efficienti gli algoritmi per le
operazioni
• in genere è usata codifica a lunghezza fissa
– l’insieme di numeri rappresentati è finito
• sono usati sistemi posizionali
RAPPRESENTAZIONE INTERNA DEI NUMERI
ad eccezione dei numeri interi positivi (caso banale), è
effettuata una trasformazione del numero da
rappresentare in un altro numero “rappresentabile” ...
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 11
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 21
• insieme X dei numeri da rappresentare
– X è un intervallo di numeri interi o reali
• insiemeY dei numeri rappresentati
– Y è un intervallo finito
• trasformazione di un numero xX in un numero yY
– regola di trasformazione: y = R(x)
• rappresentazione in cifre (sistema posizionale) di y
• codifica in bit delle cifre
Trasformazione e codifica
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 22
Overflow e underflow
• overflow: tentativo di rappresentare un numero esterno
all’intervallo
– se X è un intervallo di numeri interi allora Y deve avere
almeno la stessa cardinalità
• underflow: un numero reale x 0 viene rappresentato da y = 0
– X è un intervallo di numeri reali, rappresentati da Y
(intervallo finito) con un’approssimazione
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 12
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 23
Overflow e underflow
• Esempio di overflow:
Numero di bit per la rappresentazione: N = 4
1 1 1
1110 + 0111 =
10101
riporti
Somma Binaria
Il risultato è: 0101
che è ERRATO perché si ha overflow e si perde la cifra più
significativa (quella in rosso)
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 24
Parametri di un sistema di rappresentazione
• intervallo numerico e tipo del numero x da rappresentare
• regola di trasformazione y = R(x)
• condizione di overflow
• approssimazione e condizione di underflow (solo per i reali)
NB: se la base della numerazione della trasformazione non è binaria, la codifica del numero in binario è indiretta ...
• base di numerazione
• codifica delle cifre in binario
(se la base della numerazione è
diversa da 2)
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 13
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 25
• Y ed X coincidono,
• Numeri rappresentabili: 0 y < M
• M = bn
• b è la base di numerazione
– in pratica 2, 8, 16 … ma anche 10
• rappresentazione ad n cifre :
– Cn-1 Cn-2 ....C0 , dove 0 Ci < b
• condizione di overflow: x M
I numeri naturali
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 26
Rappresentazione con Aritmetica decimale
• Un numero viene rappresentato da d cifre decimali
• L’intervallo rappresentato è: 0 y < 10d
• per ogni cifra decimale si adotta una rappresentazione con k
bit per cifra: il numero è rappresentato da k d bit
– ad esempio, per d = 4, l’intervallo è [0, 9999);
– adottando un sistema 8-4-2-1 (k = 4) un numero è rappresentato
da 16 bit
– il numero 8012 è rappresentato dalla stringa 1000 0000 0001 0010 (codifica indiretta di un numero in binario: l’alfabeto codice intermedio è
costituito dalle codifica delle singole cifre decimali)
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 14
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 27
• poiché si adotta la codifica a lunghezza fissa ad n cifre (k bit),
– rappresentazioni estese a sinistra
– esempi: n=5, b=10 25410 ==> 0025410
n=5, b=2 410 ==> 001002
Proprietà importanti
il tentativo di rappresentare 32 … :
0 0 1 0 0
1 0 0 0 0 0
… overflow
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 28
Interi relativi: rappresentazione in segno e modulo ...
• Intervallo: x (-M , M)
• rappresentazione (tradizionale) in segno e modulo: s, y
– s = sign(x) ------ y = |x|
• condizione di overflow: |x| M
• n cifre per rappresentare il suo modulo e una cifra che
precede le altre per rappresentare il segno
- in aritmetica binaria s = sign(x) è rappresentata da un bit:
s = 1 se x < 0; s = 0 se x 0
s y
15 14 0
x (-215, 215) intervallo aperto
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 15
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 29
... vantaggi e svantaggi
• vantaggio: coincide con la nostra usuale rappresentazione
• svantaggio: richiede il trattamento separato di segno e
modulo: algoritmi aritmetici più pesanti ...
... nei calcolatori, per ovviare agli svantaggi dell’aritmetica
della rappresentazione in segno e modulo, si adottano altre
rappresentazioni ...
es. complemento a uno
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 30
Rappresentazione di reali: virgola fissa
• virgola fissa (fixed point): rappresentazione di numeri con n
cifre, nella quale la posizione della virgola (o punto decimale)
che separa la parte intera da quella frazionaria è predeterminata:
Es.: n cifre intere + m decimali
Cn-1 Cn-2 .........C1 C0 . C-1 C-2...... C-m
• nella rappresentazione dei numeri frazionari (|x| < 1) la virgola è
in prima posizione: .078900
- se la virgola occupa una posizione fissa, non necessita di essere
rappresentata esplicitamente ...
Elementi di Informatica a.a. 2017/18 - Prof. G.A. Di Lucca
Corso di Laurea in Ingegneria Energetica 16
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 31
Rappresentazione di reali: virgola mobile
• virgola mobile (floating point): un numero reale x è
rappresentato mediante la coppia (M, E), dove:
- x = M ·bE
- M è un numero frazionario o intero detto mantissa
- E è un numero intero detto esponente o caratteristica
- b è la base della numerazione (binaria nei calcolatori)
- è l’approssimazione della rappresentazione
…. più ‘coppie’ Mantissa, Esponente
Es.: dato il reale 13,78 (virgola fissa)
• 1,378 ·101
• 137,8 · 10-1
• 0,1378 · 102 (normalizzata) è quella comunemente usata
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 32
Rappresentazione di reali: virgola mobile
