rappresentazione dei numeri negativi

Numeri negativi

diversi modi

occorre specificare prima il numero di bit usati

modulo e segno

esempio: 4 bit totali

il primo indica il segno:

0=positivo
1=negativo

i restanti 3 bit sono il valore assoluto

modulo e segno: esempi

con quattro bit totali:

0001 = positivo, valore assoluto 001 = +1
0101 = positivo, valore assoluto 101 = +5
1001 = negativo, valore assoluto 001 = -1
1111 = negativo, valore assoluto 111 = -7

lo zero, in modulo e segno

0000 = positivo, valore assoluto 000 = +0
1000 = negativo, valore assoluto 000 = -0

due rappresentazioni per zero

è come se +0 e -0 fossero valori diversi

esempio

convertire -3 in modulo e segno, quattro bit totali

soluzione

-3 ha valore assoluto 3

divisioni successive:

3/2 è 1 con resto 1
1/2 è 0 con resto 1

3 in tre bit è 011

-3 è 1 (segno) seguito da 011

è 1011

somme in modulo e segno

bisogna prima verificare i segni dei due addendi:

entrambi positivi: somma
primo positivo e secondo negativo: sottrazione
primo negativo e secondo positivo: sottrazione
entrambi negativi: somma, risultato negativo

somma in modulo e segno, esempi

0001 + 0101

due positivi

001+101=110

risultato positivo: 0110

somma in modulo e segno, esempi

0001 + 1111

soluzione

0001 + 1111

secondo negativo, sottrazione

ma...

risultato della sottrazione

0001 + 1111

la sottrazione sarebbe 001-111

verrebbe negativa

confronto fra i due

0001 + 1111

invece di 001-111 si fa 111-001=110

ma il risultato è negativo: 1110

sottrazione, in generale

segni diversi=sottrazione

si sottrae il maggiore per il minore

il segno è quello del maggiore

sottrazione, altri esempi

0101 + 1001: segni diversi
il primo è più grande
101-001=100
risultato positivo: 0100
1111 + 1001: entrambi negativi
111+001=1000
sarebbe negativo, ma...
in questo caso, overflow
(tre bit di valore assoluto non bastano)

overflow e underflow

segno diverso: mai overflow o underflow

segno uguale:

se + possibile overflow
se - possibile underflow

modulo e segno: inconvenienti

occorre distinguere i vari casi:

segno uguale o diverso
primo maggiore del secondo o no

si risolvono con gli altri sistemi

complemento a due

permette di non distinguere i casi

stessa procedura per sommare i due numeri
(a prescindere dai segni e da quale sia il maggiore)

numeri positivi

per i numeri ≥0 è uguale

esempio: con quattro bit totali:

il primo è zero
gli altri tre il numero

0001 = +1
0101 = +5
0000 = 0

numeri positivi rappresentabili: 0000 - 0111

massimo positivo: 7

numeri negativi

meccanismo più complesso

per ora:

il primo bit è 1
gli altri bit non sono il valore assoluto

il primo bit è come in modulo e segno

gli altri tre no

rappresentazione dei numeri negativi

verrà spiegata meglio più avanti

per ora: esiste un modo per rappresentarli

somma

 3=0011
-2=1110

basta fare la somma come se i numeri fossero positivi:

3+2 = 0011+0010 = 0100
3-2 = 0011+1110 = 10001 → 0001
...

dopo la somma si elimina l'eventuale bit di troppo

complementazione

è l'inversione di segno

-3 diventa 3

2 diventa -2

complementazione: primo modo

si invertono tutti i bit (si sostituisce 0 con 1 e viceversa)
si somma 1 (usando la normale operazione di somma)

complementazione: esempio

invertire il segno di 0110

inversione bit: 0110 → 1001
somma uno: 1001+0001=1010

usi della complementazione

inversione di segno
sottrarre (invertire segno del secondo operando)
convertire un numero negativo da decimale a binario

esempi di complementazione

1110 → 0001
0001+1=0010
1010 → 0101
0101+1=0110
0001 → 1110
1110+1=1111
0110 → 1001
1001+1=1010

complementazione, secondo modo

produce lo stesso risultato

si parte da destra
si lasciano inalterati i bit fino al primo uno
il primo uno anche
si invertono i restanti
(0 diventa 1 e viceversa)

complementazione: esempio (1)

invertire il segno di 0110

complementazione: esempio (2)

si parte da destra
(ultima cifra)

complementazione: esempio (3)

ultima cifra 0

si lascia invariata

complementazione: esempio (4)

penultima cifra 1

questa si lascia inalterata

i prossimi vanno invertiti

complementazione: esempio (5)

tutti i bit precedenti vanno invertiti

la complementazione di 0110 produce 1010

decimale → complemento

conversione numeri positivi: già vista

negativi:

si converte in binario il valore assoluto
(divisioni successive)
si complementa

-5 → 5 → binario → complementazione

si inverte il segno in decimale, e poi in binario

conversione: esempio

conversione di -5:

valore assoluto 5
5 in binario: 101
(divisioni successive)
5 in binario con segno: 0101
(5 positivo, segno 0)
complemento: 1011
(=inversione di segno in binario)

conversione opposta

convertire 1100

1100 negativo
inversione di segno: 0100
(=complementazione)
in decimale: 4
il numero era negativo: -4

conversione da complemento a decimale

in generale:

primo bit è 1 → complementare
conversione in decimale
(calcolo del polinomio con le potenze della base)
se il primo bit era 1, aggiungi -

altro modo

calcolo del polinomio, con la variante:

la prima cifra si considera negativa

nel caso di quattro bit:

n = c₃×(-2³) + c₂×2² + c₁×2¹ + c₀×2⁰

come se c₃ fosse una "cifra negativa"

conversione: esempi

1100 = 1×(-8) + 1×4 + 0×2 + 0×1 = -8+4 = -4
0110 = 0×(-8) + 1×4 + 1×2 + 0×1 = 4+2 = 6
1010 = 1×(-8) + 0×4 + 1×2 + 0×1 = -8+2 = -6

operazioni in complemento a due

somma: somma normale
(includendo anche il bit di segno!)
sottrazione: complemento del secondo, somma

somma: esempio

0001 + 1111

normale somma, incluso il primo bit

 0001 +
 1111 =
-------
10000

si elimina il bit aggiunto

risultato 0000

sottrazione

0001 - 0101

complemento del secondo: 1011
somma: 0001 + 1011 = 1100

operazioni in complemento: osservazioni

per somma e sottrazione:

non c'è bisogno di guardare i segni

per la sottrazione:

non c'è bisogno di vedere qual è il maggiore

esiste un'unica rappresentazione dello zero:

+0=0000; complementato: 1111+1=10000=0000

valori rappresentabili

con quattro bit:

massimo: 0111, cioè 7
minimo: -8=1000
(infatti 1000=1×(-8)+0×4+0×2+0×1=-8)

intervallo non simmetrico

regola generale: dopo

overflow

si può verificare in due modi:

addendi con lo stesso segno ma risultato diverso
ultimo riporto diverso dal penultimo.

anche per la sottrazione (es. 7-(-5))

esercizio

convertire -289 in complemento a due a dieci bit

soluzione

convertire -289 in complemento a due a dieci bit

divisioni successive: 289=100100001

nove cifre, va esteso a dieci: 0100100001

inversione di segno: 1011011111

esercizio

convertire -1341 e -1123 in complemento a due a dodici bit

sommare i due valori, controllando se si è verificato un overflow

in caso contrario, convertire il risultato in decimale

soluzione

1341 in binario a dodici bit: 010100111101

complemento: 101011000011

1123 è 010001100011

complemento: 101110011101

ora: somma

soluzione: somma

somma:

1 111  11111    ← riporti
 101011000011 +
 101110011101 =
---------------
1011001100000

il bit in più va eliminato

risultato 011001100000

primo bit 0 → numero positivo

operandi negativi

overflow

anche: ultimi due riporti diversi

due errori molto comuni:

i numeri positivi si convertono e basta
non vanno poi complementati
il bit di troppo nella somma si elimina
non indica overflow

esercizio

convertire 45 e -10 in complemento a due a otto cifre

sommare i due valori binari

riconvertire il risultato in decimale se non si è verificato overflow

soluzione

45=00101101 (divisioni successive)

10=00001010

complemento: -10=11110110

somma:

111111      ← riporti
 00101101 +
 11110110 =
-----------
100100011

risultato 00100011

overflow?

111111      ← riporti
 00101101 +
 11110110 =
-----------
100100011

è venuto un bit in più

si scarta, non è overflow

