Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Arithmetic does fail in the case of overflow... You need to be more specific. – Brandon Carter Aug 23 '11 at 0:47
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
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|cite|improve this answer

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|cite|improve this answer

Note that the 2's complement of the most negative number in that number system is itself (e.g. the 2's complement of -128 is -128 itself) etc.

share|cite|improve this answer

Your Answer


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.