[Proof] Two's Complement representation is bijective

Blacksmith · #1 $Old$ October 23rd, 2009, 10:22 AM

Hi there!

I need help with a proof that the Two's Complement's representation is unique -> There are no two representations of a number.

The following formula describes the Two's Complement: $v(a_{n-1}a_{n-2}...a_1a_0) = -a_{n-1}*2^{n-1}+\sum_{i=0}^{n-2}a_i*2^i$ ,

where $v(a_{n-1}...a_0)$ is the value of the binary number $a_{n-1}...a_0$ . n is the number of digits. For example:

$v(10_2) = -1*2^{2-1} + \sum_{i=0}^{2-2}a_i*2^i = -1 * 2^1 + 0*2^0=-2$ .
So the $-2$ (decimal) is $10$ (binary; one zero, not ten) in the Two's Complement representation.

I tried proving it with a proof by contradiction, but I didn't get very far.
Any help?

Thanks in advance,

BS

Blacksmith · #2 $Old$ October 24th, 2009, 08:31 AM

No one?

I tried to solve it with a proof by contradiction:

$x=-a_{n-1}*2^{n-1}+\sum_{i=0}^{n-2}a_i*2^i=-a_{m-1}*2^{m-1}+\sum_{i=0}^{m-2}b_i*2^i$

$n \neq m$ or $a \neq b$

So I assumed that there are two possible representations of x. Now I have to show that there is a contradiction.

But I have no idea how to do something like that.

Any help?

BS