Appunti completi teoria di Elementi di informatica e programmazione

2.2 CODIFICA DEGLI INTERI RELATIVI

→

Codi ca in valore assoluto e segno

Il modo più semplice è indicare il segno seguito dal valore assoluto.

→ Se i bit disponibili per la codi ca sono n, si utilizza il primo bit della sequenza per indicare il segno (0 per positivo e 1

per negativo), e i restanti bit rappresentano il valore assoluto del numero.

Esempio: Rappresentazione di -11➔ 1 0 0 0 1 0 1 1, il primo numero corrisponde al segno -

19

fi fi fl fi fi

!!:

- si hanno due codi che per lo 0 (0 = 0000 e 0 =1000)

+ -

-

Contro di questa codi ca:

questa tecnica non viene usata nel calcolatore, porta dif coltà nel fare le operazioni aritmetiche (si fa la differenza tra i

valori assoluti, quello più grande meno quello più piccolo e poi si aggiunge il segno, ma è dif cile costruire un calcolatore

che ragioni in questo modo).

Per il calcolatore le operazioni di somma e sottrazione sono complesse → si vuole una rappresentazione per la quale

esista un unico metodo per l’addizione e la sottrazione

CODIFICA IN COMPLEMENTO A 1

↳

Si ottiene facendo il complemento di tutti i bit (ovvero si sostituiscono gli 0 con 1 e gli 1 con 0)

Es.: 5 = 0101 e –5 = 1010

dieci due dieci due

il bit più signi cativo (quello più a sinistra) indica se positivo o negativo

I numeri positivi si rappresentano come nella rappresentazione in valore assoluto e segno.

I numeri negativi si rappresentano come complemento a 1 del numero positivo corrispondente.

(ps. Anche qui lo zero ha due rappresentazioni, 00000=0 , 11111=0 )

+ -

Operazioni aritmetiche

La somma/sottrazione si ottiene facendo la somma degli addendi col segno e poi sommando l’eventuale riporto.

Risultato ERRATO! (over ow)→ il perché viene spiegato più avanti

CODIFICA IN COMPLEMENTO A 2

Sia n è il numero di bit utilizzati per la codi ca.

- I numeri positivi sono rappresentati normalmente (rappresentazione binaria dei numeri positivi) con il bit più

signi cativo pari a 0

- I numeri negativi si ottengono come complemento a due del numero positivo x corrispondente, ovvero come 2 –

n

x, e il bit più signi cativo è pari a 1

Es (n=4):

+6 = 0110

dieci

-6 → 2 - 6 = 10 → -6 = 1010

4

dieci dieci c2

Ci sono altri due metodi pratici equivalenti per calcolare il complemento a due di un numero x:

Metodo 1: 20

fi fi fi

fi fi fl fi fi fi

- E ettuare il complemento a 1 di x

- Aggiungere 1 (sommare 1)

Metodo 2:

- Partendo da destra e andando verso sinistra, lasciare invariati tutti i bit no al primo 1 compreso

- Complementare (invertire) tutti i bit successivi al primo 1

Il metodo 1 è quello utilizzato nei dispositivi elettronici

Es:

Codi ca in complemento a 2 con n=4 bit

Esempio intervalli di rappresentazione:

Supponiamo di avere una codi ca con n =16 bit

Rappresentazione in valore assoluto e segno: numeri compresi fra –(2 -1) e 2 -1, ovvero fra –32767 e +32767. Lo 0

15 15

ha due rappresentazioni 21

ff fi fi fi

Rappresentazione in complemento a 1: numeri compresi fra –(2 1) e 2 -1, ovvero fra –32767 e +32767. Lo 0 ha due

15 15

rappresentazioni

Rappresentazione in complemento a 2: numeri compresi fra –2 e 2 -1, ovvero fra –32768 e +32767. Lo 0 ha una

15 15

sola rappresentazione (in pratica, però, tipicamente si utilizzano i valori fra–32767 e +32767 per simmetria, così dato un

qualsiasi numero anche il suo opposto è rappresentabile).

sizeof ritorna la dimensione in byte della variabile

Conversione da numero binario in complemento a 2 a numero decimale

- simmetria

Si può usare la dell’operazione in compl. a 2

1000001 è un numero negativo, pari a – 0111111 = -63

due dieci

- regola:

Oppure si può usare la seguente

Il valore di un numero c c …c c rappresentato in complemento a

k k-1 1 0

due è dato dalla seguente espressione

-c x 2 + c x 2 + … + c x 2 + c x 2

k k-1 1 0

k k-1 1 0

Esempio:

1 0 0 0 0 0 1 = (-1)x2 + 1x2 = - 64 +1 = - 63

6 0

due dieci

I calcolatori usano la rappresentazione in complemento a 2

- si sempli cano i circuiti che svolgono le operazioni aritmetiche

- in particolare la somma si effettua semplicemente come nel caso di numeri naturali

- inoltre somma e sottrazione possono essere realizzate con un unico circuito: X-Y=X+(-Y).

ESTENSIONE DEL SEGNO

Estendiamo il segno per rappresentare un numero su n=k+d bit anziché su n=k bit

Somma di due numeri in complemento a 2 trascurando il riporto,

L’addizione di due numeri rappresentati in complemento a 2 dà un risultato corretto, a patto

che il risultato sia compreso entro l’intervallo dei numeri rappresentabili.

Se ho a disposizione 8 bit, posso rappresentare i numeri da -2 a +2 -1.

7 7

22

fi

Se il risultato dell’operazione non rientra nell’intervallo

rappresentabile → over ow

La somma di due numeri interi positivi o di due numeri interi

