Why does the $2$'s and $1$'s complement subtraction works?

Question

The algorithm for $2$'s complement and $1$'s complement subtraction is tad simple:

$1.$ Find the $1$'s or $2$'s complement of the subtrahend.

$2.$ Add it with minuend.

$3.$ If there is no carry then then the answer is in it's complement form we have take the $1$'s or $2$'s complement of the result and assign a negative sign to the final answer.

$4.$ If there is a carry then add it to the result in case of $1$'s complement or neglect in case of $2$'s complement.

This is what I was taught in undergraduate, but I never understood why this method work. More generally why does the radix complement or the diminished radix complement subtraction works? I am more interested in understanding the mathematical reasoning behind this algorithm.

Answer 1

To give you the intuition I will focus on non-negative numbers $x,y\ge 0$ and that the numbers are $k$-bit integers.

1-complenet

To get the 1-complement from a number $x$ you flip every bit in $x$s binary representation $\text{bin}(x)$, 1 $\Leftrightarrow$ 0. You can do the same, by subtracting $x$ from the binary number that contains only 1s and is as long as $\text{bin}(x)$. For example,

  111111
 -010111
 -------
  101000

This works for every single bit, and there are no carries, so it works for the whole binary representation.

Thus we can describe the 1-complement of $x$ by $c_1(x):=(2^{k+1}-1)-x$, where $k$ is the number of bits we have per number. By definition of the 1-complement we have $c_1(c_1(x))=x$.

Assume that $x>y$ (rule 4), hence when subtracting, we will have an overflow. Thus we will add $+1$ to the result, which yields $$ x+c_1(y)+1=x+(2^{k+1}-1)-y+1=(2^{k+1})+(x-y),$$ since we consider only the first $k$ bits, the 1 representing $2^{k+1}$ will vanish, and we get $x-y$.

Assume now that $x\ge y$ (rule 3). Then there is no overflow and $$ c_1(x+c_1(y))=c_1 (x+(2^{k+1}-1)-y)=c_1(c_1(y-x))=y-x=|x-y|.$$

2-complement

To get the 2-complement of an number $x$ we flip the bits, starting after the right most 1. This can be interpreted as subtracting $x$ from $2^{k+1}$. Again we look at an example

  1000000
 -0010100
 --------
   101100

Until the first 1 we don't have carries, so the bits are just taken from $x$, after the first 1, we have always a carry, and hence the bits get flipped.

Similarly to the 1-complement let $c_2(x):=2^{k+1}-x$, and again $c_2(c_2(x))=x$.

Assume that $x>y$ (rule 4), this gives $$ x+c_2(y)=2^{k+1}-y+x=2^{k+1}+(x-y).$$ Again, the $2^{k+1}$ vanishes since we consider only the first $k$ bits.

Assume that $x<y$ (rule 3), then $$ c_2(x+c_2(y))=c_2 (x+2^{k+1}-y)=c_2(c_2(y-x))=y-x=|x-y|.$$

Both concepts can be extended (on a very natural way) to work with negative numbers.

Answer 2

We consider $k$-bit integers with an extra $k+1$ bit, that is associated with the sign. If the "sign-bit" is 0 then we treat this number as usual as a positive number in binary representation. Otherwise this number is negative (details follow).

Let us start with the 2-complement. To compute the 2-complement of an number $x$ we flip the bits, starting after the right most 1. Here is an example:

 0010100 -> 1101100

We define for every positive number $a$, the inverse element $-a$ as the 2-complement of $a$. When adding two numbers, we will forget the overflow bit (after the sign bit), if an overflow occurs. This addition with the set of defined positive and negative numbers forms a finite Abelian group. Notice that we have only one zero, which is 00000000. The representation 10000000 does not encode a number. To check the group properties, observe that

• $a + (-a) = 0$,
• $a+0=a$,
• $-(-a)=a$,
• $(a+b)=(b+a)$,
• $(a+b)+c= a+ (b+c)$.

As a consequence, we can compute with the 2-complement as with integers. To subtract $a$ from $b$ we compute $a+(-b)$. If we want to restore the absolute value of a negative number we have to take its 2-complement (this explains step 3 in the question's algorithm).

Now the 1-complement. This one is more tricky, because we have two distinct zeros (000000 and 111111). I think it is easiest to consider the 1-complement of $a$ as its 2-complement minus 1. Then we can first reduce the 1-complement to the 2-complement and then argue over the 2-complements.