Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Here is a very good explanation of why the method for subtraction in 2's complement works: cs.cornell.edu/~tomf/notes/cps104/twoscomp.html#whyworks. –  anonymous Jul 30 '12 at 21:48
    
@anonymous: That only explains why 2's complement of a number is same as inverting the bits and adding one. –  Quixotic Jul 31 '12 at 0:22
    
But, at least, it offers insight into why inverting and adding one works for finding the negative of a number (since this is essentially the part of the algorithm that distinguishes it from addition of positive numbers, I assumed this is what you wanted to know, but I may be misinterpreting what you are asking, so correct me if I'm wrong). Then, calculating (a - b) is the same as calculating the sum of a and the negative of b. –  anonymous Jul 31 '12 at 16:13

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks.. but I think the minuend should be $2^{k+1}-1$ in case of $1$'s complement and from the steps it seems that this answer wanted to show $(y-x)$ (since $x$ is complemented) but somehow end up computing $(x-y)$?! Still it doesn't explain the adding and neglecting of carry in $1$'s and $2$'s complement respectively. –  Quixotic Jul 30 '12 at 15:03

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.