World's most popular travel blog for travel bloggers.

1's complement addition of outer carry to the result

, , No Comments
Problem Detail: 

Let's take for example this addition: 3 + (-1).

  • 1 in binary is 001, and to obtain it's 1's complement counterpart we flip the bits. So it is: 110.

  • 3 in binary is 011.

011 + 110 = 1001

That first 1 which is in bold has to be added to the number formed by the last 3 bits as follows:

001 + 1 = 010 (2 in decimal).

Why do we do the last step, adding that outer carry? Which is the logic behind?

Asked By : Iulian Barbu
Answered By : André Souza Lemos

Computers represent numbers (and other things) imperfectly, sometimes for convenience, sometimes because there is no alternative. Complement arithmetic is easier to implement than sign-magnitude, but has a few quirks.

We just live with them, there's nothing special here.

In two's complement, the "extra one" is also there, but it is added during the change of sign, and because there is only one representation for zero, the system is a bit more elegant.

Try to picture a base complemented number as representing what's missing in the number to reach $b^k$ ($b$ is the base, $k$ is the number of significant digits). The apparent "extra one" is due to the fact that what is counted here are the steps to reach the implicit "zero" in $b^k$.

For instance, in ten's complement, with $k=3$:

$-5 = 995=10^3\color{red}{-5}$

In nine's complement, $999$ is zero, so the extra one is not necessary in this case. It becomes necessary, though, when the operation causes overflow due to change of sign:

$-5 = 994$

$-5+6 = 994+006 =\color{red}{1}000\color{blue}{+1} = 001$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/64742

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback