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),