Rappresentazione numeri con e senza segno ([PH] par. 2.4)

Giovedì 1 ottobre 2015 (ore 9-13)

Punto della situazione

• Abbiamo visto:– la rappresentazione dei numeri positivi con e senza

virgola nel sistema posizionale; in particolare basi 2, 8, 10, 16 e conversioni

– Codifica simboli non numerici (ASCII)

• Oggi vedremo le rappresentazioni per numeri con il segno; in particolare la rappresentazione in complemento a 2 e la sua aritmetica.

• Oggi 4 ore: lezione ed esercitazioni

• Domani: né lezione né ricevimento

Rappresentazione in complemento a 2: vantaggi

• Una sola rappresentazione per lo zero

• Intervallo di rappresentazione: [-2n-1 , 2n-1 – 1 ]

per es. con 4 bit [-8, +7] anzichè [-7, +7]

• L’aritmetica è più semplice

• Cambiare di segno/ ottenere l’opposto è ancora semplice.

• Un’osservazione….

Somma di potenze consecutive di 2

26+ 25+ 24+ 23+ 22 = 26+ 25+ 24+ 23+ 22 + 21 + 20

– ( 21 + 20 )== (27 – 1) – (22 – 1) = 27 – 22

hkk

hi

i 222 1

122 1

0

kk

i

i

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

Complemento a Due

• Il bit più a sinistra/più significativo viene utilizzato come segno:

– 0 significa positivo

– 1 significa negativo

• Il peso del bit di segno è negativo

• Il valore di bn-1bn-2…b0 è dato dalla relazione

2

0

1

1 22n

i

i

i

n

n bbN

Esempio con n=4 bit

0 000 = 0

0 001 = 1

0 010 = 2

0 011 = 3

0 100 = 4

0 101 = 5

0 110 = 6

0 111 = 7

1 000 = -8

1 001 = -8 +1=-7

1 010 = -8+2=-6

1 011 = -8+3 =-5

1 100 = -8+4=-4

1 101 = -8+5=-3

1 110 = -8+6=-2

1 111 = -8+7=-1Massimo=7

minimo=-8

Intervallo di rappresentazione con 4 bit: [-8, +7]

Esempio con n=32 bit

0 0…00 = 0

0 0…01 = 1

0 0…10 = 2

0 0…11 = 3

….

0 1…10 = 231 - 2

0 1 …11 = 231 - 1

1 0…00 = - 231

1 0…01 = -231 +1

1 0…10 = -231 +2

1 0…11 = -231 +3

………..

1 1…10 = -231 +231 – 2=-2

1 1…11 = -231 +231 – 1=-1Massimo= 231 - 1

minimo=- 231

Intervallo di rappresentazione con 32 bit: [- 231, 231 -1]

Numeri Rappresentabili

• 8 bit in Complemento a 2

+127 = 01111111 = 27 -1

-128 = 10000000 = -27

• 16 bit in Complemento a 2

+32767 = 011111111 11111111 = 215 - 1

-32768 = 100000000 00000000 = -215

• 32 bit in Complemento a 2

+ 2 147 483 647 = 0111……..111 = 231 - 1

- 2 147 483 648 = 1000………000 = -231

Intervallo di rappresentabilità

Numeri rappresentabili con n bit in Complemento a 2

minimo: 1000………000 = -2n-1

Massimo: 0111……..111 = 2n-1 – 1

[-2n-1 , 2n-1 – 1 ]

Vantaggi

• Una sola rappresentazione per lo zero

• L’aritmetica è più semplice

• Cambiare di segno/ ottenere l’opposto è ancora semplice.

– La rappresentazione in complemento a 2 di un intero negativo si può ottenere trovando la rappresentazione in complemento a 2 del suovalore assoluto e calcolando poi l’opposto.

Cambiamento di segnoCambiare di segno è semplice.Algoritmo 1:

• Si esegue il complemento bit a bit o negazione (sitrasforma ogni 1 in 0 e viceversa)

• Si somma 1

Esempio:Con 8 bit: 310 = 00000011

Si esegue il complemento bit a bit 11111100+Si somma +1 1=

1111110111111101=11111111-10= -110 -210 = - 310

Sarà un caso?

Non è un casoCambiare di segno è semplice:

• Si esegue il complemento bit a bit (si trasforma ogni 1 in 0 e viceversa)

• Si somma 1

Perchè funziona?

Se sommiamo un numero x e il suo complemento c(x)

00000011 +

11111100 =

11111111

Otteniamo 111….111 che in complemento a 2 è -1.

Quindi: x + c(x) = -1

- x = c(x) + 1

Cambiamento di segno (2)

Algoritmo 2:• Partendo da destra si lasciano invariati tutti i bit

fino al primo 1 compreso, poi si invertono irimanenti

Rivediamo:

1210 = 00001100 c’è un modo diretto?11110011+

1=11110100

Il caso dello 0

Proviamo a cambiare di segno lo 0 rappresentato con n=8 bit con l’ Algoritmo 1.

0 = 00000000Negazione: 11111111+Somma di 1: 1 =Risultato: 1 00000000La cifra più a sinistra si perde (8 bit), quindi:

- 0 = 0

Proviamo a cambiare di segno il minimo rappresentato con n=8 bit con l’ Algoritmo 1.

-128 = - 27 = 10000000Negazione: 01111111+Somma di 1: 1 =Risultato: 10000000 = -128 !!!

