Assembly Base con MASM

Capitolo 6: Reti combinatorie per funzioni matematiche

Nel Capitolo 4 abbiamo visto che, dal punto di vista degli esseri umani, elaborare delle informazioni codificate sotto forma di numeri binari significa eseguire su questi numeri una serie di operazioni matematiche che devono produrre dei risultati sempre in formato binario; in base allora a quanto è stato esposto nel Capitolo 5, possiamo dire che dal punto di vista del computer, elaborare informazioni codificate sotto forma di segnali logici significa eseguire su questi segnali una serie di operazioni che devono produrre dei risultati sempre sotto forma di segnali logici. In questo capitolo vengono analizzate una serie di R.C. che permettono alla CPU di eseguire elaborazioni sui segnali logici; per noi esseri umani queste elaborazioni effettuate dal computer assumono proprio l'aspetto di operazioni matematiche eseguite sui numeri binari.

6.1 Circuiti Multiplexer e Demultiplexer

Prima di illustrare le R.C. per le funzioni matematiche, analizziamo due circuiti che in elettronica digitale trovano un impiego veramente massiccio; si tratta dei circuiti chiamati Multiplexer e Demultiplexer.
Il Multiplexer o MUX rappresenta un vero e proprio commutatore elettronico; questo circuito, infatti, riceve in ingresso n segnali logici ed è in grado di selezionare in uscita uno solo di essi.
Osserviamo subito che, per selezionare una tra n possibili linee in ingresso, abbiamo bisogno di m linee di selezione con: 
2m = n
Da questa relazione si ricava: 
log2 2m = log2 n
e quindi: 
m = log2 n
Nel caso, ad esempio, di un MUX a n=4 ingressi, abbiamo bisogno di m=2 linee di selezione; infatti, con 2 bit possiamo gestire 22=4 configurazioni diverse (4 numeri binari differenti).
Se colleghiamo ora i 4 ingressi del MUX a 4 porte AND, grazie alle 2 linee di selezione possiamo abilitare solo una delle porte AND; di conseguenza, la porta AND abilitata trasferisce in uscita l'ingresso ad essa collegato. Le 4 uscite delle porte AND vengono collegate ad una porta OR a 4 ingressi per ottenere il segnale che abbiamo selezionato; la Figura 6.1 illustra la struttura della R.C. che implementa un MUX a 4 ingressi e una uscita (chiamato anche MUX da 4 a 1). L'ingresso E (Enable) permette di attivare o disattivare l'intero MUX; portando l'ingresso E a livello logico 1, in uscita dal NOT otteniamo un livello logico 0 che disattiva tutte le 4 porte AND. In questo modo, l'uscita Y del MUX si trova sempre a livello logico basso indipendentemente dai 4 segnali in ingresso; se, invece, E=0, il MUX viene attivato, ed è in grado di selezionare uno solo tra i 4 ingressi a0, a1, a2, a3.
Le due linee S0 e S1 rappresentano gli ingressi di selezione; ponendo ora E=0 (MUX attivo), si può constatare dalla Figura 6.1 che: Il compito opposto rispetto al caso del MUX viene svolto da un altro circuito chiamato Demultiplexer o DMUX; il DMUX riceve in ingresso un unico segnale logico, ed è in grado di trasferirlo su una sola tra le n linee di uscita. Come al solito, per la selezione delle n linee di uscita abbiamo bisogno di: 
m = log2 n
linee di selezione.

Attraverso queste m linee di selezione possiamo attivare solo una delle n linee di uscita, disattivando tutte le altre n-1; si presenta allora il problema di stabilire il livello logico da assegnare alle n-1 linee di uscita disabilitate. Chiaramente, se vogliamo trasferire sull'uscita abilitata un segnale a livello logico 1, dobbiamo portare a livello logico 0 tutte le n-1 uscite disabilitate; viceversa, se vogliamo trasferire sull'uscita abilitata un segnale a livello logico 0, dobbiamo portare a livello logico 1 tutte le n-1 uscite disabilitate.
Per ottenere queste caratteristiche, gli m ingressi di selezione agiscono su n porte NAND ciascuna delle quali fornisce una delle n uscite; la Figura 6.2 illustra la struttura della R.C. che implementa un DMUX a 1 ingresso e 4 uscite (chiamato anche DMUX da 1 a 4). In questo circuito, S0 e S1 sono gli ingressi di selezione, D è l'unico ingresso per i dati, mentre E è come al solito l'ingresso di abilitazione; le 4 uscite del DMUX sono Y0, Y1, Y2 e Y3.
Il DMUX di Figura 6.2 permette di trasferire su una delle 4 uscite un segnale a livello logico 0; di conseguenza, le 3 uscite disabilitate si portano a livello logico 1. Per ottenere questo trasferimento bisogna porre E=0 e D=1; in queste condizioni possiamo constatare che:

6.2 Comparazione tra numeri binari

Tra le istruzioni più importanti messe a disposizione dai linguaggi di programmazione di alto livello, troviamo sicuramente quelle denominate istruzioni per il controllo del flusso, così chiamate perché permettono ad un programma di prendere delle decisioni in base al risultato di una operazione appena eseguita; si possono citare, ad esempio, istruzioni come IF, THEN, ELSE, DO WHILE, REPEAT UNTIL, etc. Dal punto di vista della CPU tutte queste istruzioni si traducono in una serie di confronti tra numeri binari; proprio per questo motivo, tutte le CPU sono dotate di apposite R.C. che permettono di effettuare comparazioni tra numeri binari.
Supponiamo, ad esempio, di avere due numeri binari A e B a 8 bit che rappresentano i codici ASCII di due lettere dell'alfabeto; consideriamo ora un programma che elabora questi due numeri attraverso le pseudo-istruzioni mostrate in Figura 6.3: Come si può notare, questa porzione del programma effettua una scelta basata sul risultato del confronto tra A e B; se A è uguale a B, l'esecuzione salta al blocco di istruzioni denominato Procedura 1, mentre in caso contrario (A diverso da B), l'esecuzione salta al blocco di istruzioni denominato Procedura 2.
Per comparare A con B, abbiamo bisogno di una funzione booleana che riceve in input i due numeri binari da confrontare e restituisce in output un risultato espresso sempre in forma binaria; possiamo usare, ad esempio, il valore 0 per indicare che i due numeri sono diversi tra loro e il valore 1 per indicare che i due numeri sono uguali. Una volta scritta la funzione booleana, si può passare alla sua realizzazione pratica tramite una R.C..
Nel precedente capitolo, abbiamo visto che una porta EX-OR a due ingressi restituisce 0 se i due livelli logici in ingresso sono uguali tra loro e restituisce, invece, 1 in caso contrario; analogamente, una porta EX-NOR a due ingressi restituisce 1 se i due livelli logici in ingresso sono uguali tra loro e restituisce, invece, 0 in caso contrario. Le porte EX-OR oppure le porte EX-NOR appaiono quindi particolarmente adatte a risolvere il nostro problema; per capire come si debba effettuare il confronto tra due numeri binari, bisogna fare innanzi tutto alcune considerazioni importanti: In base a queste considerazioni, vediamo subito come si deve procedere utilizzando, ad esempio, le porte EX-NOR che restituiscono 1 se i due livelli logici in ingresso sono uguali tra loro e 0 se sono diversi; utilizziamo una porta EX-NOR per ogni coppia di bit (corrispondenti) da confrontare. La prima porta confronta il bit in posizione 0 del primo numero con il bit in posizione 0 del secondo numero; la seconda porta confronta il bit in posizione 1 del primo numero con il bit in posizione 1 del secondo numero e così via. Ogni porta EX-NOR produce un risultato che vale 1 se i due bit sono uguali tra loro e vale, invece, 0 in caso contrario; i due numeri binari sono uguali tra loro solo quando tutte le porte EX-NOR producono 1 come risultato, cioè quando tutti i bit corrispondenti dei due numeri sono uguali tra loro. Se almeno una porta EX-NOR produce 0 come risultato, i due numeri binari sono diversi tra loro.
Per sapere se tutte le porte EX-NOR hanno prodotto 1, basta confrontare con un AND tutte le loro uscite; l'AND ci restituisce 1 solo se tutti i suoi ingressi valgono 1 e ci restituisce 0 se anche un solo ingresso vale 0. Facendo riferimento per semplicità a numeri a 4 bit (1 nibble), la nostra funzione booleana sarà allora. 
Y = (A0 EX-NOR B0) AND (A1 EX-NOR B1) AND (A2 EX-NOR B2) AND (A3 EX-NOR B3)
dove A0, A1, A2, A3 rappresentano i 4 bit del primo numero e B0, B1, B2, B3 rappresentano i 4 bit del secondo numero.
La Figura 6.4 mostra la R.C che implementa in pratica questa funzione. Si capisce subito che il numero di porte EX-NOR da utilizzare è pari al numero di coppie di bit da confrontare; per confrontare, ad esempio, due numeri a 8 bit (8 coppie di bit) occorreranno 8 porte EX-NOR. Le uscite di tutte le porte EX-NOR impiegate vanno collegate agli ingressi di una porta AND che restituisce 1 solo quando tutti i suoi ingressi valgono 1; ma questo accade solo quando tutti i confronti hanno prodotto 1 come risultato (bit corrispondenti uguali tra loro). In definitiva, la R.C. di Figura 6.4 fornisce in output il livello logico 1 se i due numeri da confrontare sono uguali tra loro e il livello logico 0 in caso contrario.
Come si può notare, ogni porta EX-NOR confronta un bit del primo numero con il bit che nel secondo numero occupa la stessa posizione; questo tipo di confronto viene definito bit a bit (in inglese bitwise).
Tutti i concetti appena esposti, si estendono immediatamente al confronto tra numeri binari di qualunque dimensione; se vogliamo confrontare numeri binari a 16 bit, ci occorreranno 16 porte EX-NOR e una porta AND a 16 ingressi; se vogliamo confrontare numeri binari a 32 bit ci occorreranno 32 porte EX-NOR e una porta AND a 32 ingressi e così via. Queste considerazioni comunque sono solamente teoriche perché in realtà, nella realizzazione pratica dei comparatori (e di altre R.C.) si segue un'altra strada; può capitare, infatti, che in commercio si trovino solo i comparatori a 4 bit illustrati in Figura 6.4. Come si può facilmente intuire, in questo caso basta utilizzare uno o più comparatori a 4 bit collegati in parallelo. Se, ad esempio, vogliamo confrontare numeri a 16 bit, utilizzeremo 4 comparatori a 4 bit in parallelo (4x4=16); se, invece, vogliamo confrontare numeri a 32 bit, utilizzeremo 8 comparatori a 4 bit in parallelo (8x4=32) e così via.
Ogni comparatore ha una sola uscita e tutte queste uscite vanno collegate agli ingressi di una porta AND che produrrà il risultato finale. Si ricorda che le porte AND con più di due ingressi, producono in uscita un livello logico alto solo se tutti i livelli logici in ingresso sono alti; in caso contrario verrà prodotto un livello logico basso.

