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.

By intuition I can see that the 2's complement will be the negative of a number but I want a more rigorous proof to convince myself that no arithmetic will ever fail.

EDIT More clarification:

Consider the domain [0,8)

decimal | 2's comp | integer
   0    |    8     |     0
   1    |    7     |     1
   2    |    6     |     2
   3    |    5     |     3
   4    |    4     |    -4
   5    |    3     |    -3
   6    |    2     |    -2
   7    |    1     |    -1

it seems that integer column picks its -ve numbers from the lower half of 2's complement column and the +ve numbers from the upper half of decimal column.

What magic is going on here?

share|improve this question
1  
Arithmetic does fail in the case of overflow... You need to be more specific. –  Brandon Carter Aug 23 '11 at 0:47
1  
2 comments after the update: 1) Note that in [0,8) we have that $8=0$ (we ignore the 1 that gets carried outside of the 3 bits we are observing) 2) The negative numbers have the leading bit set to 1, and the positive numbers have leading bit set to 0. This is why the positives and negatives group together like they do. –  Brandon Carter Aug 23 '11 at 1:23
add comment

2 Answers 2

up vote 4 down vote accepted

First off, observe that the group $G=(\{-4, -3, ..., 0, 1, ..., 3\}, +)$ is isomorphic to $\mathbb{Z}_{8}$.

The bijection $f:G \to \mathbb{Z}_{8}$ is exactly the two's complement. Why? Because:

  1. $2c(0)=0$, and
  2. For all $a$, $a^{\prime}$, if $2c(a)=a^{\prime}$, then $2c(a+1)=a^{\prime}-1$.

And that's why two's complement addition works. A similar argument can be made for multiplication, and any number of bits. Hope I didn't make things more confusing, but this is how I would go about rigorously proving the correctness of two's complement arithmetic.

share|improve this answer
add comment

One way to think of n-bit 2's complement is that the lower $n-1$ bits represent a positive number and the highest bit represents $-2^{-n+1}$. Then to prove that arithmetic comes out right assuming there is no overflow, you just consider the cases. If you add positive numbers $m$ and $p$, you get $m+p$ as long as $m+p \lt 2^{-n+1}$. If you add a positive $m$ to a negative $p$ that is smaller in absolute value, there will be a carry that wipes out the negative sign bit in $p$ and so on.

share|improve this answer
add comment

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.