Lezione 03 · Rappresentazione dei numeri relativi in binario¶

Nella lezione 02 hai convertito solo numeri positivi. Ma un calcolatore deve gestire anche temperature sotto zero, saldi in rosso, quote sotto il livello del mare. In memoria non c'è un simbolo "−": ci sono solo bit. Serve quindi una regola per decidere quali parole di bit rappresentano i numeri negativi.

In tutta la lezione l è il numero di bit a disposizione e la parola codice ha sempre esattamente l bit (si aggiungono zeri a sinistra se servono).

Binario puro: i numeri naturali¶

La rappresentazione vista finora si chiama binario puro. Con l bit hai 2ˡ parole codice e rappresenti i numeri naturali da 0 a 2ˡ − 1.

Intervallo: [0, 2ˡ − 1]

Con l = 8 rappresenti i numeri da 0 a 255. Nessun numero negativo.

Perché tante rappresentazioni?¶

I numeri relativi sono gli interi positivi, negativi e lo zero. Esistono più modi di rappresentarli: segno e modulo, complemento a uno, complemento a due, eccesso. Ognuno nasce per rendere più semplici ed efficienti i circuiti che fanno i calcoli nel processore. Vediamoli uno alla volta.

Segno e modulo¶

È l'idea più naturale, simile a come scriviamo i numeri a mano:

• il bit più a sinistra (MSB) è il segno: 0 per positivo, 1 per negativo;
• gli altri l − 1 bit contengono il modulo (valore assoluto) in binario puro.

Intervallo: [−(2ˡ⁻¹ − 1), 2ˡ⁻¹ − 1]. Con l = 8: da −127 a +127.

Un numero non è rappresentabile se il suo modulo non entra in l − 1 bit. Ad esempio su 6 bit l'intervallo è [−31, 31]: −33 non è rappresentabile.

Svantaggi

1. Lo zero ha due rappresentazioni: 00000000 (+0) e 10000000 (−0). Si spreca una parola codice: le 2ˡ parole rappresentano solo 2ˡ − 1 valori diversi.
2. La somma è complicata: bisogna prima guardare i segni.
   • Segni uguali: sommi i moduli e metti davanti il segno comune.
   • Segni diversi: sottrai il modulo minore dal maggiore e metti il segno del numero con modulo maggiore.

Il complemento¶

Data una sequenza di k cifre che rappresenta il numero N in base b:

• complemento alla base: Cb = bᵏ − N;
• complemento alla base diminuita: Cd = Cb − 1 = (bᵏ − 1) − N.

In binario (b = 2) diventano:

Complemento a uno¶

Per codificare X su l bit:

• se X ≥ 0 lo scrivi in binario puro (il primo bit sarà 0);
• se X < 0 scrivi |X| in binario puro su l bit e inverti tutti i bit. In formula: Y = 2ˡ − |X| − 1.

Intervallo: [−(2ˡ⁻¹ − 1), 2ˡ⁻¹ − 1], simmetrico, come segno e modulo. Il MSB indica ancora il segno: 0 positivo, 1 negativo.

Anche qui lo zero ha due rappresentazioni (0000 e 1111) e questo complica somme e sottrazioni. Il vantaggio è che i negativi si ottengono in modo semplicissimo, invertendo i bit.

Dal complemento a uno al decimale (8 bit):

• MSB = 0: numero positivo, normale conversione binario → decimale;
• MSB = 1: numero negativo. Inverti tutti i bit e converti: ottieni il modulo. (Oppure con la formula: |N| = 2⁸ − 1 − valore della parola.)

Complemento a due¶

È il metodo più diffuso nei calcolatori per i numeri interi con segno. Per codificare X su l bit:

• se X ≥ 0 lo scrivi in binario puro (il primo bit sarà 0);
• se X < 0 scrivi |X| in binario puro su l bit, inverti tutti i bit e somma 1. In formula: Y = 2ˡ − |X|.

Intervallo: [−2ˡ⁻¹, 2ˡ⁻¹ − 1]. Con l = 8: da −128 a +127. L'intervallo non è simmetrico: c'è un negativo in più.

I vantaggi del complemento a due

• Una sola rappresentazione dello zero: tutti i bit a 0. Nessuna parola sprecata.
• Il MSB indica il segno.
• Somma e sottrazione usano lo stesso circuito e non devono controllare i segni (lo vedi più sotto).

