Fondamenti di Informatica 1 - uniroma2.it · 2n-1-1) e metà valori negativi (da -1 a -2n-1). Si...

Fondamenti di Informatica - 1

Prof. B.Buttarazzi

A.A. 2011/2012

09/03/2012 2

Sommario

• Rappresentazione dei numeri naturali (N)

• Rappresentazione dei numeri interi (Z)

– Modulo e segno

– In complemento a 2

• Operazioni aritmetiche

• Esercizi

3

Codifica delle informazioni

• Qualunque informazione (dato associato a un significato)

sia essa un numero, una data, una immagine, un suono,

prima di essere elaborata (memorizzata, trasformata,

comunicata) da un computer necessita di essere

rappresentata in forma digitale.

• Questo in quanto i computer si basano sul sistema binario

che comprende solo i numeri 0 e 1.

• Queste cifre sono chiamate bit (binary digit) .

Registro

I computer per rappresentare le informazioni utilizzano dei dispositivi

fisici detti registri che hanno numero fisso di cifre binarie.

Si è passati rapidamente da 8 a 16 a 32 a 64 bit…. ma il limite rimane!

• Un registro è un dispositivo elettronico per memorizzare le

informazioni

• Dal punto di vista tecnologico un registro è un insieme di n elementi

fisici bistabili, detti bit.

Registro

I computer per rappresentare le informazioni utilizzano dei dispositivi

fisici detti registri che hanno numero fisso di cifre binarie.

Si è passati rapidamente da 8 a 16 a 32 a 64 bit…. ma il limite rimane!

• Un registro è un dispositivo elettronico per memorizzare le

informazioni

• Dal punto di vista tecnologico un registro è un insieme di n elementi

fisici bistabili, detti bit.

Se si usa un numero prestabilito di cifre binarie (dovuto al fatto che i registri del computer hanno una dimensione prestabilita - n bit), si pone un limite al numero massimo di informazioni rappresentabili

Registro n=1 21= 2 configurazioni

0

1


00

01

10

11


000

001

010

011

100

101

110

111


0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

000

001

010

011

100

101

110

111

Registro

Un registro formato da n bit è in grado di assumere 2n

configurazioni di stato diverse.

5 4 3 2 1 0 n=6 26= 64 configurazioni

Ciascun bit ha due configurazioni stabili possibili,

a cui per convenzione vengono associati i simboli 0 e 1

11

Per la rappresentazione si utilizza la conversione del numero

naturale in binario0

0

1

1

3

3

2

2

1

1 22.....222 xdxdxdxdxd N

N

N

N

N

N

I NUMERI NATURALI sono i numeri interi positivi:

0, 1, 2, 3, 4, 5, 6, …..

Rappresentazione dei numeri naturali

12

Il più piccolo numero codificabile è:

02020.....202020 01321 xxxxx NNN

Il più grande numero codificabile è:

01321 2121.....212121 xxxxx NNN

Se N=8, 0-255 ossia da 0 a (2N-1)

Se N=16, 0-65535 ossia da 0 a (2N-1)

Se N=32, 0-4.294.967.295 ossia da 0 a (2N-1)


13

La codifica esadecimale viene a

volte usata al posto della binaria

per ridurre spazio

Il numero binario viene

suddiviso in blocchi di 4 bits a

partire dal meno significativo

Ad ogni gruppo viene sostituito

il simbolo esadecimale

corrispondete

Decimale Binario Esadecimale

0 0000 0

1 0001 1

2 0010 2

3 0011 3

4 0100 4

5 0101 5

6 0110 6

7 0111 7

8 1000 8

9 1001 9

10 1010 A

11 1011 B

12 1100 C

13 1101 D

14 1110 E

15 1111 F


14


• Esempi:

– codifica dei numeri da 0 a 7:

• bastano3 bit

• una possibile codifica che usa 4 bit

000 0

001 1

010 2

011 3

100 4

101 5

110 6

111 7

15

• Esempi:

– codifica dei numeri da 0 a 8:

• 3 bit non bastano

• una possibile codifica che usa 4 bit

0000 0

0001 1

0010 2

0011 3

0100 4

0101 5

0110 6

0111 7

1000 8


16

Per la codifica dei numeri da 0 a M

– Se M=2n-1

Servono n bit ove n= log 2 M

– Per M qualsiasi il più piccolo n

tale che 2n M

Esempio: M=1000