Un caso che si presenta molto più di frequente consiste nel voler conoscere la relazione esatta che esiste tra due numeri binari; dati cioè i due numeri binari A e B, vogliamo sapere se A è minore di B o se A è uguale a B o se A è maggiore di B. In Figura 6.5 vediamo un esempio relativo sempre al confronto tra nibble. Prima di tutto osserviamo in Figura 6.5a la struttura elementare del circuito che confronta il bit Ai del numero A con il corrispondente bit Bi del numero B; come si può facilmente constatare, in base al risultato del confronto solo una delle tre uscite sarà a livello logico alto, mentre le altre due saranno a livello logico basso. In particolare, notiamo che la prima uscita (quella più in alto) presenta un livello logico alto solo se Ai è maggiore di Bi (cioè Ai=1 e Bi=0); la seconda uscita presenta un livello logico alto solo se Ai è uguale a Bi (cioè Ai=0 e Bi=0, oppure Ai=1 e Bi=1). La terza uscita infine presenta un livello logico alto solo se Ai è minore di Bi (cioè Ai=0 e Bi=1).
Partendo dal circuito elementare di Figura 6.5a si può facilmente ottenere un comparatore completo a 4 bit che ci permette di sapere quale relazione esiste tra il nibble A e il nibble B; il blocco che rappresenta simbolicamente questo comparatore, viene mostrato in Figura 6.5b. I comparatori a 4 bit che si trovano in commercio, sono dotati, come si può notare, di 3 uscite indicate con Y1, Y2 e Y3; l'uscita Y1 è associata alla condizione A maggiore di B, l'uscita Y2 è associata alla condizione A uguale a B e l'uscita Y3 è associata alla condizione A minore di B.
Possiamo dire quindi che se A è maggiore di B si ottiene: 
Y1 = 1, Y2 = 0, Y3 = 0
Se A è uguale a B si ottiene: 
Y1 = 0, Y2 = 1, Y3 = 0
Se A è minore di B si ottiene: 
Y1 = 0, Y2 = 0, Y3 = 1
La tecnica che si utilizza per il confronto è molto semplice e si basa su una proprietà fondamentale dei sistemi di numerazione posizionali; come sappiamo, infatti, i numeri rappresentati con questo sistema sono formati da una sequenza di cifre il cui peso dipende dalla posizione della cifra stessa nel numero. La cifra di peso maggiore è quella più a sinistra e quindi, per confrontare due numeri nel modo più rapido possibile, è necessario partire dal confronto tra le cifre più significative dei due numeri stessi (MSB per i numeri binari); ancora una volta bisogna ricordare che l'operazione di confronto ha senso solo se i due numeri hanno lo stesso numero di cifre.
Tornando allora al caso del comparatore a 4 bit di Figura 6.5b, vediamo come si svolge il confronto tra i due nibble A e B: Nella Figura 6.5b si nota anche la presenza di tre connessioni I1, I2 e I3; queste connessioni servono per il collegamento in parallelo di due o più comparatori quando si ha la necessità di confrontare tra loro numeri con più di 4 bit. La Figura 6.6 illustra un esempio che si riferisce al confronto tra numeri binari a 8 bit; vengono utilizzati a tale proposito due comparatori a 4 bit e cioè, C1 che confronta il nibble basso e C2 che confronta il nibble alto. Il confronto parte come al solito dai bit più significativi che in questo caso si trovano in posizione 7; indichiamo con Aa e Ba i nibble alti, e con Ab e Bb i nibble bassi dei due numeri A e B. Se il comparatore C2 confrontando i nibble alti verifica che Aa è maggiore di Ba o che Aa è minore di Ba, non ha bisogno di consultare C1; in questo caso C2 ignora gli ingressi I1, I2 e I3 e termina il confronto fornendo i risultati sulle sue uscite Y1, Y2 e Y3.
Se, invece, il comparatore C2 verifica che Aa è uguale a Ba, allora legge i suoi ingressi I1, I2, I3 che gli forniscono il risultato del confronto tra i nibble bassi effettuato da C1; come si può notare dalla Figura 6.6, l'ingresso I1 è associato a Ab maggiore di Bb, l'ingresso I2 è associato a Ab uguale a Bb e l'ingresso I3 è associato a Ab minore di Bb. In base ai livelli logici assunti da I1, I2 e I3, il comparatore C2 fornisce il risultato finale sempre attraverso le sue uscite Y1, Y2, Y3; anche in questo caso si nota che la condizione A uguale a B può essere verificata con certezza solo dopo l'ultimo confronto che coinvolge i bit A0 e B0 (cioè gli LSB).
Naturalmente, nell'esempio di Figura 6.6, gli ingressi I1, I2 e I3 del comparatore C1 non vengono utilizzati; appare anche evidente il fatto che, attraverso il collegamento in parallelo di più comparatori a 4 bit, si possono confrontare tra loro numeri binari di qualunque dimensione.
Un computer con architettura a 8 bit sarà dotato di comparatori a 8 bit; un computer con architettura a 16 bit sarà dotato di comparatori a 16 bit e così via. Quindi, su un computer con architettura a 8 bit, non sarà possibile confrontare via hardware numeri a 16 bit; se si vuole effettuare ugualmente il confronto tra numeri a 16 bit si dovrà procedere via software scrivendo un apposito programma che naturalmente non potrà raggiungere le prestazioni del confronto via hardware. Molti linguaggi di programmazione di alto livello mettono a disposizione delle funzioni (sottoprogrammi) che permettono di effettuare via software diverse operazioni su numeri formati da un numero di bit maggiore di quello dell'architettura del computer che si sta utilizzando.

6.3 Addizione tra numeri binari

Come abbiamo visto nei precedenti capitoli, per sommare due numeri espressi nel sistema posizionale arabo bisogna incolonnarli in modo da far corrispondere sulla stessa colonna le cifre aventi peso identico nei due numeri stessi; sappiamo anche che la somma viene eseguita a partire dalla colonna più a destra che contiene le cifre meno significative dei due addendi. Questa prima somma non deve tenere conto di alcun riporto precedente; nel sommare, invece, le colonne successive alla prima, si dovrà tenere conto dell'eventuale riporto proveniente dalla somma della colonna precedente.
Bisogna ricordare inoltre che in binario, nel sommare la prima colonna, la situazione più critica che si può presentare è: 
1 + 1
che dà come risultato 0 con riporto di 1; nel sommare le colonne successive alla prima, in presenza di un riporto pari a 1, la situazione più critica che si può presentare è: 
1 + 1 + 1
che dà come risultato 1 con riporto di 1. In base 2 quindi e in qualsiasi altra base, il riporto massimo non può superare 1.
Da quanto abbiamo appena detto, si può capire che la R.C. che dovrà eseguire la somma della prima colonna, sarà molto più semplice della R.C. che somma le colonne successive tenendo conto di eventuali riporti; per questo motivo, i circuiti che sommano le coppie di bit si suddividono in due tipi chiamati: Half Adder e Full Adder.

