Then, how works the classical pencil and paper
method to compute the difference between two numbers:
at each step, we are going to compute two bits,
a difference bit and a borrow,
an output borrow bit. Actually, the real value
of the difference can be equal to
1, 0, -1 or -2. Then,
we define the borrow, an output borrow,
and a bit d of the difference. If the
result, the real result, is 1 no problem: there is no borrow, and d =1.
If the result is 0, the same: dout = 0
and d = 0. Then, if the result is
negative, first case: the result is -1; then you
could write or say that -1 = -2 + 1.
So, we will choose a bit of the difference equals 1,
but then transmit the borrow to the next step,
with a weight equal to the present weight multiplied by 2,
so that in this case the borrow
- the output borrow - will be equal to 1. You must think
that this borrow actually has a negative weight.
This is 1 and this is -1 with the weight equal to 2.
It's the same as -2.
In the same way, in the case where the real result is -2, we will say that -2
is -2 + 0. So, here the bit
of the difference is 0, and the borrow is equal
to 1, actually it is a negative weight.
Observe now that d is equal to the real
difference computed modulo 2,
because when the real result is odd,
the corresponding bit is 1 and when the
real result is even, the corresponding
bit is 0. And the output borrow
bit is equal to 0, when the real
result is non-negative, and equal to 1 when the real result
is negative. Another comment: the value of
x - y - bin modulo 2 is exactly
the same as the value of x + y + bin modulo 2,
because modulo 2, -1 is the same as 1.
Both numbers are
odd numbers. Let us see an example:
First we compute 12 (decimal 12) minus 9; then
we compute in a step by step way: 0 minus 1 is equal
to -1. Then the difference bit is 1
and the borrow bit is also 1;
0 minus 0 minus 1 once again is equal to minus 1.
Then, here the difference bit is 1 and the borrow bit
is 1, with a negative weight;
next step: 1 - 1 = 0; next step: 1 - 1 = 0,
so that the result is this one (in decimal 3).
Now, let us compute, 9 minus 12: 1 - 0 = 1;
0 - 0 = 0; 0 - 1 is -1; then
here, the difference bit is 1 and there
is a borrow to the next step; 1 - 1 - 1 = -1;
once again, difference bit
equal to 1 and borrow equal to -1, so that
the result is this one, but now the first 1
has a negative weight, and this number
is equal to minus 16 plus 8
plus 4 plus 1 and
this is minus 3. This type of
representation is called
2's complement representation
of the negative number.
This is the algorithm: it's an iteration (a loop)
where at each step, we compute a difference bit,
the modulo 2 sum of the three incoming bits,
two bits of the operands and one borrow input,
and we compute the sign of the difference
x(i) minus y(i) minus b(i). Here
is the algorithm that we can modify. We can
replace this modular 2 sum by the
exclusive or sum of x(i), y(i) and b(i),