Aritmetica in complemento a due

29 settembre 2017

Complemento a Due

• Differenza con il sistema posizionale: il peso del bit piùsignificativo è negativo

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

2

0

1

1 22n

i

i

i

n

n bbN

• 00010010 = + 24+ 2= 18

• 10010010 = −27+ 24+ 2= −128+18 = −110

• 111111 = −25+ 24+ 23+ 22+ 21+ 20= − 25 + 25−1= −1

• 111101=−25+ 24+ 23+ 22+ 20= − 32 + 29 = −3

Positivi e negativi

Esercizio

Dimostrare che nella rappresentazione bn-1 bn-2 … b0 in complemento a due dell’intero N:

• Se bn-1 = 0 allora N ≥ 0

• Se bn-1 = 1 allora N < 0

Osservazione: Il bit più significativo ci indica il segno:0 significa positivo1 significa negativo

Perché «complemento a 2»?

Sia B= bn-1 bn-2…b0

Se B 0 allora bn-1=0 e il valore di bn-2…b0 è uguale a|B|.

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

Cioè il complemento a 2n-1 di |B|.

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

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 ]

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]

Vantaggi

• Una sola rappresentazione per lo zero

• L’aritmetica è semplice: l’algoritmo per l’addizione è indipendente dal segno degli operandi

• 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 suo valore assoluto e calcolando poi l’opposto

• La sottrazione si può fare sommando al minuendo l’opposto del sottraendo

Cambiamento di segno: algoritmo 1Algoritmo 1:

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

• Si somma 1

Esempio:Con 6 bit: 310 = 000011

Si esegue il complemento bit a bit 111100+

Si somma +1 1=

111101

111101= −25+ 24+ 23+ 22+ 20= − 32 + 29 = − 310

Cambiamento di segno: algoritmo 2

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

primo 1 compreso, poi si invertono i rimanenti

Esempio:

1210 = 0000110011110011+

1=11110100 11110100 = 10100 = −24+ 22= − 16 + 4 = − 1210

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.

Addizione in complemento a 2

La somma in complemento a 2 si calcola 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 è positiva o la somma di due negativi è negativa allora il risultato è corretto. Altrimenti l’operazione non poteva essere fatta perché c’è traboccamento/overflow: il risultato non è rappresentabile con quel numero di bit.

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

EsempiEsempio 1 (n=6 bit):12 + 6

12 = 0011006 = 000110

0 01100001100 +000110 =010010

X

Esempio 2 (n=6 bit):25 + (−13)

25 = 011001−13 = 110011

1 10011011001 +110011 =001100

X

Corretto!010010= 24+ 2=18

12+6=18

Corretto! 001100= 23+ 22=12

25 + (−13)=12

EsempiEsempio 3 (n=6 bit):13 + 23

13 = 00110123 = 010111

0 11111001101 +010111 =100100

X

Esempio 4 (n=6 bit):−13 + (−23)

−13 = 110011−23 = 101001

1 00011110011 +101001 =011100

X

Overflow!100100 = − 25+ 22= − 28

13+23=36 non rappresentabile con 6 bit

Overflow! 011100= 24+ 23+ 22=28−13 + (−23) = −36 non

rappresentabile con 6 bit

n=6intervallo rappresentabilità

[-32, 31]

Sottrazione in complemento a 2

• 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 negazione dei bit

Cosa cambia nell’addizione in complemento a due?

an-1…ai…a2 a1a0 +

bn-1…bi…b2b1b0 =

s0s1s2sisn-1

c1c2ci…cn-1 …cn

sn ……

Il contributo di cn-1 è sempre +cn-12n-1.

In binario (puro) il contributo di an-1 è +an-12n-1,

quello di bn-1 è +bn-12n-1 e quello di sn-1 è +sn-12

n-1.

Invece, in complemento a due, il contributo di an-1 è −an-12n-1, quello di bn-1 è

−bn-12n-1 e quello di sn-1 è − sn-12

n-1.