Se scelgo n=9 riesco a rappresentare 512

informazioni:, quindi non basta. n=10

(1024 informazioni) va bene

00000000 0

00000001 1

00000010 2

00000011 3

00000100 4

00000101 5

00000110 6

00000111 7

….. ….

11111111 127

Rappresentazione di M numeri naturali

17

Modulo e segno

Complemento a 2

Codifica Numeri Interi

18

I numeri interi o relativi sono rappresentati in modo analogo

a quanto fatto per i numeri senza segno, riservando 1 bit per

rappresentare il segno

Si sceglie il bit più significativo per il segno

Se il bit vale 1 allora il segno rappresentato è il –

Se il bit vale 0 allora il segno è il +

Il numero di bit utili per rappresentare il valore assoluto del

numero intero relativo è: N-1

Rappresentazione dei Numeri

Interi Modulo e Segno

19

Esempio: si voglia rappresentare il numero -5 con 8 bit

Il primo bit (quello più significativo) viene posto a 1 perchè il numero è negativo

gli altri 7 bit si calcolano con il metodo visto prima applicato al numero 5, ottenendo

0000101.

Dunque il numero binario che rappresenta -5 è: 10000101

Si rappresenta un intero mediante la rappresentazione separata del modulo e del

segno;

•qualunque sia il numero dei bit usati, quello più significativo rappresenta il segno

(0 +;1 -) (tale bit simbolico, non ha peso);

•I restanti (n-1) bit (che hanno un peso in funzione della posizione) rappresentano la

codifica binaria del modulo



20

Dunque se dispongo di N bit, è possibile rappresentare numeri

interi relativi il cui intervallo sarà:

