Number Representation


Two's Complement: More Details

Sign extension

Note that in two's complement, non-negative numbers have an implicit infinite number of leading 0's, and negative numbers have an implicit infinite number of leading 1's.

For example,

            0 = 00000000 = 00000000 00000000 ( = 010 )
        00010 = 00000010 = 00000000 00000010 ( = 210 )
        11110 = 11111110 = 11111111 11111110 ( = -210 )
        01101 = 00001101 = 00000000 00001101 ( = 1310 )
        10011 = 11110011 = 11111111 11110011 ( = -1310 )

Proving the relationship between One's Complement and Two's Complement

Prove: -x = x + 1

[In our examples, we will assume that integers are 8 bits long, but the proof applies to binary integers of any length (e.g., 16 bits, 32 bits, 64 bits).]

Let x represent the one's complement of x.

Note that in two's complement, the definition of -1 is 11111111 (the result of subtracting 1 from 0).

Note that x + x = 11111111 = -1. This is true because for every 0 in x, the corresponding bit in x is 1, yielding a sum bit of 1, and for every 1 in x, the corresponding bit in x is 0, again yielding a sum bit of 1. For example:

           00001101   13
         + 11110010   one's complement of 13
         ----------
           11111111

Since

   x + x = -1
we can add one to both sides and get
   x + x + 1 = 0

Now, by definition,

   x + (-x) = 0
so, substituting x + (-x) for 0 in our previous result, we have
   x + x + 1 = x + (-x)
or
   x + 1 = (-x)
or
   (-x) = x + 1

Overflow


Alyce Brady, Kalamazoo College