Aritmetica dei calcolatori: sommatori, riporto anticipato e moltiplicazione
Sommatore completo con dimostrazione, propagazione del riporto, riporto anticipato, sottrazione in complemento a due, traboccamento e flag, moltiplicatori.
L’unità aritmetico-logica fa i conti con porte logiche. In Fondamenti di informatica abbiamo visto come si rappresentano i numeri in binario e in complemento a due; qui vediamo come l’hardware li somma, li sottrae, rileva gli errori e li moltiplica, e perché il modo di propagare il riporto decide la velocità di un processore.
Il sommatore completo
Sommare due numeri binari colonna per colonna richiede, per ogni bit, di sommare tre cifre: i due bit 
e 
e il riporto 
dalla colonna precedente. Il risultato è un bit di somma 
e un riporto 
per la colonna successiva.
Teorema.
![\[ S = A \oplus B \oplus C_{in},\qquad C_{out} = AB + C_{in}(A \oplus B) \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-c502b6f8f1a0d4e1f911e4bc5e463b1b_l3.png "Rendered by QuickLaTeX.com")
Dimostrazione. Si verifica sulla tabella di verità delle otto combinazioni. vale 1 quando il numero di ingressi a 1 è dispari (1 o 3), che è la definizione dell’OR esclusivo di tre bit. vale 1 quando almeno due ingressi sono a 1: o e lo sono entrambi (
), o uno solo dei due lo è (
) e anche . I due casi sono disgiunti e coprono tutte le possibilità. ∎
La propagazione del riporto
Mettendo in fila 
sommatori completi, con il riporto d’uscita di ciascuno collegato all’ingresso del successivo, si ottiene il sommatore a propagazione del riporto (ripple carry). È semplice, ma lento: il bit più significativo non è valido finché il riporto non ha attraversato tutta la catena. Se ogni stadio introduce un ritardo di due porte, un sommatore a 64 bit ne accumula 128, troppo per un processore a qualche gigahertz.
Il riporto anticipato
Per ogni colonna si definiscono due segnali che dipendono solo da 
e 
:
![\[ g_i = A_iB_i\ \ \text{(genera)},\qquad p_i = A_i \oplus B_i\ \ \text{(propaga)} \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-55e4be3f91252a4093bb83bdabc2554e_l3.png "Rendered by QuickLaTeX.com")
La colonna genera un riporto da sola se entrambi i bit sono 1; propaga quello in arrivo se esattamente uno è 1. Quindi 
, e sostituendo:
![\[ c_2 = g_1 + p_1g_0 + p_1p_0c_0,\qquad c_3 = g_2 + p_2g_1 + p_2p_1g_0 + p_2p_1p_0c_0 \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-2a465c06c79c30c86c75b2b733778722_l3.png "Rendered by QuickLaTeX.com")
Ogni riporto si calcola direttamente dagli ingressi, con due livelli di porte, senza aspettare i precedenti. Le porte diventano molto larghe al crescere di , quindi si lavora a gruppi di 4 bit e si ripete l’idea gerarchicamente: il ritardo cresce come 
invece che come . I sommatori dei processori moderni sono varianti di questa idea (sommatori a prefisso, come Kogge-Stone).
La sottrazione e il traboccamento
In complemento a due, 
si ottiene invertendo tutti i bit e sommando 1. Quindi
![\[ A - B = A + \overline{B} + 1 \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-f003a7f52b4fb2597d548ea787c8d30e_l3.png "Rendered by QuickLaTeX.com")
e lo stesso sommatore fa anche le sottrazioni: basta mettere delle porte XOR sugli ingressi (per invertirli quando serve) e portare a 1 il riporto iniziale 
. È uno dei motivi per cui il complemento a due ha soppiantato tutte le altre rappresentazioni dei numeri negativi.
Il traboccamento (overflow). Sommando due numeri dello stesso segno il risultato può uscire dall’intervallo rappresentabile: con 8 bit, 
supera 127 e appare come −56. Si riconosce perché il segno del risultato è diverso da quello dei due addendi; in hardware, equivalentemente, il riporto che entra nel bit più significativo è diverso da quello che ne esce: 
.
L’ALU segnala l’esito delle operazioni con alcuni bit di stato, i flag: Z (risultato zero), N (negativo), C (riporto, utile per i numeri senza segno), V (traboccamento, per quelli con segno). I salti condizionati delle architetture che li usano si basano su questi bit.
La moltiplicazione
La moltiplicazione binaria è più semplice di quella decimale: ogni prodotto parziale è il moltiplicando oppure zero, a seconda del bit del moltiplicatore, spostato della posizione corrispondente. Si sommano poi gli prodotti parziali.
- Il metodo più lento, sposta e somma, usa un solo sommatore per cicli.
- I moltiplicatori ad albero sommano tutti i prodotti parziali insieme con sommatori disposti ad albero (alberi di Wallace), e moltiplicano due numeri a 64 bit in pochi cicli di clock.
La divisione è più difficile e si fa con algoritmi iterativi, che producono una o più cifre del quoziente per ciclo: per questo, nei programmi in cui conta la velocità, i compilatori sostituiscono le divisioni per costanti con moltiplicazioni e spostamenti. I numeri in virgola mobile (standard IEEE 754, lezione di Calcolo numerico) hanno un’unità dedicata, che allinea gli esponenti, opera sulle mantisse e normalizza il risultato.
