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!