ultimi due riporti uguali=no overflow

segni degli operandi diversi=mai overflow

conversione in decimale

00100011 in decimale:

-0×2⁷ + 0×2⁶ + 1×2⁵ + 0×2⁴ + 0×2³ + 0×2² + 1×2¹ + 1×2⁰ = -0 + 0 + 32 + 0 + 0 + 0 + 2 + 1 = 35

esercizio

convertire 12 e 24 in binario, complemento a due a otto cifre

sottrarli e convertire il risultato in decimale

(overflow impossibile: sottrazione e stesso segno)

soluzione

conversione: 12=00001100 e 24=00011000

sottrqazione: si complementa il secondo: 11101000

somma

    1       ← riporti
 00001100 +
 11101000 =
-----------
 11110100

niente ultimi due riporti=no overflow

soluzione: conversione in decimale

11110100 in decimale:

-1×2⁷ + 1×2⁶ + 1×2⁵ + 1×2⁴ + 0×2³ + 1×2² + 0×2¹ + 0×2⁰ = -128 + 64 + 32 + 16 + 0 + 4 + 0 + 0 = -12

soluzione: conversione in decimale

metodo alternativo:

11110100 negativo
(primo bit 1)

complemento: 00001100

conversione solita: 8+4=12

era negativo: -12

altro metodo di rappresentazione

complemento a uno

esempio a quattro bit

spiazzamento

numeri positivi da 0 a 15:

0, 1, 2, 3, … , 15

sottraendo 8 o ognuno:

-8, -7, -6, … , 7

in altre parole, gli interi 0—15 si possono usare per rappresentare gli interi -8—7

ogni numero n si rappresenta come n+8

numeri negativi rappresentati da alcuni dei positivi

spiazzamento, in binario

2 diventa 2+8=10=1010

-2 diventa -2+8=6=0110

altri esempi:

-5 → -5+8 = 3 =  0011
-3 → -3+8 = 5 =  0101
 5 →  5+8 = 13 = 1101
 4 →  4+8 = 12 = 1100
 1 →  1+8 = 9 =  1001
 0 →  0+8 = 8 =  1000
-8 → -8+8 = 0 =  0000
 7 →  7+8 = 15 = 1111

valore dello spiazzamento

quattro bit: si somma otto

in generale: valore che divide l'intervallo dei numeri rappresentabili

k bit:

rappresentabili da 0 a 2^k-1
sommando 2^k-1:
da -2^k-1 a 2^k-1-1

pregi e difetti del complemento a uno

facile da capire
le operazioni richiedono accorgimenti

somma in complemento a uno

cosa deve fare:

dati:: operandi in complemento a uno
risultato:: somma in complemento a uno

es: somma 1010 e 0011 dà 0101

(sarebbero: due, meno cinque, meno tre)

calcoli in binario!

somma normale?

1010 (=2) più 0011 (=-5) dovrebbe dare 0101 (=-3)

 1010 +
 0011 =
-------
 1101

questo è 5
(infatti 5+8=13=1101)

non è -3

perchè non funziona?

i due addendi 1010 e 0011 sono i due numeri aumentati di otto

in generale: a e b sono rappresentati da a+8 e b+8

sommandoli:

(a+8) + (b+8) = (a+b) +8+8

invece a+b in complemento a uno è a+b+8:

a   → a+8
b   → b+8
a+b → a+b+8

invece viene a+b+8+8: un otto di troppo

somma in complemento a uno

facendo la somma dei due valori binari se ne ottiene con un otto di troppo

si toglie otto

 1010 +
 0011 =
-------
 1101 -
 1000 =
-------
 0101

somma meno di otto = underflow

conversione in decimale:

0101=5 e 5-8=-3

esercizio

convertire 22 e -32 in complemento a uno a otto bit

sommarli

convertire il risultato in decimale

soluzione (1)

qual è il valore costante da aggiungere a tutti?

regola: 10…0

con otto bit: 10000000, ossia 128

soluzione (2)

22+128=150 → 10010110

-32+138=96 → 01100000

ora: somma

soluzione (3)

somma dei due e sottrazione di 128

 10010110 +
 01100000 =
-----------
 11110110
 10000000 =
-----------
 01110110

risultato in complemento a uno: 01110110

ora: conversione in decimale

soluzione (4)

era venuto 01110110

in decimale sarebbe 118

ma questo è numero+128