In realtà sappiamo che con 8 bit l’intervallo di rappresentazione è [- 27, 27 -1] = [-128, 127]128 non apparteiene all’intervallo di rappresentabilità: c’è overflow!

Il caso del minimo

Estensione del segno• Per i numeri positivi si aggiungono 0 nella parte più

significativa+18 = 00010010 = 24+ 2= 18

+18 = 00000000 00010010 = 24+ 2= 18

• Per i numeri negativi si aggiungono 1 nella parte piùsignificativa-18 = 101110= -25+ 23+ 22+2= -32 +14=-18

-18 = 1111 101110 = -29+(28 + … + 25) + 23+ 22+2 =

= -29+(29 - 25) + 23+ 22+2 = -25+ 23+ 22+2= -18

• Regola dell’estensione del segno: Si completa la rappresentazione riportando a sinistra il bit piùsignificativo.

Aritmetica in binario

La somma in binario

1010110101110 +

1101011101101 =

Non sono un problema

0+0=0

0+1=1

1+0=1

Sono un problema

1+1= ?210

Regole

0

1

0 1+

0 1

1 0

0

1

0 1

0 0

0 1

c

Somma Riporto

an-1…ai…a2a1a0 +

bn-1…bi…b2b1b0 =

s0s1s2sisn-1

c1c2cicn-1cn

sn

Addizione

……

si bit di sommaci bit di riporto / carry

Esempio

1010110101110 +

1101011101101 =

1101100100001

10 011 01111111

1

Un caso particolare

1 1 1 1 1 1 +

1 =

000000

1 11111

1

In generale:

2n-1+ 2n-2+ … +21 + 20 = 2n-1

1221

0

nn

i

i

(1 1 1 … 1 1) 2 = 2n-1+ 2n-2+ … +21 + 20

(1 1 1 … 1 1) 2 + 1 = (1 0 0 0 … 0 0 ) 2 = 2n

Da cui: (1 1 1 … 1 1) 2 = 2n - 1

n

n

n

n

Formula da ricordare!Dimostrata classicamente per induzione

Un’altra prova

2n-1+ 2n-2+ … +21 + 20 = 2n-1

1221

0

nn

i

i

(0 0 0 … 0 0 ) 2 = 0

(1 1 1 … 1 1) 2 = 2n - 1

n

n

Dimostrazione:Con n bit posso rappresentare gli interi da 0 0 0 … 0 0 a 1 1 1 … 1 1

(00…0 è il più piccolo, 11…1 è il più grande possibile)

Con n bit è possibile rappresentare tutti i 2n interi compresi fra 0 e 2n-1

n n

Un caso particolare

1 1 1 1 1 1 +

1 =

000000

1 11111

1

(111111)2 = 127 può essere rappresentato con 6 bit

(1000000) 2 = (111111)2 + 1 = 128 necessita di 7 bit

Nota: La somma di due numeri rappresentati con n bit può essere un numero che necessita di n+1 bit per essere rappresentato, cioè un numero che supera 2n -1: OVERFLOW!Overflow = traboccamento

Aritmetica in complemento a due

Complemento a Due

• Il bit più a sinistra viene utilizzato come segno.

• 0 significa positivo

• 1 significa negativo

• Il peso del bit di segno è negativo

• Il valore di bn-1bn-2…b0 è dato dalla relazione

2

0

1

1 22n

i

i

i

n

n bbN

Somma e Sottrazione in complemento a 2

• Somma

– Si utilizza la normale somma binaria

– L’ultimo (l’n-esimo) bit di riporto si ignora

– Alla fine bisogna controllare la consistenza dei segni: se non c’è consistenza significa che siamo in presenza diunnumero al di fuori dell’intervallo di rappresentazione: questa situazione si chiama overflow o traboccamento.

• Sottrazione

– Si calcola l’opposto del sottraendo e si somma al minuendo

– a - b = a + (-b)

• Avremo quindi bisogno dei soli circuiti di somma e complemento

Più in dettaglio….

Maggiori dettagli ([P] 6.2)

A= an-1an-2…a0 , B= bn-1bn-2…b0 , A+B= sn-1sn-2…s0

1. A≥0, B ≥0 e A+B ≥2n-1 (overflow): sn-1=1 (somma negativa!)

2. A<0, B<0 e A+B ≥2n-1 (overflow): sn-1=0 (somma positiva!)

3. A≥0, B<0 e |A| ≥ |B|: corretto ignorando l’n-esimo riporto

4. A≥0, B<0 e |A| < |B|: corretto

Si usa che se B<0 allora bn-1=1 e il valore di bn-2…b0 è uguale a 2n-1 -|B|.

Esempio: n=4; B=1011=-5; 011=3 = 8 - 5

Caso 1: A ≥ 0, B ≥ 0

Somma di positivi è negativa: traboccamento!

Corretto!

Caso 2: A < 0 B < 0 (es. 6.5 corretto)

Somma di negativi è positiva: traboccamento!

Corretto: trascurare riporto!

1 0 0 0 1 11 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0

Casi 3 e 4: A ≥ 0 , B<0

• 3

• 4

Corretto: trascurare riporto!

Regola

La somma in complemento a 2 si fa come nel caso binario tranne che:• Si trascura l’eventuale bit di riporto finale (cn)• Si deve controllare la consistenza dei segni: se la

somma di positivi è negativa o la somma di due negativi è positiva significa che c’è traboccamento/overflow (altrimenti il risultato è corretto)

Dimostrazione del caso generale: facoltativa ([P] par. 6.2)