La sottrazione binaria

Lo scopo di questa procedura è quello di determinare la rappresentazione binaria della differenza tra due numeri binari.

Più formalmente, date le rappresentazioni binarie con "n" cifre di due numeri naturali:

A = (an-1 . . . a2a1a0)2

B = (bn-1 . . . b2b1b0)2

si vuole determinare la rappresentazione binaria del numero naturale:

D = (dn-1 . . . d2d1d0)2

in modo tale che

D = A - B.


Per risolvere questo problema si deve disegnare la seguente tabella:

i  | n  . . . . 3  2  1  0 
pi | pn . . . . p3 p2 p1 p0 |
a
i  an-1 . . a3 a2 a1 a0 |-
bi  bn-1 . . b3 b2 b1 b0 |=
di  dn-1 . . d3 d2 d1 d0 |

Dove ciascun elemento della tabella va calcolato per mezzo della seguente procedura: 

1. p0 = 0;
2. Per i = 0, 1, 2, . . . n-1 ripeti:
   1. Se ai < bi + pi allora pi+1 = 1, altrimenti pi+1 = 0;
   2. di = ai + 2·pi+1 - bi - pi;

Alla fine, se "pn = 0", il risultato è corretto (D = A - B), altrimenti:

D = A + (2n - B)


Esempio di sottrazione tra due numeri in base 2:

A = (101)2 = 1 + 4 = 5.

B = (111)2 = 1 + 2 + 4 = 7. 

i |3 2 1 0|
pi|1 1 0 0|
ai|  1 0 1|
bi|  1 1 1|
di|  1 1 0|

D = (110)2 = 2 + 4 = 6.

Poichè p3 = 1,

D = A + 23 - B = 5 + 8 - 7 = 6.