Dal complemento a due al decimale (8 bit). Se il MSB è 0 è una normale conversione. Se il MSB è 1 hai due metodi:

• Metodo 1: il MSB ha peso negativo, −2⁷ = −128. Gli altri bit hanno il peso solito. Valore = −128 + c₆·2⁶ + … + c₀·2⁰.
• Metodo 2: inverti tutti i bit, converti e somma 1: ottieni il modulo. Metti il segno meno.

Confronta questa tabella con quella del complemento a uno: la stessa parola vale un'unità in meno (−86 invece di −85).

Rappresentazione per eccesso¶

Si sceglie un numero positivo k, detto eccesso (o bias). Per codificare X si scrive X + k in binario puro su l bit. Così i numeri da −k a 2ˡ − k − 1 vengono "spostati" su 0 … 2ˡ − 1.

Il caso più usato è k = 2ˡ⁻¹ (eccesso 128 su 8 bit, eccesso 64 su 7 bit, …):

• Intervallo: [−2ˡ⁻¹, 2ˡ⁻¹ − 1], lo stesso del complemento a due. Con l = 8: da −128 a +127.
• Una sola rappresentazione dello zero: 10000000 su 8 bit.
• Su 8 bit i negativi vanno nelle parole 0 … 127, lo zero in 128, i positivi in 129 … 255.
• Trucco: la parola in eccesso 2ˡ⁻¹ è uguale a quella in complemento a due con il primo bit invertito.

Confronto delle quattro rappresentazioni (8 bit)¶

Verifica con Python (facoltativo). Scrivi un numero e il numero di bit: il programma mostra le quattro codifiche, oppure ti dice che il numero non è rappresentabile.

x = int(input('Numero intero (anche negativo): '))
l = int(input('Numero di bit: '))

# Valore (in binario puro) della parola codice in ogni rappresentazione
if x >= 0:
    sm = x
    c1 = x
    c2 = x
else:
    sm = 2 ** (l - 1) + (-x)    # bit di segno a 1 + modulo
    c1 = 2 ** l - (-x) - 1
    c2 = 2 ** l - (-x)
ecc = x + 2 ** (l - 1)

nomi = ['Segno e modulo', 'Complemento a 1', 'Complemento a 2', 'Eccesso ' + str(2 ** (l - 1))]
valori = [sm, c1, c2, ecc]
simmetrica = -(2 ** (l - 1) - 1) <= x <= 2 ** (l - 1) - 1
asimmetrica = -(2 ** (l - 1)) <= x <= 2 ** (l - 1) - 1
rappresentabile = [simmetrica, simmetrica, asimmetrica, asimmetrica]

for i in range(4):
    if rappresentabile[i]:
        n = valori[i]
        cifre = ''
        for j in range(l):          # esattamente l bit
            cifre = str(n % 2) + cifre
            n = n // 2
        print(f'{nomi[i]:17}: {cifre}')
    else:
        print(f'{nomi[i]:17}: non rappresentabile')

Prova con −9 su 8 bit, −128 su 8 bit e −33 su 6 bit.

Somme in complemento a due¶

Con il complemento a due (e con l'eccesso 2ˡ⁻¹) la sottrazione diventa una somma: X − Y = X + (−Y). Basta un unico algoritmo e un unico circuito: sommi le due parole bit per bit, come in binario puro, senza guardare i segni.

Regole:

1. Fai la somma normale dei due numeri su l bit.
2. Se esce un riporto oltre l'ultimo bit (a sinistra), ignoralo.
3. Overflow: succede solo se i due operandi hanno lo stesso segno e il risultato ha segno diverso. Se gli operandi hanno segni diversi il risultato è sempre corretto.

Errori frequenti negli esercizi¶

Esercizi¶

Esercizio 1 · Le quattro codifiche. Rappresenta −25 su 8 bit in segno e modulo, complemento a uno, complemento a due ed eccesso 128.

Esercizio 2 · Una parola, cinque significati. Che numero rappresenta la parola 11100110 su 8 bit se letta in binario puro, segno e modulo, complemento a uno, complemento a due ed eccesso 128?

Esercizio 3 · Somme in complemento a due (come allo scritto). Su 8 bit in complemento a due calcola (a) 45 + (−20) e (b) (−70) + (−60). Indica se il risultato è corretto o se c'è overflow.

Verifica¶