negativi può dare luogo ad un intero non rappresentabile con i bit

Over ow

→→ → in questo caso

a disposizione il risultato

dell’operazione non è valido.

Regola per la determinazione dell’over ow:

Se gli addendi hanno segno discorde non c’è MAI overflow

• Se gli addendi hanno segno concorde c’è overflow se il segno del risultato è diverso dal segno dei due

• addendi.

Con una rappresentazione su n bit, si ha overflow se i riporti generati nelle due posizioni più significative

• (n-1 e n-2 in figura) sono diversi (ovvero se c’è riporto generato in una posizione ma non nell’altra)

23

fl fl fl

2.3 CODIFICA DEI NUMERI REALI

→

Per rappresentare numeri come radici, frazioni e pigreco, servirebbe un numero di cifre illimitato, ma nel calcolatore è

possibile usare solo successioni di bit di lunghezza nita → è necessaria un’approssimazione che viene fatta in due

modalità:

1. Rappresentazione in virgola ssa

2. Rappresentazione in virgola mobile

una rappresentazione è de nita mediante un formato:

In entrambi i casi,

- Il numero n di bit a disposizione

- I campi in cui sono suddivisi i bit: quanti, in che ordine, quanti bit per

ciascun campo, cosa rappresenta ciascun campo

1 Rappresentazione in virgola ssa

→→

Abbiamo n bit a disposizione (e vogliamo

rappresentare numeri reali):

- un campo del formato rappresenta il segno → 1

bit per il segno

- un campo del formato rappresenta la parte intera

→ nI bit per la parte intera

- un campo del formato rappresenta la parte

frazionaria → nF bit per la parte frazionaria

Per indicare la “precisione” della rappresentazione in virgola ssa si utilizza il concetto di GRANULARITÀ = di erenza tra

un numero e il successivo rappresentabile→ quanto più è piccola, tanto più precisa è la rappresentazione.

Dato un numero, trovo il successivo sommando ad esso un numero avente tutti i bit pari a 0 tranne l’ultimo bit a destra,

quello che corrisponde alla potenza con esponente negativo maggiore in modulo (es: 0.00000000001). Quindi in generale

la granularità è ssa ed è pari a 2 . Per un qualsiasi numero rappresentabile I, il suo successivo è I+2

-nF -nF

Con il medesimo metodo devo poter rappresentare numeri grandi, per i quali non serve una grande precisione ma un

grande intervallo di rappresentazione (quindi per i quali è utile il campo della parte intera, e non quello della parte

frazionaria), e numeri piccoli, per i quali, al contrario, non serve un grande intervallo di rappresentazione ma serve elevata

precisione (quindi è fondamentale il campo della parte frazionaria, non il campo della parte intera).

→ Si vuole un sistema di rappresentazione in cui la granularità dipende dal numero rappresentato: maggiore è

l’ordine di grandezza, maggiore è la granularità (minore è la precisione). Si può estendere così l’intervallo dei numeri

rappresentabili.

notazione esponenziale:

nelle calcolatrici scienti che, un numero in base dieci viene rappresentato con m x 10 exp

IDEA: rappresentare un numero come N = mant * 2

→ esp

Nel calcolatore di utilizza quindi ↴

Rappresentazione in virgola mobile

→→

2

Questo tipo di rappresentazione è de nito da: formato, codi ca della mantissa, codi ca dell’esponente.

- Formato 24

fi fi fi fi fi fi fi fi fi fi ff

Dato un numero N da rappresentare N= ± mant * 2 , si memorizzano segno, mantissa, esponente

esp

Rappresentazione della mantissa:

forma normalizzata della mantissa perché abbia una rappresentazione univoca normalizzazione

si stabilisce una →

nella forma 1.xxxxxx

Esempi:

1001.01001 = 1.00101001 * 2 (forma normalizzata)

3

0.001011 = 1.011 * 2 (forma normalizzata)

-3

Rappresentazione dell’esponente

Codi ca con polarizzazione (o eccesso):

è un numero intero relativo.

- Prevede di aggiungere una costante positiva C in modo tale che i valori negativi compresi fra –C e 0 vengano codi cati

come interi positivi

- Con e bit a disposizione per l’esponente l’intervallo dei numeri rappresentabili

è [-C, 2 -C]

e-1

Esempio:

4 bit per l’esponente, rappresentazione in eccesso 7 (C = 2 -1)

e-1

Numeri rappresentabili [-7, +8] → Si somma 7 all’esponente e si trova il numero

da rappresentare

Standard IEEE 754

Stabilisce l’ordine dei campi, la lunghezza di mantissa e le loro codi che al ne di uniformare la precisione del calcolo.

25

fi fi fi fi

L’insieme dei numeri in virgola mobile non coincide con R

- L’insieme dei numeri reali è denso e illimitato.

- L’insieme dei numeri in virgola mobile ed è

non è denso limitato tra un numero reale massimo ed uno minimo

esprimibili

- l’aritmetica “reale” del calcolatore è diversa da quella classica→ approssimazioni inevitabili.

E lo zero?

In generale lo zero non si potrebbe rappresentare perché la mantissa è sempre 1.M …

Si usa un valore speciale dell’esponente (E = 0) e si pone la mantissa a 0000….000 → questa rappresentazione signi ca

“0”

Problemi che nascono dalla natura digitale del calcolatore

26 fi

Operazioni sui numeri “reali”

Addizione e sottrazione:

- si trasformano (con eventuale perdita di precisione) gli addendi in una rappresentazione con uguale esponente (il

maggiore)

- si sommano (sottraggono) le mantisse

- si normalizza se necessario

-

Moltiplicazione:

- si somm