La Figura 6.7a illustra la tabella della verità di un Half Adder (H.A.) o semisommatore binario; la Figura 6.7b illustra la R.C. che permette di implementare la somma di due bit. L'H.A. esegue la somma relativa ai due bit che nell'addizione occupano la prima colonna (LSB) e produce quindi un valore a 2 bit compreso tra 00b e 10b; nella tabella della verità indichiamo con S il bit più a destra e con C il bit più a sinistra della somma appena effettuata dall'H.A.. Il bit S rappresenta una delle cifre del risultato finale (si tratta per la precisione del LSB); il bit C (Carry) rappresenta il riporto (0 o 1) di cui si dovrà tenere conto nella somma relativa alla colonna successiva dell'addizione.
Osservando la tabella della verità dell'H.A. in Figura 6.7a, si vede subito che il contenuto della colonna S coincide esattamente con i livelli logici in uscita da una porta EX-OR in seguito alla operazione: 
A EX-OR B
Notiamo poi che il contenuto della colonna C (riporto destinato alla colonna successiva), coincide esattamente con i livelli logici forniti in uscita da una porta AND in seguito alla operazione: 
A AND B
In base a questi risultati, siamo in grado di definire le due funzioni che caratterizzano l'H.A. e che sono: 
S = A EX-OR B
e 
C = A AND B
La Figura 6.7b illustra la R.C. che soddisfa la tabella della verità di Figura 6.7a; possiamo dire quindi che l'H.A. ha bisogno di due ingressi che rappresentano i due bit da sommare e di due uscite che rappresentano una delle cifre del risultato finale e il riporto destinato alla colonna successiva dell'addizione.

La Figura 6.8a illustra la tabella della verità di un Full Adder (F.A.) o sommatore binario; la Figura 6.8b illustra la R.C. che permette di implementare la somma di due bit più il riporto. Il F.A. esegue la somma relativa ai due bit che nell'addizione occupano una tra le colonne successive alla prima e deve tenere conto quindi anche del bit di riporto proveniente dalla colonna precedente; questa volta la somma produce un valore a 2 bit che sarà compreso tra 00b e 11b. Nella tabella della verità indichiamo con S il bit più a destra e con C il bit più a sinistra della somma appena effettuata dal F.A.; il bit S rappresenta una delle cifre del risultato finale, mentre il bit C (Carry) rappresenta il riporto (0 o 1) destinato alla colonna successiva dell'addizione.
Supponiamo di dover sommare i bit della seconda colonna di una addizione e indichiamo con C0 il riporto precedente, con A1 e B1 i due bit da sommare, con S1 la cifra meno significativa della somma A1+B1 e con C1 il riporto di A1+B1 destinato alla colonna successiva; la tabella della verità di Figura 6.8a è formata da 8 righe in quanto, per ciascuno dei 4 possibili risultati della somma A1+B1, dobbiamo considerare i due casi C0=0 e C0=1 per un totale di 4x2=8 casi distinti.
Le funzioni booleane che realizzano il F.A. possono essere ottenute facilmente ricordando la tecnica che si utilizza per eseguire le addizioni con carta e penna; in relazione alle colonne successive alla prima, sappiamo che prima di tutto si sommano le due cifre in colonna, dopo di che si aggiunge al risultato ottenuto il riporto precedente.
Queste due addizioni consecutive suggeriscono l'idea di utilizzare per il F.A., due H.A. in serie come si vede in Figura 6.8b; il primo H.A. somma i due bit in colonna (A1+B1) producendo in uscita i risultati parziali S' e C', mentre il secondo H.A. somma S' con il riporto precedente C0 producendo a sua volta i risultati parziali S'' e C''. Alla fine S'' rappresenta la cifra S1 del risultato finale, mentre i due riporti C' e C'' devono fornirci il riporto C1 destinato alla colonna successiva.
Come si verifica facilmente dal circuito di Figura 6.8b, i due riporti C' e C'' non possono mai essere entrambi a livello logico 1 (la somma massima, infatti, è 11b) e quindi basta applicarli ai due ingressi di una porta OR per ottenere il riporto C1 destinato alla colonna successiva.
Possiamo dire quindi che il F.A. ha bisogno di tre ingressi che rappresentano i due bit da sommare e il riporto proveniente dalla colonna precedente; le due uscite del F.A. forniscono, invece, una delle cifre del risultato finale e il riporto destinato alla colonna successiva.

Una volta definiti l'H.A. e il F.A., possiamo realizzare circuiti per sommare numeri binari di qualsiasi dimensione; lo schema a blocchi di Figura 6.9 mostra una R.C. per la somma tra numeri binari a 4 bit. La R.C. di Figura 6.9 utilizza un H.A. e tre F.A.; l'H.A. somma i bit della prima colonna (LSB), mentre i tre F.A. sommano i bit delle tre colonne successive. Il riporto finale C3 contiene il valore (0 o 1) che verrà assegnato al Carry Flag; come già sappiamo, grazie a CF possiamo sommare via software numeri binari di qualsiasi ampiezza in bit.
Anche nel caso dell'addizione (e di tutte le altre operazioni), bisogna ricordare che un computer con architettura, ad esempio, a 16 bit, sarà dotato di circuiti in grado di sommare via hardware numeri a 16 bit; se vogliamo sommare tra loro numeri a 32 bit, dobbiamo procedere via software suddividendo i bit degli addendi in gruppi da 16.
Nei precedenti capitoli abbiamo anche appurato che grazie all'aritmetica modulare, una R.C. come quella di Figura 6.9 può sommare indifferentemente numeri con o senza segno; alla fine dell'addizione, se stiamo operando sui numeri senza segno dobbiamo consultare CF per conoscere il riporto finale, mentre se stiamo operando sui numeri con segno dobbiamo consultare OF e SF per sapere se il risultato è valido e per individuarne il segno. Come si può facilmente verificare attraverso la Figura 6.9, si ha: 
CF = C3, SF = S3, OF = (A3 EX-NOR B3) AND (A3 EX-OR B3 EX-OR S3)

6.4 Sottrazione tra numeri binari

Per la sottrazione valgono considerazioni analoghe a quelle svolte per l'addizione; sottraendo i bit della colonna più a destra non si deve tenere conto di eventuali prestiti chiesti dalle colonne precedenti; sottraendo, invece, i bit delle colonne successive alla prima, bisogna tenere conto degli eventuali prestiti chiesti dalle colonne precedenti. Nel primo caso, la situazione più critica che può presentarsi è: 
0 - 1
che dà come risultato 1 con prestito di 1 dalle colonne successive; nel secondo caso, in presenza di un prestito pari a 1 richiesto dalla colonna precedente, la situazione più critica che può presentarsi è: 
0 - 1 - 1
che dà come risultato 0 con prestito di 1 dalle colonne successive.
In qualsiasi base numerica quindi, il prestito massimo non può superare 1; per gestire questi due casi possibili vengono impiegati due circuiti chiamati Half Subtractor e Full Subtractor.

La Figura 6.10a illustra la tabella della verità di un Half Subtractor (H.S.) o semisottrattore binario; la Figura 6.10b illustra la R.C. che permette di implementare la sottrazione tra due bit. L'H.S. calcola la differenza tra i due bit che nella sottrazione occupano la prima colonna (LSB) e produce quindi come risultato un valore a 1 bit compreso tra 0b e 1b; nella tabella della verità indichiamo questo bit con D. Il bit D rappresenta una delle cifre del risultato finale (in questo caso si tratta del LSB); indichiamo poi con P il bit che rappresenta il prestito (0 o 1) richiesto alle colonne successive.
Osservando la tabella della verità dell'H.S. in Figura 6.10a, si vede subito che il contenuto della colonna D coincide esattamente con i livelli logici in uscita da una porta EX-OR in seguito alla operazione: 
A EX-OR B
Notiamo anche che il contenuto della colonna P (prestito richiesto alle colonne successive), coincide esattamente con i livelli logici forniti in uscita da una porta AND in seguito alla operazione: 
NOT(A) AND B
In base a questi risultati, siamo in grado di definire le due funzioni che caratterizzano l'H.S. e che sono: 
D = A EX-OR B
e 
P = NOT(A) AND B
La Figura 6.10b illustra la R.C. che soddisfa la tabella della verità di Figura 6.10a; possiamo dire quindi che l'H.S. ha bisogno di due ingressi che rappresentano i due bit da sottrarre e di due uscite che rappresentano una delle cifre del risultato finale (in questo caso si tratta dell'LSB) e il prestito richiesto alle colonne successive della sottrazione.

