il sistema di numerazione decimale

(1)

Elementi di Informatica

Prof. G. A. Di Lucca - Univ. del Sannio 1

Sistemi di Numerazione e Rappresentazione interna di Numeri

La rappresentazione 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 in 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

il sistema di numerazione decimale

• l’alfabeto in 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

(2)

• 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 c_i in una stringa (il primo posto a partire da destra è il posto 0), il numero rappresentato da tale cifra è: c_i *10ⁱ

esempio: la stringa 3542 rappresenta il numero:

3*10³ + 5*10² + 4*10¹ + 2*10⁰

• il sistema viene detto POSIZIONALE e PESATO

• 10 è detta la BASE del sistema

il sistema di numerazione decimale

cambiando l’alfabeto in 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:

C_n-1C_n-2...C₁C₀ . C_-1C_-2... C_-m

con ⁿ ⁱ

m i

i b

C X 



^ 



 1

… ovviamente nelle operazioni aritmetiche bisogna tener presente la base b della numerazione ...

…in generale ...

(3)

Il sistema decimale

• Base: b = 10

• Cifre: (0,1,2,3,4,5,6,7,8,9)

• Pesi: ... 10000 1000 100 10 1

i pesi sono potenze delle base 10

Il sistema ottale

• Base: b = 8

• Cifre: (0,1,2,3,4,5,6,7)

• Pesi: ... 4096 512 64 8 1

i pesi sono potenze delle base 8

6₈= 6₁₀10₈= 8₁₀ 11₈ = 9₁₀ 12₈ = 10₁₀ 13₈ =... .… = 19₁₀ 77₈= 63₁₀100₈= 6410 777₈= …. 1000₈= ….

0.1₈= 1/8₁₀0.01₈= 1/64₁₀0.001₈0.77₈

(4)

Il sistema esadecimale

• Base = 16

• Cifre: (0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F)

• Pesi: … 4096 256 16 1

10₁₆= 16₁₀16C₁₆= 364₁₀ 0.1 0.01

Il sistema binario

• Base = 2

• Cifre: (0,1)

• Pesi: ...2048 1024 512 256 128 64 32 16 8 4 2 1

10₂= 210 100₂= 410 111010₂= 58₁₀ 0.1₂= 1/2₁₀0.01₂= 1/4₁₀ 0.11₂= 3/4₁₀

(5)

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

… una caratteristica dei sistemi a base 2

^k

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: 77₈= 111 111₂34₈= 011 100₂

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)

– A9₁₆ = 1010 1001₂ FF₁₆ = 1111 1111₂

(6)

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.1₁₀è periodico in binario

CONVERSIONE DI BASE

Dato N>0 intero, in base decimale, convertirlo in base b:

• dividiamo N per b, otteniamo un quoto Q₀ ed un resto R₀ : N=Q₀b+R₀

• dividiamo Q₀ per b, otteniamo un quoto Q₁ ed un resto R₁:Q₀=Q₁b+R

• ripetiamo finché Q_n < b, ovvero dividendo Q_n per b il quoto è zero :

• Q₁= Q₂b+R₂

• _{………….}

• Q_n-1= Q_nb+R_n dove Q_n< b , ovvero

• Q_n= 0 + Q_n Ovvero :

N = Q_nbⁿ⁺¹+ R_nbⁿ+ R_n-1b^n-1+ … + R₁b +R₀b⁰ e quindi N nella base b la rappresentazione è:

Q_nR_nR_n-1 ...R₁R₀

(7)

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

10268₁₀ = 24034₈

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

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

123₁₀ = 1111011₂

Esempio:

123 : 2 61 : 2

30 : 2 15 : 2

7 : 2 1 : 2 1

1 0 1 1

3 : 2 1

1 0

(8)

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

Aritmetica binaria

• Un numero viene rappresentato da una stringa di n bit

• L’intervallo rappresentato è: 0  y < 2ⁿ

ad esempio se n = 16 l'intervallo è [0, 65536)

Per le operazioni valgono le stesse regole della base decimale

(9)

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

6₁₀ + 7₁₀ = 13₁₀

Aritmetica binaria

• Sottrazione

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

41₁₀- 15₁₀ = 26₁₀

(10)

Aritmetica binaria

110  101 = 110 000 110 11110

Prodotto Binario

• Prodotto

a b prodotto

0 0 0

0 1 0

1 0 1

1 1 1

6₁₀

5₁₀ = 30₁₀

• 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” ...

(11)

• 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 xX in un numero yY – regola di trasformazione: y = R(x)

• rappresentazione in cifre (sistema posizionale) di y

• codifica in bit delle cifre

Trasformazione e codifica

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



(12)

• Esempio di overflow:

Numero di bit per la rappresentazione: N = 4

1 1 1

1110 + 0111 = 10101

riporti

Somma Binaria

Il risultato è: 0101

ERRATO in quanto si ha overflow e si perde la cifra più significativa (quella in rosso)

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)

(13)

• Y ed X coincidono,

• Numeri rappresentabili: 0  y < M

• M = bⁿ

• b è la base di numerazione

– in pratica 2, 8, 16 … ma anche 10

• rappresentazione ad n cifre :

– C_n-1 C_n-2 ....C₀ , dove 0  C_i < b

• condizione di overflow: x  M

I numeri naturali

Rappresentazione con Aritmetica decimale

• Un numero viene rappresentato da d cifre decimali

• L’intervallo rappresentato è: 0  y < 10^d

• 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)

(14)

• poiché si adotta la codifica a lunghezza fissa ad n cifre (k bit),

– rappresentazioni estese a sinistra

– esempi: n=5, b=10 254₁₀ ==> 00254₁₀ n=5, b=2 4₁₀ ==> 00100₂

il tentativo di rappresentare 32 … :

0 0 1 0 0

1 0 0 0 0 0

… overflow

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 (-2¹⁵, 2¹⁵) intervallo aperto

(15)

... 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

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

C_n-1C_n-2...C₁C₀ . C_-1C_-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 ...

(16)

• virgola mobile (floating point): un numero reale x è rappresentato mediante la coppia (M, E), dove:

- x = M ·b^E  

- 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 ·10¹

• 137,8 · 10^-1

• 0,1378 · 102 (normalizzata) è quella comunemente usata

il sistema di numerazione decimale

il sistema di numerazione decimale

il sistema di numerazione decimale



Il sistema decimale

Il sistema ottale

Il sistema esadecimale

Il sistema binario

Tabella riassuntiva

… una caratteristica dei sistemi a base 2

i numeri periodici:

CONVERSIONE DI BASE

Esempio:

Esempio:

Aritmetica dei numeri naturali

Aritmetica binaria

Aritmetica binaria

Aritmetica binaria

Aritmetica binaria

RAPPRESENTAZIONE INTERNA DEI NUMERI

Trasformazione e codifica

Overflow e underflow



Parametri di un sistema di rappresentazione



I numeri naturali

Rappresentazione con Aritmetica decimale

Interi relativi: rappresentazione in segno e modulo ...

... vantaggi e svantaggi

Rappresentazione di reali:

virgola fissa

Rappresentazione di reali: virgola mobile