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 )

Overflow

• Overflow cannot occur when adding numbers of different signs, so we can ignore the extra borrows and carrys in that case.
   
• Overflow cannot occur when subtracting two numbers with the same sign.
   
• Overflow occurs when you:
  • Add 2 positive numbers and get a negative sum.
  • Add 2 negative numbers and get a positive sum.
  • Subtract a positive number from a negative number and get a positive difference.
  • Subtract a negative number from a positive number and get a negative difference.
  
  
• Ignoring overflow:
  • In MIPS, addu, subu, and addiu all ignore overflow (unsigned integer calculations); the "sign bit" gives an extra digit's worth of positive numbers we can express.
  • C always ignores overflow; catching it is the programmer's responsibility.

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