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