-(2N-1-1…….+(2N-1-1)

Se N=8 ---> -127,….,0,….,+127.

Se N=16 ---> -32.767,….,0,….,+32.767.

Se N=32 ---> -2.147.483.647,….,0,….,+2.147.483.647.

NOTA: ci sono due

rappresentazioni

dello 0



Rappresentazione dei numeri

negativi in modulo e segno

• Con 3 bit avremo:

000 +0

001 +1

010 +2

011 +3

100 -0

101 -1

110 -2

111 -3

Problemi:

Il numero 0 ha due

rappresentazioni

Per l’operazione di

somma si deve tener

conto dei segni degli

addendi

0 0 1 0 + (+2)

1 0 1 1 = (-3)

1 1 0 1 (-5 ERRATO)

22

Dati due numeri binari in rappresentazione modulo e segno, le operazioni

di somma o di sottrazione dipendono dai segni

Se i segni sono gli stessi:

Si considerano tutti i bit meno quello del segno

Si sommano tali sequenze

Il numero binario risultante sarà ottenuto aggiungendo il bit di

segno ai bit ottenuti dalla somma.

Se i segni dei due numeri sono diversi:

Si considerano tutti i bit meno quello del segno

Si sottrae il numero più piccolo in valore assoluto dal numero più

grande

Il numero binario risultante sarà ottenuto aggiungendo ai bit ottenuti

dalla sottrazione il bit di segno del numero in valore assoluto più

grande.

Somme e Sottrazioni in Modulo

e Segno

Il principale problema della rappresentazione in Modulo e

segno è che le somme algebriche vanno eseguite in modo

diverso in dipendenza dal segno concorde o discorde dei due

operandi

Questo complica notevolmente la realizzazione delle operazioni

di somma e sottrazione a livello hardware.

Somme e Sottrazioni in Modulo

e Segno

24

Cosa è il complemento a 2 di un numero binario ?

Dato un numero binario X di N bit, si definisce

complemento a 2 di tale numero il numero Y che si ottiene

effettuando l’operazione 2N-X

Un modo semplice per calcolarlo si ottiene tramite il

seguente algoritmo: si invertono tutti i bit del numero (0 diviene 1, e viceversa)

si somma 1

Il Complemento a 2

25

Esempio: si determini il complemento a 2 del numero 10100.

Dalla definizione si ottiene: 100000-10100 =01100

Applicando il metodo si ha:

01011 +1

01100

Esempio: si determini il complemento a 2 del numero 01101001.

Dalla definizione si ottiene: 100000000- 01101001 =10010111

Applicando il metodo si ha:

10010110 +1

10010111

Il Complemento a 2

26

La rappresentazione in complemento a 2 di un numero intero su N bit, si effettua

nella seguente maniera:

i numeri interi positivi (incluso lo zero) sono rappresentati in modulo e segno

utilizzando gli N bit:

1 bit di segno (il MSB, pari a 0) e N-1 bit per la codifica

i numeri interi negativi sono rappresentati realizzando il complemento a 2 della

codifica binaria su N bit del valore assoluto del numero che si vuole

rappresentare


Interi in Complemento a 2

27

La rappresentazione in complemento a 2 di un numero intero su N bit, si effettua

nella seguente maniera:

i numeri interi positivi (incluso lo zero) sono rappresentati in modulo e segno

utilizzando gli N bit:

1 bit di segno (il MSB, pari a 0) e N-1 bit per la codifica

i numeri interi negativi sono rappresentati realizzando il complemento a 2 della

codifica binaria su N bit del valore assoluto del numero che si vuole

rappresentare



1. Si rappresenta in binario usando tutti i bit il valore assoluto del

numero negativo da codificare

2. Si effettua il complemento a due del numero binario ottenuto

• Si invertono tutti i bit in tale rappresentazione (0 1,1 0)

• Si somma uno al risultato ottenuto al passo precedente

28



Esempio: si voglia rappresentare il numero 1 con 8 bit

Essendo il numero positivo:

•Segno 0

•Codifica binaria su 7 bit di 1: 0000001

Codifica ottenuta: 00000001


Essendo il numero negativo:

Codifica binaria del valore assoluto (1) su 8 bit 00000001

complemento a 2:

•11111110+1

• 11111111.

29

Esempio: si voglia rappresentare il numero 1 con 8 bit

Essendo il numero positivo:

•Segno 0

•Codifica binaria su 7 bit di 1: 0000001

Codifica ottenuta: 00000001


Essendo il numero negativo:

Codifica binaria del valore assoluto (1) su 8 bit 00000001

complemento a 2:

•11111110+1

• 11111111.



30

Esempio Codifica in Complemento a 2 su 4 bit



31

Secondo questa rappresentazione non (completamente) posizionale le 2n

combinazioni di n bit vengono usate per denotare metà valori positivi (da 0 a

2n-1-1) e metà valori negativi (da -1 a -2n-1).

Si noti che in questa rappresentazione il bit più significativo ha peso -2n-1

anziché, come accade usualmente in binario puro, 2n-1.

Così, ad esempio, nella sequenza di bit 11110001 il bit più significativo ha

peso -128 anziché +128.

In questo modo:

quando il bit più significativo vale 0, la stringa di bit denota valori positivi, e

in particolare denota gli stessi valori che denoterebbe in binario puro, perché

il differente peso del MSB non ha influenza;

quando invece tale bit vale 1, la stringa denota valori negativi, e in particolare

il valore rappresentato si ottiene sommando il contributo negativo dell’MSB

con i contributi positivi degli altri bit.



32

Dato un numero in complemento a 2, la sua conversione in

decimale avviene tramite la formula:

Da questa formula si vede che il numero più piccolo che può

essere rappresentato con N bit è:

mentre il numero più grande è:

00

11

3N3N

2N2N

1N1N 2d2d....2d2d2d

1N2

1222....22 1N013N2N



33

Dunque se dispongo di N bit, è possibile rappresentare numeri

interi relativi il cui intervallo sarà:

-(2N-1)…….+(2N-1-1)

Se N=8 ---> -128,….,0,….,+127.

Se N=16 ---> -32.768,….,0,….,+32.767.

Se N=32 ---> -2.147.483.648,….,0,….,+2.147.483.647.


Complemento a 2

34

Esempio: si voglia convertire il numero binario in complemento a 2

00000001

Applicando la formula precedente , si ottiene che il numero decimale è 1.

Esempio: si voglia convertire il numero binario in complemento a 2

11111111

Applicando la formula

si ottiene che il numero decimale è dato dalla somma:

-1*27+1*26+1*25+1*24+1*23+1*22+1*21+1*20=

-128+64+32+16+8+4+2+1 =

-128+127=-1

00

11

55

66

77 2d2d....2d2d2d

00

11

55

66

77 2d2d....2d2d2d


Complemento a 2

35

Perchè la Rappresentazione in Complemento a 2 è più Conveniente ?

Il motivo più rilevante è relativo ai vantaggi ottenibili nell'esecuzione di

operazioni elementari come la somma e la sottrazione.

Queste due operazioni sono quelle che vengono più frequentemente

realizzate in un computer, e, dunque, un risparmio nel tempo necessario

alla loro esecuzione comporta un indiscusso aumento delle prestazioni di

un computer.

La codifica in complemento a 2 permette un notevole risparmio di tempo

nell'esecuzione di somme

Con la rappresentazione in complemento a 2 l’operazione di sottrazione

viene ricondotta alla somma previa complementazione dell’operando.

Confronto tra le Codifiche

Numeri Interi

36

Addizione…..già studiata

Le regole per realizzare l'addizione tra numeri binari:

0+0=0

0+1=1

1+0=1

1+1=0 con riporto di 1

Esempio: Sommare i numeri 0001 (1) e 1010(10).

0001+

1010=

_______

1011 (11)

Esempio: Sommare i numeri 0011 (3) e 1010(10).

0011+

1010=

_______

1101 (13)

37

Somme e Sottrazioni in

Complemento a 2

Dati due numeri binari in complemento a due, per la somma si

applicano le regole dell'addizione a tutti i bit compreso il bit

di segno.

Esempio: Si sommino i numeri a 4 bit 0010 (+2) e 1010 (-6).

0010+

1010=

______

1100 (-4)

Il numero binario risultante è già il risultato con il segno

giusto.

38

Somme e Sottrazioni in

Complemento a 2

Esempio: Si sommino i numeri in complemento a 2 001100

(+12) e 100000 (-32).

001100+

100000=

_______

101100 (-20)

Il numero binario risultante è già il risultato con il segno

giusto.

39

E’evidente la semplificazione nel calcolo della somma e

della sottrazione dei numeri rappresentati in complemento

a due.

Confronto tra le Codifiche

Numeri Interi

40

Primo caso

Si supponga di lavorare con codifica complemento a 2 su 4 bit (-8,…,+7)

si consideri la seguente operazione di somma in complemento a due:

1001 (-7) e 1111 (-1).

La somma in base 10 è -8 e rappresenta il limite inferiore codificabile con 4 bit

Eseguendo la somma tra le rappresentazioni dei numeri si ottiene:

1001+

1111=

_________

1 1000

l'operazione effettuata ha prodotto un risultato non contenibile nello spazio

predisposto in quanto è necessario un altro bit (l’1 a sinistra, ottenuto come riporto,

viene memorizzato nel CARRY FLAG per superamento della capacità del registro),

comunque il risultato ottenuto (1000 in complemento a 2 corrisponde a –8) è da

considerare corretto.

Riconoscimento Automatico di

un Risultato Corretto

41

Secondo Caso

Si supponga sempre di lavorare con codifica in complemento a 2 su 4 bit (-8,…,+7)Si consideri la seguente operazione di somma in complemento a due:

1001 (-7) e 1110 (-2).

In questo caso la somma -9 non è codificabile con 4 bit.

Eseguendo la somma si ottiene:

1001+

1110=

________

1 0111

l'operazione effettuata ha prodotto un risultato non contenibile nello spazio predisposto in

quanto è necessario un altro bit (l’1 a sinistra, ottenuto come riporto, viene memorizzato

nel CARRY FLAG per superamento della capacità del registro ), ma il risultato ottenuto

(0111 - in complemento a 2 corrisponde a +7) ) è da considerare errato!

