43
Fondamenti di Informatica - 1 Prof. B.Buttarazzi A.A. 2011/2012
Fondamenti di Informatica - 1
Prof. B.Buttarazzi
A.A. 2011/2012
07/03/2012 2
Sommario
• I sistemi di numerazione
• Il sistema binario
• Altri sistemi di numerazione
• Algoritmi di conversione
• Esercizi
Sistemi di numerazione
Un sistema numerico o di numerazione è un linguaggio che permette di rappresentare i numeri e, come tale, si compone di:• un alfabeto (l'insieme di simboli),• una grammatica: le regole con le quali comporre sequenze valide (sintassi) e quelle per dedurne il significato numerico (semantica).
Sistema di numerazione romano
XXVII (romano) = 27 (decimale)
Simboli: I = 1 V = 5 X = 10 L = 50 C = 100 D = 500 M = 1000
non è presente un simbolo che rappresenta 0
Sistema di numerazione additivo basato sull’uso di simboli associati a un
valore numerico
REGOLE DI CALCOLO
27 è compreso fra 20 e 30
XX (parte residua non rappresentata: 7)
7 è compreso fra 5 e 10
V (parte residua non rappresentata: 2)
2 si rappresenta direttamente
II
27 si rappresenta in romano con la stringa di simboli XXVII
Sistema di numerazione romano
Nel sistema numerico posizionale il valore di ogni cifra checompare nella rappresentazione del numero dipende dallaposizione che occupa.
Il numero di cifre diverse usate da un sistema numerico prende il
nome di BASE.
Ogni cifra è moltiplicata per una potenza della base.
Ad es:
32110 = 3x102 + 2x101 + 1x100 = 3x100 + 2x10 +1x1 = 32110
Sistema di numerazione posizionale
Sistemi di numerazione
posizionali
Sistemi di numerazione
posizionali
Decimale (es. 200210):
Binario (es. 01112 = 710):
cifre 2 0 0 2
pesi 103 102 101 100
cifre x pesi 2000 0 0 2
cifre 0 1 1 1
pesi 23 22 21 20
cifre x pesi 0 4 2 1
Sistemi di numerazione posizionali
Conversioni di base
j
j
k
0
j10 01cNck ck-1 ….. c1 c0
Da qualsiasi base (B) a decimale (10):Osservando che comunque in una notazione posizionale si ha
NB = B0 *d0 + B1 * d1 + B2 * d2 + B3 * d3 + ...
dw dw-1 ….. d1 d0
Conversioni di base
j
j
k
0
j10 01cNck ck-1 ….. c1 c0
Da qualsiasi base (B) a decimale (B=10):Osservando che comunque in una notazione posizionale si ha
N2 =1011= B0 *d0 + B1 * d1 + B2 * d2 + B3 * d3 + ...
=1*1+2*1+4*0+8*1
=1+2+8= 11 dw dw-1 ….. d1 d0
=1*1+10*1= 11
Conversioni di base
cw cw-1 ….. c1 c0
• Da qualsiasi base (B) a decimale (B=10)
Metodo del calcolo della espressione polinomiale associata
bk bk-1 ….. b1 b0
j
j
w
0
j10 01cN
Conversione: base 16 base 10
Trasformare 1F416 in decimale
cifre 1 F 4
pesi 162 161 160
cifre x pesi 1*162 15*16 4*1
j
j
w
0
j10 bcN
Conversione: base 16 base 10
Trasformare 1F416 in decimale
cifre 1 F 4
pesi 162 161 160
cifre x pesi
256 240 4
50010 = 1F416
Conversioni di base
Da decimale (10) a qualsiasi base (B):
n = 100 *c0 + 101 * c1 + 102 * c2 + 103 * c3 + ...
n = B0 *d0 + B1 * d1 + B2 * d2 + B3 * d3 + ...
ovvero
n = d0 + B *( d1 + B1 * d2 + B2 * d3 + ... )
che si può riscrivere come:
n = d0 + B *( d1 + B1 * (d2 + B2 * (d3 + ... ))))
d0 si può ricavare come resto della divisione intera n / B
Conversioni di base
Da decimale (10) a qualsiasi base (B):
n = 100 *c0 + 101 * c1 + 102 * c2 + 103 * c3 + ...
n = B0 *d0 + B1 * d1 + B2 * d2 + B3 * d3 + ...
ovvero
n = d0 + B *( d1 + B1 * d2+ B2 * d3 + ... )
che si può riscrivere come:
n = d0 + B *( d1 + B1 * (d2 + B2 * (d3 + ... ))))
Considerando il quoziente q della divisione intera
q = d1 + B1 * (d2 + B2 * (d3 + ... ))))
Conversioni di base
Da decimale (10) a qualsiasi base (B):
n = 100 *c0 + 101 * c1 + 102 * c2 + 103 * c3 + ...
n = B0 * d0+ B1 * d1 + B2 * d2 + B3 * d3 + ...
ovvero
n = d0 + B *( d1 + B1 * d2 + B2 * d3 + ... )
che si può riscrivere come:
n = d0 + B *( d1 + B1 * (d2 + B2 * (d3 + ... ))))
le altre cifre si possono ottenere allo stesso modo, iterando il procedimento
fino a quando si ottiene come quoziente 0, secondo il metodo delle
divisioni successive
Conversioni di base
cw cw-1 ….. c1 c0
• Da decimale a qualsiasi base:
Metodo delle divisioni successive
bk bk-1 ….. b1 b0
le cifre vengono prodotte nell'ordine dalla meno significativa (b0)
(LSB) alla più significativa (bk)(MSB)
Conversioni di base
• Metodo delle divisioni successive
Per convertire il numero n in una stringa di cifre
che ne rappresentino il valore in base B
• si divide n per B
• il resto costituisce la cifra meno significativa (LSB)
• il quoziente q serve a iterare il procedimento
• se tale quoziente è zero, l’algoritmo termina;
se non lo è, si assume come nuovo valore q
• si itera il procedimento con il valore q
Conversione: base 10 base 2
Trasformare 1110 in base 2.
11 2
1 5 2
1 2 2
0 1 2
1 0 1110 = 10112
Conversione: base 10 base 12
Trasformare 50010 in base 12
500 12
20 41 12
8 3 12
5 0
3
50010 = 35812
cifre 3 5 8
pesi 122 121 120
cifre x pesi
432 60 8
Metodo semplificato:
base 10 base 2
50 0
25 1
12 0
6 0
3 1
1 1
0
5010 = 1100102
Da base 10 a base 2 (es. 5010): dividere per 2 corrisponde a stabilire se un numero è pari o dispari.
Metodo semplificato:
base 2 base 10Da base 2 a base 10 (es. 1100102): le potenze di 2 sono facilmente calcolabili.
1100102 = 5010
1100102
2
16
32
+
=
50
Conversione
base B1 base B2
In generale, non è possibile convertire direttamente un numero
rappresentato in base B1 in un numero in base B2, a meno che una
delle due basi non sia la base 10.
Bisogna prima passare dalla base B1 alla base 10 (attraverso la
forma polinomia), e poi passare dalla base 10 alla base B2
(attraverso il metodo delle divisioni successive ).
Ci sono però dei casi in cui la conversione diretta è possibile.
CONVERSIONE TRA BASI POTENZA UNA DELL’ALTRA
Le rappresentazioni R1 e R2 di uno stesso numero su basi B1 e B2 che
sono una potenza dell’altra sono strettamente correlate:
se B1=2 e B2 = 2n
ogni cifra nella rappresentazione R1 corrisponde a n cifre nella
rappresentazione R2
in particolare ogni cifra ottale corrisponde a 3 cifre binarie
001011101 = 5 6 4 ottale
CONVERSIONE TRA BASI POTENZA UNA DELL’ALTRA
Le rappresentazioni R1 e R2 di uno stesso numero su basi B1 e B2 che
sono una potenza dell’altra sono strettamente correlate:
se B1=2 e B2 = 2n
ogni cifra nella rappresentazione R1 corrisponde a n cifre nella
rappresentazione R2
in particolare ogni cifra esadecimale corrisponde a 4 cifre binarie
Esempio 1
001011101 = 1 7 4 esadecimale
CONVERSIONE TRA BASI POTENZA UNA DELL’ALTRA
Le rappresentazioni R1 e R2 di uno stesso numero su basi B1 e B2 che
sono una potenza dell’altra sono strettamente correlate:
se B1=2 e B2 = 2n
ogni cifra nella rappresentazione R1 corrisponde a n cifre nella
rappresentazione R2
in particolare ogni cifra esadecimale corrisponde a 4 cifre binarie
Esempio 2
11000101 = A 3 esadecimale
CONVERSIONE DA BINARIO A OTTALE/ESADECIMALE
Per i numeri ottali è sufficiente suddividere il numero binario in gruppi di 3 bit (a
partire da destra) e convertire ogni singolo gruppo nel corrispondente ottale:
Per i numeri esadecimali è sufficiente suddividere il numero binario in gruppi di 4 bit
(a partire da destra) e convertire ogni gruppo nel corrispondente esadecimale:
001011101 = 5 6 4 ottale
11000101 = A 3 esadecimale
CONVERSIONE INVERSA DA OTTALE/ESADECIMALE A
BINARIO
Per passare da un numero ottale a binario è sufficiente rappresentare con 3 bit
ciascuna cifra ottale
Per passare da un numero esadecimale a binario è sufficiente rappresentare con 4 bit
ciascuna cifra esadecimale
001011101
5 6 4 ottale
11000101
A 3 esadecimale
Metodi semplificati:
base 8 (23) base 2 (21) base 16 (23)
Le trasformazioni tra basi potenza l’una dell’altra hanno caratteristiche algoritmiche interessanti:
0100 1001 0111 1111 00102
4 9 7 F 2 16
8 4 2 1 8 4 2 1 8 4 2 1 8 4 2 1 8 4 2 1
2 1 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1
01 001 001 011 111 110 0102
010010010111111100102
1 1 1 3 7 6 2 8
Confronti
Confronti
Operazioni aritmetiche• Tutte le notazioni posizionali utilizzano per le operazioni
aritmetiche le stesse regole, indipendentemente dalla base
di rappresentazione adottata, quindi, le regole già note per
la familiare rappresentazione in base 10 restano valide.
• Esempio addizione
Operazioni aritmetiche• Esempio sottrazione
Operazioni aritmetiche• Esempio moltiplicazione
la tabellina del 2 non richiede di essere memorizzata
),
Operazioni aritmetiche• Esempio divisione
La divisione in base 2 utilizza ancora lo stesso algoritmo visto per la base 10,
ma anche in questo caso con una semplificazione: non c'è più alcun bisogno di
"indovinare" i quozienti parziali, dato che ogni quoziente parziale (che ha sempre
una sola cifra) può essere solo 1 oppure 0, ed è uguale a 1 quando il dividendo
parziale è maggiore del divisore, uguale a 0 altrimenti.
1. Rappresentare il numero decimale 123 in base
binaria, ottale e esadecimale
2. Convertire il numero esadecimale FA in
decimale, ottale e binario
ESERCIZIO 1
Quale tra i seguenti valori corrisponde alla
rappresentazione binaria del numero 25410
?
a) 2542
b) 127.52
c) 111111102
d) 1111111110
e) 011101112
ESERCIZIO 2
Quale tra i seguenti è il numero successivo a 778
?
a) 7810
b) 788
c) 1002
d) 1008
e) 808
ESERCIZIO 3
Quale tra i seguenti rappresenta la conversione del numero 13AH
(base 16) in decimale, binario e ottale ?
a) 31410
, 1001110102, 472
8
b) 3142, 100111010
10, 472
8
c) 31410
, 1111111112, 477
8
d) 11410
, 1001110102, 577
8
e) 11010
, 1001110102, 472
8
ESERCIZIO 4
Eseguire le seguenti somme:
1. (1101 + 1101);
2. (11011 + 101);
3. (1110111 +111);
4. (101101 + 110 + 11101);
5. (11111 + 11)
Eseguire le seguenti moltiplicazioni:
1. (111011 * 11);
2. (10011*10);
3. (111011*1001)
ESERCIZIO 5
Eseguire le seguenti sottrazioni:
1. (1011 – 101);
2. (10101 – 11);
3. (11011 –111);
4. (11000 - 101)
Eseguire le seguenti divisioni:
1. (1101/10);
2. (100110/101);
3. (11010/111)
ESERCIZIO 6
Convertire in binario i seguenti numeri ottali:
(37; 121, 7032; 976)
Convertire in binario i seguenti numeri esadecimali:
(37; 7032; 976;5A7B)
Convertire in ottale i seguenti numeri binari
(101111100; 1001000;11011110)
Convertire in esadecimale i seguenti numeri binari
(10111100;111110101010000; 101101110111)
ESERCIZIO 7
