Results 1 to 2 of 2

Math Help - [Proof] Two's Complement representation is bijective

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    2

    Question [Proof] Two's Complement representation is bijective

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2009
    Posts
    2

    Question

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Bijective proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 27th 2010, 11:11 PM
  2. Bijective Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 30th 2010, 09:49 PM
  3. bijective proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 12th 2009, 01:09 PM
  4. Bijective Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 2nd 2009, 12:30 PM
  5. Complement Representation using Bit Strings
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 20th 2008, 11:30 AM

Search Tags


/mathhelpforum @mathhelpforum