La Figura 6.11a illustra la tabella della verità di un Full Subtractor (F.S.) o sottrattore binario; la Figura 6.11b illustra la R.C. che permette di implementare la differenza tra due bit tenendo conto della presenza di un eventuale prestito. Il F.S. calcola la differenza tra i due bit che nella sottrazione occupano una tra le colonne successive alla prima e produce quindi come risultato un valore a 1 bit compreso tra 0b e 1b; nella tabella della verità indichiamo questo bit con D. Il bit D rappresenta una delle cifre del risultato finale; indichiamo poi con P il bit che rappresenta il prestito (0 o 1) richiesto alle colonne successive.
Supponiamo di dover calcolare la differenza tra i bit della seconda colonna di una sottrazione e indichiamo con P0 il prestito precedente, con A1 e B1 i due bit da sottrarre, con D1 la cifra meno significativa della sottrazione A1-B1 e con P1 il prestito richiesto da A1-B1 alle colonne successive; la tabella della verità di Figura 6.11a è formata da 8 righe in quanto per ciascuno dei 4 possibili risultati della differenza A1-B1, dobbiamo considerare i due casi P0=0 e P0=1 per un totale di 4x2=8 casi distinti.
Anche in questo caso le funzioni booleane che realizzano il F.S. possono essere ottenute facilmente ricordando la tecnica che si utilizza per eseguire le sottrazioni con carta e penna; in relazione alle colonne successive alla prima, possiamo iniziare dalla sottrazione tra le due cifre in colonna, dopo di che sottraiamo al risultato ottenuto il prestito precedente.
Queste due sottrazioni consecutive suggeriscono l'idea di utilizzare per il F.S., due H.S. in serie come si vede in Figura 6.11b; il primo H.S. sottrae i due bit in colonna (A1-B1) producendo in uscita i risultati parziali D' e P', mentre il secondo H.S. sottrae D' con il prestito precedente P0 producendo a sua volta i risultati parziali D'' e P''. Alla fine D'' rappresenta la cifra D1 del risultato finale, mentre i due prestiti P' e P'' devono fornirci il riporto P1 richiesto alle colonne successive.
Come si verifica facilmente dal circuito di Figura 6.11b, i due prestiti P' e P'' non possono mai essere entrambi a livello logico 1 (il prestito massimo, infatti, è 1) e quindi basta applicarli ai due ingressi di una porta OR per ottenere il prestito P1 richiesto alle colonne successive.
Possiamo dire quindi che il F.S. ha bisogno di tre ingressi che rappresentano i due bit da sottrarre e il prestito richiesto dalla colonna precedente; le due uscite del F.S. forniscono, invece, una delle cifre del risultato finale e il prestito richiesto alle colonne successive.

Una volta definiti l'H.S. e il F.S., possiamo realizzare circuiti per sottrarre numeri binari di qualsiasi dimensione; lo schema a blocchi di Figura 6.12 mostra una R.C. per la sottrazione tra numeri binari a 4 bit. La R.C. di Figura 6.12 utilizza un H.S. e tre F.S.; l'H.S. sottrae i bit della prima colonna (LSB), mentre i tre F.S. sottraggono i bit delle tre colonne successive. Il prestito finale P3 contiene il valore (0 o 1) che verrà assegnato al Carry Flag; come già sappiamo, grazie a CF possiamo sottrarre via software numeri binari di qualsiasi ampiezza in bit.
Un computer con architettura, ad esempio, a 16 bit, sarà dotato di circuiti in grado di sottrarre via hardware numeri a 16 bit; se vogliamo sottrarre tra loro numeri a 32 bit, dobbiamo procedere via software suddividendo i bit del minuendo e del sottraendo in gruppi da 16.
Nei precedenti capitoli abbiamo anche appurato che grazie all'aritmetica modulare, una R.C. come quella di Figura 6.12 può sottrarre indifferentemente numeri con o senza segno; alla fine della sottrazione, se stiamo operando sui numeri senza segno dobbiamo consultare CF per conoscere il prestito finale, mentre se stiamo operando sui numeri con segno dobbiamo consultare OF e SF per sapere se il risultato è valido e per individuarne il segno. Come si può facilmente verificare attraverso la Figura 6.12, si ha: 
CF = P3, SF = D3, OF = (A3 EX-NOR B3) AND (A3 EX-OR B3 EX-OR D3)

6.5 Circuiti complementatori

Nella precedente sezione sono stati descritti i circuiti che eseguono la sottrazione tra numeri binari; nella realizzazione pratica di questi circuiti può essere seguita anche un'altra strada. Osserviamo, infatti, che dati i due numeri binari n1 e n2, possiamo scrivere: 
n1 - n2 = n1 + (-n2)
In sostanza, la differenza tra n1 e n2 è pari alla somma tra n1 e l'opposto di n2; come già sappiamo, l'opposto di un numero binario si ottiene effettuando il complemento a 2 del numero stesso. Il complemento a 2 (NEG) di un numero binario n si ottiene invertendo tutti i suoi bit (NOT) e sommando 1 al risultato ottenuto; possiamo scrivere quindi: 
NEG(n) = NOT(n) + 1
Per realizzare nel modo più semplice il complemento a 1 di un numero, possiamo utilizzare delle semplici porte NOT che come sappiamo producono in uscita un livello logico che è l'opposto di quello in ingresso; se entra un segnale alto, esce un segnale basso, mentre se entra un segnale basso, esce un segnale alto. Quindi se vogliamo complementare, ad esempio, numeri binari a 16 bit, possiamo utilizzare 16 porte NOT; ciascuna di queste porte inverte uno dei bit del numero da complementare e alla fine otteniamo in uscita il numero in ingresso con tutti i bit invertiti.
Il circuito complementatore appena descritto è molto semplice; nella pratica però si segue un'altra strada legata come al solito alla semplificazione circuitale. Invece di realizzare una R.C. per ogni funzione booleana, si preferisce realizzare delle R.C. leggermente più complesse, che permettono però di svolgere diverse funzioni con lo stesso circuito; in Figura 6.13, ad esempio, vediamo un dispositivo a 4 bit che svolge 4 funzioni differenti a seconda dei livelli logici assunti dai cosiddetti ingressi di selezione che sono S0 e S1. Dalla tabella della verità di Figura 6.13 si vede che attribuendo ai due ingressi S0 e S1 i 4=22 possibili valori binari 00b, 01b, 10b e 11b, si possono ottenere in uscita 4 differenti elaborazioni dello stesso nibble in ingresso. In particolare: In questi ultimi due casi, il nibble in ingresso è ininfluente; con lo stesso circuito quindi realizziamo 4 funzioni differenti che altrimenti avrebbero richiesto 4 circuiti diversi.
I circuiti complementatori sono molto importanti in quanto vengono largamente utilizzati dalla CPU in molte operazioni; ricordiamo, ad esempio, che la CPU esegue moltiplicazioni e divisioni solo sui numeri senza segno. Eventuali numeri negativi vengono prima di tutto convertiti nei corrispondenti numeri positivi; per poter effettuare queste conversioni vengono appunto utilizzati i circuiti complementatori.

6.6 Moltiplicazione tra numeri binari

