Binary arithmetic with two's complement 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?
 A: 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:


*

*$2c(0)=0$, and

*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.
A: 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.
A: 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.