Si ha Overflow.



Quando la somma di due interi

produce come risultato un valore

esterno all’insieme dei valori

rappresentabili si dice che si è

verificato un “Overflow” e il risultato

ottenuto non è corretto;

Il Calcolatore non e in grado di

prevenire un errore di Overflow, in

quanto questo viene individuato solo

dopo aver effettuato l’operazione.

42

Terzo Caso

Si supponga di lavorare ad 8 bit (-128,….,+127)

Si consideri la seguente operazione di somma in complemento a due:

01111110 (126) e 00000011 (3).

In questo caso la somma (129) è superiore al numero massimo positivo codificabile in

complemento a due. con 8 bit

Eseguendo la somma, si ottiene:

01111110 +

00000011 =

____________

10000001

l'operazione effettuata ha prodotto un valore contenibile nello spazio predisposto ma il

risultato ottenuto (10000001 - in complemento a 2 corrisponde a -127) ) è da considerare

errato!

Si ha Overflow.



Quando la somma di due interi

produce come risultato un valore

esterno all’insieme dei valori

rappresentabili si dice che si è

verificato un “Overflow” e il risultato

ottenuto non è corretto;

Il Calcolatore non e in grado di

prevenire un errore di Overflow, in

quanto questo viene individuato solo

dopo aver effettuato l’operazione.

