3
$\begingroup$

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?

  • 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.2011-08-23

3 Answers 3

4

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.

  • 0
    Can anyone explain what did he mean by $c(a)$ ?2018-09-12
3

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.

1

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.