Correttezza dell’algoritmo ([P] 6.2, facoltativo)

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

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

altrimenti corretto

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

altrimenti corretto ignorando l’n-esimo riporto

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

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

Caso 1: A ≥ 0, B ≥ 0, n=4 bit (facoltativo) • A= a3a2a1a0, B= b3b2b1b0

• a3= b3= 0

• s2s1s0 ≤ 23 – 1 =7

a3 a2 a1 a0 +

b3b2 b1 b0 =

s0s1s2s3

c1c2c3c4

Se c’è overflow allora A+B ≥ 23=8, quindi c3= 1, s3= 1, c4= 0

Il risultato è negativo: non è corretto in complemento a due!

Se non c’è overflow allora A+B ≤ 7 quindi c3= 0, s3= 0, c4= 0

Risultato corretto.

c0

0 1 1 0 +

0 0 1 1 =

1001

0 1 1 0 6 +

3 =

9 in binario, ma-7 in complemento a due

Caso 1: A ≥ 0, B ≥ 0 (facoltativo) • A= an-1an-2…a0 , B= bn-1bn-2…b0

• an-1= bn-1= 0

• sn-2…s0 ≤ 2n-1 – 1

an-1an-2 … a1 a0 +

bn-1bn-2 … b1 b0 =

s0s1sn-2sn-1

c1cn-2cn-1cn

…

Se c’è overflow allora A+B ≥ 2n-1 quindi cn-1= 1, sn-1= 1, cn= 0

Se non c’è overflow allora A+B ≤ 2n-1 – 1 quindi cn-1= 0, sn-1= 0, cn= 0

Caso 1: A ≥ 0, B ≥ 0, esempi

Somma di positivi è negativa: traboccamento!

Corretto!

Caso 2: A < 0, B < 0 (facoltativo) • A= an-1an-2…a0 , B= bn-1bn-2…b0

• an-1= bn-1= 1

• 0 ≤ sn-2…s0 ≤ 2n-1 – 1

an-1an-2 … a1 a0 +

bn-1bn-2 … b1 b0 =

s0s1sn-2sn-1

c1cn-2cn-1cn

…

Se c’è overflow allora A+B < – 2n-1 quindi cn-1= 0, sn-1= 0, cn= 1

Se non c’è overflow allora A+B > 2n-1 quindi cn-1= 1, sn-1= 1, cn= 1

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

Somma di negativi è positiva: traboccamento!

Corretto: trascurando 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, esempi

• 3

• 4

Corretto: trascurando riporto!

Regola alternativa per l’overflow

Dalle considerazioni fatte nei vari casi si ottiene un’altra regola per determinare l’overflow.

Se cn-1= cn il risultato è corretto.

Si ha invece overflow ogni qual volta cn-1 cn

Sottrazione con la ALUPer eseguire A − B, la ALU eseguirà A + (− B).

A= an-1an-2 … a1 a0 e B= bn-1bn-2 … b1 b0

−B= bn-1bn-2 … b1 b0 + 1

an-1an-2 … a1 a0 +

bn-1bn-2 … b1 b0 +

1 =

s0s1sn-2sn-1

c1cn-2cn-1cn

…

an-1an-2 … a1 a0 +

bn-1bn-2 … b1 b0 +

s0s1sn-2sn-1

c1cn-2cn-1cn

…

c0=11

e poi controlla l’overflow

Esercizi da [PH]: 3.1 – 3.11da [P]: 6.1 – 6.4

Esercizi

• Eseguire l’operazione 5ED4 − 07A4 direttamente in esadecimale.

• Eseguire l’operazione 5E24 − 07A4 direttamente in esadecimale.

• Eseguire l’operazione 1011 − 0010 direttamente in binario.

• Eseguire l’operazione 1100 − 1010 direttamente in binario.

• Eseguire l’operazione 1100 − 1010 passando per la rappresentazione in complemento a due.

Per ogni operazione è necessario giustificare le operazioni svolte e verificarne la correttezza esprimendo ogni numero in decimale.