Nei precedenti capitoli è stato detto che la CPU effettua la moltiplicazione attraverso un metodo fortemente basato sullo stesso procedimento che utilizziamo noi esseri umani quando eseguiamo questa operazione con carta e penna; abbiamo anche visto che la moltiplicazione provoca un cambiamento di modulo, per cui la CPU ha bisogno di sapere se vogliamo operare nell'insieme dei numeri senza segno o nell'insieme dei numeri con segno.
Moltiplicando tra loro due numeri binari a n bit, otteniamo un risultato interamente rappresentabile attraverso un numero binario a 2n bit; partiamo allora dai numeri interi senza segno a 4 bit (1 nibble), e supponiamo di voler calcolare, ad esempio: 
10 x 13 = 130
Traducendo tutto in binario e applicando lo stesso procedimento che si segue con carta e penna, otteniamo la situazione mostrata in Figura 6.14. Osserviamo che moltiplicando tra loro due numeri a 4 bit, otteniamo un risultato che richiede al massimo 8 bit; la CPU tiene conto di questo aspetto e quindi è impossibile che la moltiplicazione possa provocare un overflow.
Notiamo anche l'estrema semplicità del calcolo dei prodotti parziali; considerando il primo fattore 1010b, si possono presentare solamente i due casi seguenti: 
a) 1010b x 0b = 0000b
b) 1010b x 1b = 1010b
La Figura 6.15 mostra in forma simbolica la moltiplicazione tra i due nibble A3A2A1A0 e B3B2B1B0. Cominciamo con l'osservare che le singole cifre dei prodotti parziali non sono altro che moltiplicazioni tra singoli bit; nel precedente capitolo abbiamo visto che il prodotto binario è ottenibile attraverso una porta AND a 2 ingressi. Nel caso di Figura 6.15 abbiamo, ad esempio: 
A3 x B2 = A3 AND B2
Osserviamo ora che la cifra P0 del prodotto finale (cifra meno significativa) si ottiene direttamente da A0xB0; abbiamo quindi: 
P0 = A0 AND B0
La cifra P1 del prodotto finale è data da: 
P1 = (A0 AND B1) + (A1 AND B0)
Per svolgere questa somma utilizziamo un H.A. che produce in uscita la cifra P1 e il riporto C1 destinato alla colonna successiva.
La cifra P2 del prodotto finale è data da: 
P2 = (A0 AND B2) + (A1 AND B1) + (A2 AND B0) + C1
Per svolgere la prima somma (A0 AND B2) + (A1 AND B1) utilizziamo un H.A. che produce in uscita la somma parziale P2' e il riporto C2' destinato alla colonna successiva; per svolgere la seconda somma tra P2' e (A2 AND B0) utilizziamo un F.A. che riceve in ingresso anche il riporto C1 derivante dal calcolo di P1 e produce in uscita la cifra P2 e il riporto C2'' destinato alla colonna successiva.
La cifra P3 del prodotto finale è data da: 
P3 = (A0 AND B3) + (A1 AND B2) + (A2 AND B1) + (A3 AND B0) + C2' + C2''
Per svolgere la prima somma (A0 AND B3) + (A1 AND B2) utilizziamo un H.A. che produce in uscita la somma parziale P3' e il riporto C3' destinato alla colonna successiva; per svolgere la seconda somma tra P3' e (A2 AND B1) utilizziamo un F.A. che riceve in ingresso anche il riporto C2' derivante dal calcolo di P2, e produce in uscita la somma parziale P3'' e il riporto C3'' destinato alla colonna successiva. Per svolgere la terza somma tra P3'' e (A3 AND B0) utilizziamo un F.A. che riceve in ingresso anche il riporto C2'' derivante dal calcolo di P2 e produce in uscita la cifra P3 e il riporto C3''' destinato alla colonna successiva.
La cifra P4 del prodotto finale è data da: 
P4 = (A1 AND B3) + (A2 AND B2) + (A3 AND B1) + C3' + C3'' + C3'''
Per svolgere la prima somma (A1 AND B3) + (A2 AND B2) utilizziamo un F.A. che riceve in ingresso anche il riporto C3' derivante dal calcolo di P3 e produce in uscita la somma parziale P4' e il riporto C4' destinato alla colonna successiva; per svolgere la seconda somma tra P4' e (A3 AND B1) utilizziamo un F.A. che riceve in ingresso anche il riporto C3'' derivante dal calcolo di P3 e produce in uscita la somma parziale P4'' e il riporto C4'' destinato alla colonna successiva. A questo punto utilizziamo un H.A. per sommare P4'' con il riporto C3''' derivante dal calcolo di P3; in questo modo otteniamo in uscita dall'H.A. la cifra P4 e il riporto C4''' destinato alla colonna successiva.
La cifra P5 del prodotto finale è data da: 
P5 = (A2 AND B3) + (A3 AND B2) + C4' + C4'' + C4'''
Per svolgere questa somma utilizziamo un F.A. che riceve in ingresso anche il riporto C4' derivante dal calcolo di P4 e produce in uscita la somma parziale P5' e il riporto C5' destinato alla colonna successiva. A questo punto utilizziamo un F.A. per sommare P5' con i riporti C4'' e C4''' derivanti dal calcolo di P4; in questo modo otteniamo in uscita dal F.A. la cifra P5 e il riporto C5'' destinato alla colonna successiva.
La cifra P6 del prodotto finale è data da: 
P6 = (A3 AND B3) + C5' + C5''
Utilizziamo allora un F.A. che riceve in ingresso anche i riporti C5' e C5'' derivanti dal calcolo di P5; in questo modo otteniamo in uscita dal F.A. la cifra P6 e il riporto C6 destinato alla colonna successiva.
Naturalmente, il riporto C6 non è altro che la cifra P7 del prodotto finale; quest'ultimo passaggio conferma che nella moltiplicazione l'overflow è impossibile.

Applicando alla lettera i concetti appena esposti, otteniamo la R.C. di Figura 6.16 che permette di moltiplicare numeri interi senza segno a 4 bit. La R.C. appena descritta, pur essendo perfettamente funzionante, ha un valore puramente teorico; nella pratica, infatti, si utilizzano R.C. che pur essendo basate sul circuito di Figura 6.16, presentano notevoli ottimizzazioni che hanno lo scopo di aumentare la velocità di calcolo. In ogni caso appare chiaro il fatto che queste ottimizzazioni, per quanto spinte possano essere, danno luogo ad R.C. nettamente più complesse di quelle utilizzate dalla CPU per le addizioni e per le sottrazioni; proprio per questo motivo, la moltiplicazione impone alla CPU un tempo di calcolo nettamente superiore a quello necessario per l'esecuzione delle addizioni e delle sottrazioni.

La R.C. di Figura 6.16 può essere utilizzata anche per la moltiplicazione tra numeri interi con segno; a tale proposito bisogna prima di tutto cambiare di segno gli eventuali fattori negativi. In teoria questo metodo funziona, ma la R.C. che ne deriva tende a diventare molto più complessa di quella di Figura 6.16; proprio per questo motivo, molte CPU utilizzano R.C. appositamente concepite per operare direttamente sui numeri interi con segno.

6.7 Divisione tra numeri binari

Anche la divisione viene effettuata dalla CPU attraverso un metodo basato sullo stesso procedimento che utilizziamo noi esseri umani quando eseguiamo questa operazione con carta e penna; come viene mostrato in seguito, l'algoritmo utilizzato dalla CPU comporta un cambiamento di modulo, per cui è necessario specificare se vogliamo operare nell'insieme dei numeri senza segno o nell'insieme dei numeri con segno.
Dividendo tra loro due numeri binari a n bit, otteniamo un quoziente minore o uguale al dividendo e quindi interamente rappresentabile attraverso un numero binario a n bit; il resto, inoltre, è minore o uguale al divisore, per cui anch'esso è interamente rappresentabile attraverso un numero binario a n bit.
Partiamo come al solito dai numeri interi senza segno a 4 bit (1 nibble) e supponiamo di voler calcolare, ad esempio: 
14 / 5 = [Q = 2, R = 4]
Traducendo tutto in binario e applicando lo stesso procedimento che si segue con carta e penna, otteniamo la situazione mostrata in Figura 6.17. Analizzando la Figura 6.17 possiamo riassumere i passi necessari per il classico algoritmo di calcolo della divisione: Per poter realizzare un circuito logico capace di effettuare l'operazione di divisione, dobbiamo elaborare il precedente algoritmo in modo da renderlo generale e ripetitivo; dobbiamo cioè fare in modo che la CPU calcoli la divisione ripetendo (iterando) uno stesso procedimento per un determinato numero di volte. Per raggiungere questo obiettivo si utilizza un algoritmo perfettamente equivalente a quello appena illustrato; in riferimento come al solito ai numeri interi senza segno a 4 bit, i passi da compiere sono i seguenti: Proviamo ad applicare questo algoritmo alla precedente divisione di 1110b per 0101b; il risultato che si ottiene viene mostrato dalla Figura 6.18. In riferimento quindi ai numeri interi senza segno a 4 bit, possiamo dire che l'algoritmo appena illustrato consiste nel ripetere per 4 volte uno stesso procedimento che comprende uno shift di un posto verso destra delle cifre del divisore e un tentativo di eseguire una sottrazione tra il resto parziale e lo stesso divisore.
Nel caso della moltiplicazione, abbiamo risolto il problema attraverso una R.C. relativamente semplice; nel caso della divisione, invece, la situazione si presenta più complessa. La necessità di dover stabilire se effettuare o meno la sottrazione, rende necessario un apposito dispositivo capace di prendere una tale decisione; ci serve cioè un dispositivo derivato dal F.S. e dotato di una linea di controllo attraverso la quale si possa abilitare o meno la sottrazione. Questo dispositivo prende il nome di Conditional Subtractor (C.S.) o sottrattore condizionale; lo schema circuitale del C.S. viene mostrato in Figura 6.19a, mentre lo schema simbolico viene mostrato in Figura 6.19b. Come si può notare, la struttura del C.S. è del tutto simile alla struttura del F.S.; sono presenti, infatti, l'ingresso Ai per il bit del minuendo, l'ingresso Bi per il bit del sottraendo, l'ingresso Cin (Carry In) per il prestito richiesto dalla colonna precedente, l'uscita Cout (Carry Out) per il prestito richiesto alla colonna successiva e l'uscita D per il risultato finale che nel caso del F.S. è dato da: 
D = Ai - (Bi + Cin)
In Figura 6.19 notiamo però anche la presenza della linea Enable che attraversa il C.S. da Ein a Eout; proprio attraverso questa linea è possibile modificare il comportamento del C.S.. Come si può vedere in Figura 6.19a, l'ingresso Ai e l'uscita D' del F.S. rappresentano i 2 ingressi di un MUX da 2 a 1; analizzando allora questo circuito possiamo dire che:

a) se la linea Enable è a livello logico 0, viene abilitato l'ingresso D' del MUX, per cui il C.S. calcola: 
D = Ai - (Bi + Cin)
b) se la linea Enable è a livello logico 1, viene abilitato l'ingresso Ai del MUX, per cui il C.S. calcola: 
D = Ai
Possiamo dire quindi che se la linea Enable è a livello logico 0, il C.S. effettua normalmente la sottrazione; se, invece, la linea Enable è a livello logico 1, si ottiene sull'uscita D il bit Ai del minuendo. Si tenga presente che in Figura 6.19 la linea Enable non ha niente a che vedere con il segnale di abilitazione E del MUX di Figura 6.1.
A questo punto si presenta il problema di come pilotare la linea Enable; in sostanza, la linea Enable deve essere portata a livello logico 0 solo quando il minuendo è maggiore o uguale al sottraendo. Il metodo che viene utilizzato, consiste nello sfruttare l'uscita Cout che viene collegata all'ingresso Ein; per capire il funzionamento di questo sistema, analizziamo in dettaglio il funzionamento del C.S. di Figura 6.19: In base alle considerazioni appena esposte, si intuisce facilmente che per ottenere la sottrazione condizionale tra due numeri binari a 4 bit, basta collegare in serie 4 C.S.; il circuito che si ottiene viene mostrato in Figura 6.20. Supponiamo, ad esempio, di avere A=1110b e B=0101b; in questo caso si vede subito che: La linea Enable si porta quindi a livello logico 0 e il risultato della sottrazione (1001b) viene confermato; se il quarto C.S. avesse prodotto Cout=1, la linea Enable si sarebbe portata a livello logico 1 annullando il risultato della sottrazione e producendo quindi in uscita il nibble A=1110b. In quest'ultimo caso è come se il minuendo venisse ripristinato (restored); proprio per questo motivo, l'algoritmo di calcolo della divisione con i C.S. prende il nome di restoring division (divisione con ripristino).
Applicando le considerazioni appena esposte, possiamo implementare finalmente il circuito per la divisione tra numeri interi senza segno a 4 bit; ricordando che l'algoritmo esposto in Figura 6.18 prevede un procedimento ripetitivo costituito da uno shift di un posto verso destra delle cifre del divisore e da un tentativo di sottrazione tra resto parziale e divisore stesso, si ottiene il circuito mostrato in Figura 6.21. Gli ingressi a0, a1, a2, a3, a4, a5 e a6 contengono i 4 bit del dividendo e rappresentano anche il resto parziale; naturalmente gli ingressi a4, a5 e a6 vengono portati a livello logico basso. Gli ingressi b0, b1, b2 e b3 contengono i 4 bit del divisore; come si può notare, il divisore si trova shiftato a sinistra di 3 posizioni anziché di 4 in quanto (Figura 6.18) 4 shift a sinistra e uno a destra equivalgono a 3 shitf a sinistra.
La riga più in alto dei C.S. esegue la sottrazione tra a6a5a4a3 e b3b2b1b0; se alla fine non si verifica alcun prestito il risultato della sottrazione viene confermato, mentre in caso contrario viene ripristinato il minuendo e il risultato prodotto in uscita è a6a5a4a3. Si nota subito che l'uscita q3 vale 1 se il minuendo è maggiore o uguale al sottraendo e 0 in caso contrario; possiamo dire quindi che q3 non è altro che uno dei 4 bit del quoziente finale.
Le considerazioni appena esposte si applicano naturalmente anche alle altre tre righe dei C.S.; terminata la divisione, sulle quattro uscite q0, q1, q2 e q3 preleviamo i 4 bit del quoziente finale, mentre sulle quattro uscite r0, r1, r2 e r3 preleviamo i 4 bit del resto finale.

Come al solito, il circuito di Figura 6.21 pur essendo perfettamente funzionante ha un valore puramente teorico; nella pratica, infatti, si utilizza una versione elaborata e notevolmente ottimizzata del circuito appena descritto. Come è facile intuire però, la divisione si presenta come una operazione particolarmente complessa per la CPU; infatti, la divisione comporta per la CPU un tempo di calcolo superiore persino a quello necessario per la moltiplicazione (soprattutto nel caso di restoring delle varie sottrazioni).

Il circuito di Figura 6.21 può essere utilizzato anche per la divisione tra numeri interi con segno; a tale proposito bisogna prima di tutto cambiare di segno gli eventuali operandi negativi.

In relazione alla divisione la CPU ha bisogno di distinguere tra numeri con o senza segno in quanto abbiamo visto che per poter utilizzare il circuito di Figura 6.21, è necessario modificare l'ampiezza in bit del dividendo e del divisore; tutto ciò dimostra che il metodo di calcolo della divisione utilizzato dalla CPU provoca un cambiamento di modulo.

6.8 Scorrimento dei bit di un numero binario

Le considerazioni esposte in precedenza ci hanno permesso di constatare che la moltiplicazione e la divisione sono operazioni particolarmente impegnative per la CPU e richiedono tempi di calcolo notevolmente superiori a quelli necessari per l'addizione o per la sottrazione; purtroppo nel caso generale non è possibile ovviare a questo problema. Nei precedenti capitoli però abbiamo visto che per la moltiplicazione e la divisione esiste un caso particolare che ci permette di velocizzare notevolmente queste operazioni; esaminiamo allora questo caso particolare che è legato ancora una volta alla struttura dei sistemi di numerazione posizionali.

6.8.1 Moltiplicazione di un numero intero binario per una potenza intera del 2

Nel caso, ad esempio, della base 10, abbiamo visto che moltiplicare un numero intero n per 10 (cioè per la base), equivale ad aggiungere uno zero alla destra del numero stesso. Tutte le cifre di n scorrono verso sinistra di una posizione aumentando quindi il loro peso; infatti, la moltiplicazione di n per 10 trasforma le unità di n in decine, le decine in centinaia, le centinaia in migliaia e così via.
Analogamente, moltiplicare n per 100 (102) equivale ad aggiungere due zeri alla destra di n facendo scorrere tutte le sue cifre di due posizioni verso sinistra; moltiplicare in generale n per 10m equivale ad aggiungere m zeri alla destra di n facendo scorrere tutte le sue cifre di m posizioni verso sinistra.
Nel caso ancora più generale di un numero intero n espresso in base b qualunque, moltiplicare n per bm equivale ad aggiungere m zeri alla destra di n, facendo scorrere tutte le sue cifre di m posizioni verso sinistra. Possiamo dire allora che, ogni volta che uno dei due fattori può essere espresso sotto forma di potenza intera della base, la moltiplicazione si traduce in uno scorrimento verso sinistra delle cifre dell'altro fattore, di un numero di posizioni pari all'esponente della base; risulta evidente che in questo caso, i calcoli diventano estremamente semplici e veloci rispetto al metodo tradizionale.
Proprio per questo motivo, abbiamo visto che le CPU della famiglia 80x86 forniscono l'istruzione SHL (Shift Logical Left) per gli scorrimenti verso sinistra dei bit di un numero intero senza segno e l'istruzione SAL (Shift Arithmetic Left) per gli scorrimenti verso sinistra dei bit di un numero intero con segno; siccome però il segno viene codificato nel MSB di un numero binario, le due istruzioni SHL e SAL sono assolutamente equivalenti (e quindi interscambiabili).

Per chiarire questi concetti molto importanti, è necessario tenere presente che le considerazioni appena esposte hanno un valore puramente teorico; in teoria, infatti, possiamo prendere un numero n e far scorrere i suoi bit di migliaia di posizioni verso sinistra o verso destra. Nel caso del computer però il discorso cambia radicalmente; non bisogna dimenticare, infatti, che la CPU gestisce i numeri binari assegnando a ciascuno di essi una ampiezza fissa in bit. Ogni numero binario inoltre viene sistemato in una locazione ad esso riservata; consideriamo, ad esempio, la situazione mostrata in Figura 6.22.
Figura 6.22
00100111

Questa figura mostra una locazione da 8 bit riservata al numero binario n=00100111b; il numero binario n si trova confinato all'interno della sua locazione da 8 bit e tutte le modifiche compiute su di esso, devono produrre un risultato interamente rappresentabile attraverso questi 8 bit.
Analizzando allora la Figura 6.22 si intuisce subito che eccedendo nello scorrimento verso sinistra dei bit di n, si rischia di ottenere un risultato sbagliato; il problema che si verifica è dovuto chiaramente al fatto che un numero eccessivo di scorrimenti può provocare la fuoriuscita (dalla parte sinistra della locazione di Figura 6.22) di cifre significative per il risultato finale.
Supponiamo, ad esempio, di far scorrere (con SHL o con SAL) ripetutamente di un posto verso sinistra i bit del numero binario di Figura 6.22; in questo modo otteniamo la seguente successione: 
01001110b, 10011100b, 00111000b, 01110000b, ...
Tutti gli scorrimenti si applicano agli 8 bit della locazione di Figura 6.22 e devono quindi produrre un risultato interamente contenibile nella locazione stessa; è chiaro quindi che dopo un certo numero di scorrimenti, comincerà a verificarsi il trabocco da sinistra di cifre significative del risultato.
Nell'insieme dei numeri senza segno il numero binario 00100111b equivale a 39; il primo scorrimento produce il risultato 78 che è corretto in quanto rappresenta il prodotto della moltiplicazione di 39 per 2. Il secondo scorrimento produce il risultato 156 che è corretto in quanto rappresenta il prodotto della moltiplicazione di 39 per 22; il terzo scorrimento produce il risultato 56 che è chiaramente sbagliato. L'errore è dovuto al fatto che moltiplicando 39 per 23 si ottiene un numero a 9 bit che non è più contenibile nella locazione di Figura 6.22; il bit più significativo del risultato (di valore 1) trabocca da sinistra e invalida il risultato finale.

Anche nell'insieme dei numeri con segno il numero binario 00100111b equivale a +39; il primo scorrimento produce il risultato +78 che è corretto in quanto rappresenta il prodotto della moltiplicazione di +39 per 2. Il secondo scorrimento produce il risultato -100 che è chiaramente sbagliato; l'errore questa volta è dovuto al fatto che moltiplicando +39 per 22 si ottiene un numero positivo (+156) più grande di +127 che è il massimo numero positivo rappresentabile con 8 bit. Osserviamo, infatti, che il bit di segno che inizialmente valeva 0, è traboccato da sinistra e il suo posto è stato preso da un bit di valore 1; il numero n quindi si è trasformato da positivo in negativo.

Le considerazioni appena esposte ci fanno capire che se intendiamo utilizzare SHL o SAL per calcolare rapidamente il prodotto di un numero binario per una potenza intera del 2, dobbiamo essere certi della validità del risultato che verrà fornito da queste istruzioni; in sostanza, dobbiamo verificare che nella parte sinistra del numero n ci sia un certo "spazio di sicurezza". Nel caso dei numeri senza segno dobbiamo verificare che nella parte sinistra di n ci sia un numero sufficiente di zeri; nel caso dei numeri con segno dobbiamo verificare che nella parte sinistra di n ci sia un numero sufficiente di bit di segno (0 per i numeri interi positivi e 1 per quelli negativi).

6.8.2 Divisione di un numero intero binario per una potenza intera del 2

Passando alla divisione sappiamo che in base 10, dividendo un numero intero positivo n per 10, si provoca uno scorrimento di una posizione verso destra delle cifre di n; la cifra meno significativa di n (cioè quella più a destra) in seguito allo scorrimento, "trabocca" da destra e viene persa. Tutte le cifre di n scorrono verso destra di una posizione riducendo quindi il loro peso; infatti, la divisione di n per 10 trasforma le decine di n in unità, le centinaia in decine, le migliaia in centinaia e così via. La cifra che trabocca da destra rappresenta il resto della divisione; abbiamo, ad esempio: 
138 / 10 = [Q = 13, R = 8]
Quindi le tre cifre di 138 scorrono verso destra di una posizione facendo uscire l'8 che rappresenta proprio il resto della divisione.
Analogamente: 
138 / 100 = [Q = 1, R = 38]
Le tre cifre di 138 quindi scorrono verso destra di due posizioni facendo uscire il 38 che anche in questo caso, rappresenta il resto della divisione.
Generalizzando, nel caso di una base b qualunque, dividendo un numero intero positivo n per bm si provoca uno scorrimento di m posizioni verso destra delle cifre di n facendo così traboccare le m cifre più a destra; le cifre rimaste rappresentano il quoziente, mentre le m cifre traboccate da destra rappresentano il resto.
In definitiva, se il divisore può essere espresso sotto forma di potenza intera della base, utilizzando questa tecnica si esegue la divisione in modo nettamente più rapido rispetto al metodo tradizionale; proprio per questo motivo, abbiamo già visto che le CPU della famiglia 80x86 forniscono l'istruzione SHR (Shift Logical Right) per gli scorrimenti verso destra dei bit di un numero intero senza segno e l'istruzione SAR (Shift Arithmetic Right) per gli scorrimenti verso destra dei bit di un numero intero con segno. Questa volta però le due istruzioni SHR e SAR non sono equivalenti; la differenza di comportamento tra SHR e SAR è legata al fatto che nello scorrimento verso destra dei bit di un numero, è necessario distinguere tra numeri con segno e numeri senza segno. Osserviamo, infatti, che: 
+138 / 10 = [Q = +13, R = +8]
mentre: 
-138 / 10 = [Q = -13, R = -8]
Vediamo allora come viene gestita questa situazione da SHR e da SAR; a tale proposito consideriamo la situazione di Figura 6.23 che rappresenta come al solito un numero binario contenuto in una locazione da 8 bit:
Figura 6.23
10110000

Nell'insieme dei numeri interi senza segno, il numero binario 10110000b equivale a 176; utilizziamo allora SHR per far scorrere ripetutamente di un posto verso destra i bit del numero binario di Figura 23. In questo modo otteniamo la seguente successione: 
01011000b, 00101100b, 00010110b, 00001011b, 00000101b, ...
Il primo scorrimento produce il risultato 88 (con resto 0b) che è corretto in quanto rappresenta il quoziente della divisione di 176 per 2; il secondo scorrimento produce il risultato 44 (con resto 00b) che è corretto in quanto rappresenta il quoziente della divisione di 176 per 22. Il terzo scorrimento produce il risultato 22 (con resto 000b) che è corretto in quanto rappresenta il quoziente della divisione di 176 per 23; il quarto scorrimento produce il risultato 11 (con resto 0000b) che è corretto in quanto rappresenta il quoziente della divisione di 176 per 24. Il quinto scorrimento produce il risultato 5 (con resto 10000b) che è corretto in quanto rappresenta il quoziente della divisione di 176 per 25.
Nel caso generale possiamo dire allora che l'utilizzo di SHR per la divisione rapida di un numero intero senza segno per una potenza intera del 2, produce sempre il risultato corretto; la sequenza di cifre che trabocca da destra rappresenta sempre il resto della divisione appena effettuata. Osserviamo poi che SHR opera sui numeri interi positivi, per cui riempie con degli zeri i posti che si liberano a sinistra in seguito allo scorrimento verso destra dei bit di un numero binario; in questo modo si ottiene sempre un quoziente positivo. È chiaro allora che dopo un certo numero di scorrimenti verso destra dei bit di un numero positivo n, il quoziente diventa 0; nel caso, ad esempio, di un numero binario a 8 bit, dopo 8 scorrimenti verso destra delle cifre di questo numero si ottiene sicuramente un quoziente nullo.

Nell'insieme dei numeri interi con segno, il numero binario 10110000b di Figura 6.23 equivale a -80; utilizziamo allora SAR per far scorrere ripetutamente di un posto verso destra i bit di questo numero binario. In questo modo otteniamo la seguente successione: 
11011000b, 11101100b, 11110110b, 11111011b, 11111101b, ...
Osserviamo subito che SAR riempie con degli 1 i posti che si liberano a sinistra del numero 10110000b in seguito allo scorrimento delle sue cifre verso destra; questo perché il MSB di 10110000b è 1 e quindi SAR deve preservare il bit di segno.
Il primo scorrimento produce il risultato -40 (con resto 0b) che è corretto in quanto rappresenta il quoziente della divisione di -80 per 2; il secondo scorrimento produce il risultato -20 (con resto 00b) che è corretto in quanto rappresenta il quoziente della divisione di -80 per 22. Il terzo scorrimento produce il risultato -10 (con resto 000b) che è corretto in quanto rappresenta il quoziente della divisione di -80 per 23; il quarto scorrimento produce il risultato -5 (con resto 0000b) che è corretto in quanto rappresenta il quoziente della divisione di -80 per 24. Il quinto scorrimento produce il risultato -3 (con resto 10000b) che è però sbagliato in quanto dividendo -80 per 25 si dovrebbe ottenere il quoziente -2 e il resto -16!
Dall'analisi dei risultati ottenuti con SHR e con SAR emerge allora che: Per capire il perché di questa situazione, bisogna tenere presente che la CPU, nell'eseguire una divisione intera tra due numeri interi con o senza segno, arrotonda sempre il quoziente verso lo zero; questo comportamento è corretto in quanto rispetta le regole matematiche della divisione intera. Ad esempio, il quoziente +4.9 deve essere arrotondato a +4 e non a +5; analogamente, il quoziente -6.8 deve essere arrotondato a -6 e non a -7!

Con l'istruzione SHR, questa regola matematica viene sempre rispettata; ciò è dovuto al metodo utilizzato dalla CPU, per codificare i numeri interi senza segno.
In riferimento, ad esempio, ai numeri interi senza segno a 8 bit, sappiamo che la CPU utilizza le codifiche binarie comprese tra 00000000b e 11111111b, per rappresentare i numeri interi senza segno compresi, rispettivamente, tra 0 e 255; come si può notare, i numeri interi senza segno crescenti (0, 1, 2, etc) hanno una codifica binaria crescente (00000000b, 00000001b, 00000010b, etc).
La conseguenza pratica di tutto ciò è data dal fatto che, utilizzando l'istruzione SHR per far scorrere di n posti verso destra le cifre di un numero intero senza segno m, si ottiene sempre un risultato arrotondato verso lo zero; tale risultato, coincide quindi con il quoziente della divisione intera tra m e 2n e inoltre, le n cifre traboccate da destra, coincidono con il resto della divisione stessa!

Con l'istruzione SAR, questa regola matematica non viene sempre rispettata; ciò è dovuto al metodo utilizzato dalla CPU, per codificare i numeri interi con segno (codifica binaria in complemento a 2).
In riferimento, ad esempio, ai numeri interi con segno a 8 bit, sappiamo che: Come si può notare, i numeri interi positivi crescenti (+0, +1, +2, etc), hanno una codifica binaria crescente (00000000b, 00000001b, 00000010b, etc); invece, i numeri interi negativi crescenti in valore assoluto (|-1|, |-2|, |-3|, etc), hanno una codifica binaria decrescente (11111111b, 11111110b, 11111101b, etc)!
La conseguenza pratica di tutto ciò è data dal fatto che, utilizzando l'istruzione SAR per far scorrere di n posti verso destra le cifre di un numero intero positivo m, si ottiene sempre un risultato arrotondato verso lo zero; tale risultato, coincide quindi con il quoziente della divisione intera tra m e 2n e, inoltre, le n cifre traboccate da destra, coincidono con il resto della divisione stessa.
Utilizzando l'istruzione SAR per far scorrere di n posti verso destra le cifre di un numero intero negativo m, si ottiene sempre un risultato arrotondato verso l'infinito negativo (-∞); ad esempio, il risultato -5.3 viene arrotondato a -6 anziché a -5.
Se m è un numero intero negativo multiplo intero di 2n, si ottiene un risultato che coincide con il quoziente della divisione intera tra m e 2n; infatti, in questo caso il resto è zero e quindi il quoziente non necessita di nessun arrotondamento (quoziente esatto).
Se m è un numero intero negativo non divisibile per 2n, si ottiene un risultato che non coincide con il quoziente della divisione intera tra m e 2n; infatti, in questo caso il resto è diverso da zero e quindi il quoziente necessita di un arrotondamento. Mentre però la divisione arrotonda il suo quoziente verso lo zero, l'istruzione SAR arrotonda il suo risultato verso l'infinito negativo (ad esempio, il valore -9.3 viene arrotondato a -9 dalla divisione e a -10 da SAR); in tal caso, il risultato prodotto da SAR differisce del valore -1 rispetto al quoziente della divisione!

I problemi appena illustrati, inducono decisamente ad evitare l'uso degli scorrimenti aritmetici a destra per dividere rapidamente numeri negativi per potenze intere del 2; appare molto più sensato, in questo caso, ricorrere alla divisione tradizionale che comporta però, come sappiamo, una notevole lentezza di esecuzione.

6.8.3 Verifica del risultato attraverso i flags

Come accade per tutte le altre operazioni logico aritmetiche, la CPU utilizza i vari flags per fornire al programmatore tutti i dettagli sul risultato di una operazione appena eseguita; analizziamo innanzi tutto le informazioni che ci vengono fornite attraverso CF, SF e OF in relazione al risultato prodotto dalle istruzioni SHL, SAL, SHR e SAR applicate ad un numero binario n.
Il flag CF contiene sempre l'ultimo bit traboccato da n (da destra o da sinistra); se, ad esempio, facciamo scorrere di un posto verso destra i bit di 01001101b, si ottiene CF=1 in quanto il bit traboccato da destra ha valore 1.
Il flag SF contiene sempre il MSB del risultato appena ottenuto; se, ad esempio, facciamo scorrere di un posto verso sinistra i bit di 01001101b, si ottiene il risultato 10011010b, e quindi SF=1 in quanto il MSB ha assunto il valore 1.
Il flag OF si porta a 1 ogni volta che il MSB del risultato appena ottenuto cambia da 0 a 1 o da 1 a 0; se, ad esempio, facciamo scorrere di un posto verso sinistra i bit di 01001101b, si ottiene il risultato 10011010b e quindi OF=1 in quanto il valore del MSB è cambiato da 0 a 1.

6.8.4 Esempio di shifter a 4 bit

Vediamo ora come può essere implementata una R.C. capace di effettuare lo scorrimento dei bit di un numero binario; la Figura 6.24 illustra uno "shifter" a 4 bit capace di implementare tutte le 4 istruzioni SHL, SAL, SHR e SAR. Indichiamo con A0, A1, A2 e A3 i 4 bit del nibble in ingresso e con Y0, Y1, Y2 e Y3 i 4 bit del nibble in uscita; abbiamo poi l'uscita CF che permette di inviare al Carry Flag il bit appena scartato, e infine i seguenti tre ingressi di abilitazione: Come si può constatare attraverso la Figura 6.24 si ha, inoltre: 
SF = Y3, OF = A3 EX-NOR Y3
Ponendo in Figura 6.24 SHL=1, SHR=0 e SAR=0, si abilita la R.C. allo scorrimento logico/aritmetico verso sinistra dei bit del nibble in ingresso; come già sappiamo, questa operazione produce effetti identici, sia sui numeri senza segno, sia sui numeri con segno (SHL=SAL).
Ponendo in Figura 6.24 SHL=0, SHR=1 e SAR=0, si abilita la R.C. allo scorrimento logico verso destra dei bit del nibble in ingresso; il nibble in ingresso deve essere quindi un numero senza segno.
Ponendo in Figura 6.24 SHL=0, SHR=1 e SAR=1, si abilita la R.C. allo scorrimento aritmetico verso destra dei bit del nibble in ingresso; il nibble in ingresso deve essere quindi un numero con segno.

In relazione agli scorrimenti dei bit di un numero binario, è necessario sottolineare un aspetto molto importante; come si può facilmente intuire, più aumenta il numero di shift da effettuare, più aumentano i tempi per l'esecuzione di questa operazione da parte della CPU. È chiaro allora che al crescere del numero di shift da effettuare diminuiscono i vantaggi di questa tecnica rispetto alle moltiplicazioni e divisioni tradizionali.

6.9 Rotazione dei bit di un numero binario

In conclusione di questo capitolo, citiamo anche l'operazione di rotazione dei bit di un numero binario; questa operazione è simile a quella di scorrimento dei bit, con la differenza però che i bit che traboccano da una estremità dell'operando, rientrano in sequenza dall'altra estremità dell'operando stesso. Appare evidente che in relazione alla operazione di rotazione dei bit, non ha alcun senso la distinzione tra numeri senza segno e numeri con segno.

Le CPU della famiglia 80x86 mettono a disposizione 4 istruzioni per la rotazione dei bit, che sono: ROL, RCL, ROR, RCR.
L'istruzione ROL (Rotate Left) fa scorrere verso sinistra i bit di un numero binario; i bit che traboccano da sinistra rientrano in sequenza da destra. In Figura 6.24 si può simulare l'istruzione ROL abilitando l'ingresso SHL e collegando l'uscita Y0 all'uscita CF.
L'istruzione RCL (Rotate Through Carry Left) fa scorrere verso sinistra i bit di un numero binario; i bit che traboccano da sinistra finiscono in sequenza nel flag CF, mentre i vecchi bit contenuti in CF rientrano in sequenza dalla destra del numero binario. In Figura 6.24 si può simulare l'istruzione RCL abilitando l'ingresso SHL e memorizzando in Y0 il vecchio contenuto di CF (prima di ogni shitf).
L'istruzione ROR (Rotate Right) fa scorrere verso destra i bit di un numero binario; i bit che traboccano da destra rientrano in sequenza da sinistra. In Figura 6.24 si può simulare l'istruzione ROR abilitando l'ingresso SHR e collegando l'uscita Y3 all'uscita CF.
L'istruzione RCR (Rotate Through Carry Right) fa scorrere verso destra i bit di un numero binario; i bit che traboccano da destra finiscono in sequenza nel flag CF, mentre i vecchi bit contenuti in CF rientrano in sequenza dalla sinistra del numero binario. In Figura 6.24 si può simulare l'istruzione RCR abilitando l'ingresso SHR e memorizzando in Y3 il vecchio contenuto di CF (prima di ogni shitf).

Dalle considerazioni appena esposte si intuisce che la R.C. di Figura 6.23 può essere facilmente modificata per poter implementare, sia le istruzioni di scorrimento, sia le istruzioni di rotazione dei bit; nella pratica si segue proprio questa strada che permette di ottenere un notevole risparmio di porte logiche.