[Math] Binary arithmetic with two’s complement

arithmetic

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?

Best Answer

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.

Related Question