43

Per capire se il risultato che è stato ottenuto sia valido o meno, osservando i casi

precedenti basta controllare i bit più significativi dei numeri da sommare ( X e Y ) e

della somma ( S ) ottenuta.

Se i bit più significativi dei numeri da sommare ( X e Y ) sono diversi non potrà

verificarsi mai l’overflow e il risultato sarà sempre da considerarsi corretto.

Se i bit più significativi dei numeri da sommare ( X e Y ) sono uguali e il bit più

significativo della somma ( S ) è diverso da essi allora ci sarà overflow e il risultato

dovrà essere considerato errato.

Nella CPU esiste un registro (detto registro di stato - PSW) dove ciascuno dei bit che lo compongono ha un

significato autonomo che indica (flag) se nel corso dell'ultima operazione eseguita si è verificato un determinato

evento.CF=1: Carry Flag o flag del riporto. Indica se l'operazione effettuata ha generato un riporto.

OF=1: Overflow Flag. Indica se nell'operazione effettuata si è verificato un errore di overflow (risultato non rappresentabile

nello spazio predisposto).

PF = 1 se il risultato di un’operazione ha un numero pari di bit ad uno;

ZF = 1 quando il risultato di un’operazione è pari a zero;

SF = 1 indica il segno associato al risultato, in questo caso negativo;

……………

In caso di risultato errato viene impostato a 1 il flag di overflow (OF)



44

Esempio: Siano dati i numeri a 4 bit 0010 (+2) e 1010 (-6).

0010+

1010=

_______

1100 (-4)

OF=0, ossia il risultato S è valido, perché i bit più

significativi di X e Y sono diversi.



45

Esempio: Siano dati i numeri a 8 bit 01111110 (+126) e

00000011 (+3)

01111110+

00000011=

___________

10000001

OF=1, ossia il risultato S NON è valido, perché i bit più significativi di X

e Y sono uguali e il bit più significativo di S NON è uguale a loro.



46

Esempio: si consideri la seguente operazione di somma in

complemento a due:

1001 (-7) e 1111 (-1).

Eseguendo la somma, il calcolatore ottiene:

1001+

1111=

_________

1 1000 (-8)

OF=0, ossia il risultato S è valido, perché i bit più

significativi di X e Y sono uguali e il risultato ha il bit più

significativo uguale ad essi.



47

Esercizi

1. Data una rappresentazione in complemento a due con 16 bit

quanti numeri interi positivi e negativi si possono

rappresentare?

2. Effettuare la sottrazione tra il numero decimale 22 e il

numero decimale 33 rappresentati prima in binario con

modulo e segno e poi rappresentati in binario in

complemento a 2.

3. Determinare la rappresentazione in complemento a 2 del

numero decimale -10 con 5 e 12 bit.

48

Esercizi

• Fare la somma dei numeri binari in complemento a 2

codificati su n = 8 bit che corrispondono ai numeri decimali 16

e – 42

• Fare la somma dei numeri binari in complemento a 2

codificati su n = 6 bit che corrispondono ai numeri decimali -5

e –28

49

Esercizi

Si ordinino in modo decrescente i seguenti numeri:

• N1= - 113 in base 10

• N2 = 0100 0111 in base 2

• N3 = 43 in base 16

Quanti bit occorrono per rappresentare N3 ed N1 in

complemento a 2?

Eseguire in complemento a 2 (mostrando i passaggi, indicando

esplicitamente se si verifica overflow e motivando la risposta) le

operazioni:

• N1 + N2

• N1 - N3.

50

Esercizi

Eseguire le seguenti operazioni aritmetiche utilizzando la

rappresentazione in complemento a 2 su 3 bit dei numeri

evidenziando i casi in cui viene impostato a 1 il Flag di Overflow

(Overflow Flag – OF- risultato non valido)

1-1=

3-3=

3-1=

-1-2=

0-2=

1+2=

Fondamenti di Informatica 1 - uniroma2.it · 2n-1-1) e metà valori negativi (da -1 a -2n-1). Si...

Documents

Transcript of Fondamenti di Informatica 1 - uniroma2.it · 2n-1-1) e metà valori negativi (da -1 a -2n-1). Si...