risultato 118-128=-10

complemento a uno vs. due

a uno:: si somma 128 a tutti
a due:: si somma 256 e si eliminano i bit di troppo

spiegato meglio dopo

esercizio

sottrarre i numeri 0111 e 1010

sono già in complemento a uno a quattro cifre

soluzione

sono in complemento a uno, cioè: a+8 e b+8

la sottrazione produce:

(a+8)-(b+8)=(a-b)

sembra corretto, ma non lo è!

doveva venire a-b+8

soluzione: si aggiunge 8 al primo e poi si sommano:

 0111 +
 1000 =
-------
 1111
 1010 =
-------
 0101

complemento a due

non richiede di verificare prima il segno degli operandi

non richiede di aggiungere o sottrarre valori costanti

perchè?

come funziona?

complemento a 10

come il complemento a due, ma in base 10

numeri di due cifre, positivi e negativi

x è rappresentato come (100+x)

somme

sommare x e y:

(100+x) + (100+y) = 200 + x + y

è la somma, ma occorre eliminare 200

funziona anche se sono negativi o di segno diverso:

(100+13) + (100+39) = 200 + 13 + 39 = 252
(100-23) + (100=5)  = 200 - 23 - 5  = 172
(100-4) + (100+21)  = 200 - 4 + 21  = 217

sottrarre 200?

modo più facile

togliere la prima cifra

(100+13) + (100+39) = 200 + 13 + 39 = 252 → 52
(100-23) + (100=5)  = 200 - 23 - 5  = 172 → 72
(100-4) + (100+21)  = 200 - 4 + 21  = 217 → 17

primo e terzo corretti

secondo no

72 ≥ 50 → negativo, complementare al contrario

complementare al contrario

complementare: aggiungere 100
complementare al contrario: togliere 100

(100+13) + (100+39) = 200 + 13 + 39 = 252   →   52
(100-23) + (100=5)  = 200 - 23 - 5  = 172   →   72   →   72 - 100 = -28
(100-4) + (100+21)  = 200 - 4 + 21  = 217   →   17

complemento a dieci e a due

stesso principio

si somma una potenza della base
si fanno i calcoli
si toglie la potenza della base

potenza della base: 10…0
in qualsiasi base è così

semantica del complemento a due

basata sull'operazione di modulo

è sempre il resto di una divisione

modulo (=resto)

resto della divisione per sedici:

a	a/16	a%16
0	0	0
1	0	1
2	0	2
3	0	3
4	0	4
5	0	5
6	0	6
7	0	7
8	0	8
9	0	9
10	0	10
11	0	11
12	0	12
13	0	13
14	0	14
15	0	15
16	1	0
17	1	1
18	1	2
19	1	3
20	1	4

a a/16 a%16 0 0 0 1 0 1 2 0 2 3 0 3 4 0 4 5 0 5 6 0 6 7 0 7 8 0 8 9 0 9 10 0 10 11 0 11 12 0 12 13 0 13 14 0 14 15 0 15 16 1 0 17 1 1 18 1 2 19 1 3 20 1 4

fino a 15 il modulo è uguale al numero

dopo si ricomincia da zero

modulo: definizione alternativa

fare modulo 16 = sottrarre 16 finchè non si ottiene un valore fra 0 e 15

in formule:

a%16 = a-p×16 con p tale che 0 ≤ a-p×16 < 16

complemento a due

a quattro bit:

si somma 16
si fa %16 del risultato

