Aritmetica binaria

Somma

In colonna come in base 10, con le regole $0+0=0$, $0+1=1$, $1+1=0$ con riporto 1, $1+1+1 = 1$ con riporto 1.

$$\begin{array}{r} 0101\,1011 \\ +\ 0011\,1001 \\ \hline 1001\,0100 \end{array} \qquad (91 + 57 = 148)$$

Il circuito che lo fa è il sommatore a propagazione di riporto (vedi Circuiti combinatori notevoliMultiplexer, decodificatore e codificatore; semisommatore e sommatore completo; sommatore a propagazione del riporto e suo ritardo, idea dell'anticipo del riporto; sommatore-sottrattore in complemento a 2 con rilevazione dell'overflow; comparatore.Circuiti combinatori notevoli →).

Sottrazione in complemento a 2

$a - b = a + (-b)$: si calcola l'opposto di $b$ (inverti i bit, +1; vedi Rappresentazione dei numeri interi con segnoInteri con segno su n bit: modulo e segno, complemento a 1, complemento a 2 ed eccesso K; intervalli rappresentabili, calcolo dell'opposto, estensione del segno.Rappresentazione dei numeri interi con segno →) e si somma. In hardware: si invertono i bit di $b$ e si porta a 1 il riporto in ingresso del sommatore, così non serve un sottrattore.

Esempio a 8 bit, $25 - 40$:

$$25 = 0001\,1001, \quad 40 = 0010\,1000 \to -40 = 1101\,1000$$

$$0001\,1001 + 1101\,1000 = 1111\,0001 = -128+64+32+16+1 = -15 \ ✓$$

Il riporto che esce dal bit più significativo si scarta: $50 - 20$ dà $0011\,0010 + 1110\,1100 = 1\,0001\,1110$ → $0001\,1110 = 30$.

Overflow

Il risultato non sta negli $n$ bit. La regola dipende da come si interpretano i bit:

Sommando due numeri di segno diverso non c'è mai overflow in complemento a 2. Equivalente: $V =$ riporto entrante nel MSB $\oplus$ riporto uscente dal MSB.

Esempio a 8 bit: $0111\,0000 + 0101\,0000 = 1100\,0000$.

• Senza segno: $112 + 80 = 192$, nessun riporto, risultato corretto (C = 0).
• Complemento a 2: $112 + 80$ dà $-64$: due positivi, risultato negativo → overflow (V = 1).

I processori calcolano sempre entrambi i flag; è il programma a scegliere quale guardare (in ARM: condizioni diverse per confronti con e senza segno, vedi Strutture di controllo in assembly ARMSalti B e condizionati, codici di condizione con e senza segno; traduzione di if, if-else, while, for e do-while da C ad ARM; esecuzione condizionata per eliminare salti brevi; switch con tabella di salto.Strutture di controllo in assembly ARM →). I quattro flag tipici sono N (risultato negativo, cioè MSB), Z (risultato zero), C, V.

Moltiplicazione

Il prodotto di due numeri di $n$ bit occupa fino a $2n$ bit.

Senza segno, per somme e scorrimenti. Per ogni bit del moltiplicatore, se vale 1 si somma il moltiplicando opportunamente spostato:

$$\begin{array}{r} 1011 \\ \times\ 1101 \\ \hline 1011 \\ 0000\phantom{0} \\ 1011\phantom{00} \\ 1011\phantom{000} \\ \hline 1000\,1111 \end{array} \qquad (11 \cdot 13 = 143)$$

L'hardware tiene un accumulatore A e il moltiplicatore Q affiancati: a ogni passo, se $Q_0 = 1$ somma il moltiplicando ad A, poi fa scorrere a destra la coppia C, A, Q di un bit. Dopo $n$ passi il prodotto è in A:Q. Svolto passo per passo in Esercizio 2 · moltiplicazione 11 per 13 su 4 bit.

In complemento a 2: algoritmo di Booth. Si esaminano le coppie $(Q_0, Q_{-1})$ con $Q_{-1}$ inizialmente 0:

poi scorrimento aritmetico a destra di A, Q, $Q_{-1}$. Una sequenza di 1 consecutivi nel moltiplicatore costa una sottrazione all'inizio e una somma alla fine invece di una somma per bit.

Esempio $7 \cdot 3$ su 4 bit ($M = 0111$, $Q = 0011$):

Risultato $A:Q = 0001\,0101 = 21$ ✓.

Divisione

Senza segno, come in colonna: a ogni passo si prova a sottrarre il divisore dal resto parziale; se il risultato è $\ge 0$ il bit del quoziente è 1, altrimenti è 0 e si ripristina il resto. Esempio $13 : 3$: $1101 : 11$ → quoziente $100 = 4$, resto $1$.

Scorrimenti (shift)

ARM ha gli shift come modificatore del secondo operando di quasi ogni istruzione (LSL, LSR, ASR, ROR, vedi Istruzioni ARM di elaborazione datiIstruzioni aritmetiche (ADD, SUB, RSB, ADC), logiche (AND, ORR, EOR, BIC, MVN), di spostamento (MOV), moltiplicazione (MUL, MLA); secondo operando immediato o registro scalato con LSL, LSR, ASR, ROR; aggiornamento dei flag con S, CMP e TST; esempi di traduzione di espressioni C.Istruzioni ARM di elaborazione dati →).

Errori tipici

• Considerare overflow il riporto uscente in una somma in complemento a 2: conta solo il cambio di segno.
• Usare lo shift logico a destra per dividere un negativo: $-16 = 1111\,0000$ diventa $0111\,1000 = 120$.
• Dimenticare che il prodotto richiede $2n$ bit.