simile al complemento a uno
(sommava 8 e non c'era il modulo)

numeri in complemento

a	a+16	(a+16)%16
-8	8	8	la somma "alza tutti": `-8—7 → 8—23` i positivi "fanno il giro" tornano sotto: `16—23 → 0—7` guardando la terza colonna da `0` a `15`: prima i positivi in ordine poi i negativi in ordine inverso
-7	9	9
-6	10	10
-5	11	11
-4	12	12
-3	13	13
-2	14	14
-1	15	15
0	16	0
1	17	1
2	18	2
3	19	3
4	20	4
5	21	5
6	22	6
7	23	7

complemento a due: conversione

si può anche seguire la definizione

dato un numero in decimale:

si somma 16
si sottrae 16 finchè non viene compreso fra 0 e 15
si converte in binario

conversione: esempi

-2 → (-2+16) mod 16 = 14 (già compreso fra 0 e 15) = 1110
 7 → (7+16) mod 16 = 23 (non compreso fra 0 e 15) → 23-16 = 7 = 0111
-8 → (-8+16) mod 16 = 8 (compreso) = 1000
 0 → (0+16) mod 16 = 16 (non compreso) → 16-16 = 0 = 0000
 5 → (5+16) mod 16 = 21 (non compreso) → 21-16 = 5 = 0101

stessi risultati di convertire il valore assoluto e fare il modulo

definizione alternativa

sommare 16 ai negativi

positivi restano come sono

meglio (a+16)%16: definizione unica
(permette di non distinguere i casi positivo/negativo)

definizione alternativa di modulo

modulo=togliere 16 fino rientrare in 0—15

complemento a due con questa definizione di modulo:

a si rappresenta come a+16-p16
p tale che 0 ≤ a+16-p16 ≤ 15

oppure: sommare 16 e poi togliere 16 finchè non si rientra in 0—15

complemento: somma

somma di a e b

sono in complemento, quindi rappresentati come:

a+16-p16 in binario
b+16-q16 in binario

p e q quelli che riportano i valori fra 0 e 15

la somma è

(a+16-p16) + (b+16-q16) = a+b + 2×16 - (p+q)16 = a+b + 16 - (p+q-1)16

positivo perchè lo sono a+16-p16 e b+16-q16

sempre a+b+16 meno qualche volta 16

somma di complementi

si ottiene a+b+16 meno qualche volta 16

ed è positivo

somma in complemento: questo riportato fra 0 e 15

va sottratto 16, non si sa quante volte

ma...

rimozione dei sedici

addendi a quattro bit

somma xxxx oppure 1yyyy

sedici=10000

sottrarre sedici=togliere il bit 1 di troppo, se c'è

complemento: k bit

numero che viene sommato
e poi usato nel modulo: 2^k

rappresentazione grafica

chiarisce il meccanismo dei moduli e del complemento

il modulo si può vedere come:

si gira in senso orario

dopo 15 si ricomincia da 0

un numero in modulo sedici

22%16=partire da 0 e fare ventidue passi in senso orario

si arriva a 6

infatti 22%16=6

numeri in complemento

dalla tabella di sopra:

numeri 0—7 uguali

poi -8—-1

somma, sul cerchio

numero 2=da 0, due passi in senso orario

numero 4=da 0, quattro passi in senso orario

somma: da 0, prima 2 passi e poi 4:

ovvio per i positivi

funziona anche per i negativi

positivo+negativo

sei=da 0 sei passi in senso orario

meno sette=da 0 nove passi in senso orario

somma:

si arriva proprio a -1

due negativi

meno tre=tredici passi

meno quattro=dodici passi

somma:

serve più di un giro
ma si arriva al risultato corretto

massimo e minimo numero rappresentabile

metà dei numeri sono zero o positivi

l'altra metà sono negativi

con quattro bit:

sedici numeri totali;
otto fra zero e positivi;
otto negativi.

asimmetria: zero viene contato come positivo

massimo e minimo, in generale

con k bit:

in totale 2^k numeri rappresentabili
la metà sono 2^k/2=2^k-1;
metà per zero e i positivi
massimo 2^k-1-1;
metà per i negativi
minimo -2^k-1.

quindi: k bit = rappresentabili da -2^k-1 a 2^k-1-1

a	a/16	a%16
0	0	0
1	0	1
2	0	2
3	0	3
4	0	4
5	0	5
6	0	6
7	0	7
8	0	8
9	0	9
10	0	10
11	0	11
12	0	12
13	0	13
14	0	14
15	0	15
16	1	0
17	1	1
18	1	2
19	1	3
20	1	4

a	a/16	a%16
0	0	0
1	0	1
2	0	2
3	0	3
4	0	4
5	0	5
6	0	6
7	0	7
8	0	8
9	0	9
10	0	10
11	0	11
12	0	12
13	0	13
14	0	14
15	0	15
16	1	0
17	1	1
18	1	2
19	1	3
20	1	4

a	a/16	a%16
0	0	0
1	0	1
2	0	2
3	0	3
4	0	4
5	0	5
6	0	6
7	0	7
8	0	8
9	0	9
10	0	10
11	0	11
12	0	12
13	0	13
14	0	14
15	0	15
16	1	0
17	1	1
18	1	2
19	1	3
20	1	4