A short introduction to integer representation:
===============================================

- In the coming lecture, we'll talk more about floating point numbers, 
  and roundoff error. Let's talk now about representing integers.

- To represent unsigned integers, we simply store them in binary form.
  So if we have n bits available, integers are represented as strings
  of binary digits:

                           b    b    ... b  b
                            n-1  n-2      1  0

  where each b_i is either 0 or 1 and the integer represented is equal
  to 2^{n-1} b_{n-1} + 2^{n-2} n_{n-2} + ... + 2 b_1 + b_0 (b_0 is the
  "least significant bit" and b_{n-1} is the "most significant bit").
  For example, with n = 6, the bit string (100110) represents the
  integer 2^5 + 2^2 + 2^1 = 38.

- If we have n bits, we can represent integers from (0...0) = 0 to
  (1...1) = 2^n-1.

- How do we represent signed integers?  Well, we could simply use the
  first bit b_{n-1} to store the sign (0 = +ve, 1 = -ve). This
  "shifts" the range of values we can store, for example, with n = 6:

     (000000) =   0      
     (000001) =   1      The only problem with this is that it's
          ...            wasteful: we are using two different bit
     (011110) =  30      strings to represent the same number since
     (011111) =  31      (100000) = -0 = 0 = (000000).
     (100000) = - 0      
     (100001) = - 1      Ideally, we would like to be able to still
          ...            represent 2^n-1 *distinct* values but right
     (111110) = -30      now, we're only representing 2^n-2.
     (111111) = -31      

- Another common technique is to use what's called "one's
  complement": if we let b' = 1-b, then b' is b's "complement"
  (every bit has been flipped from 0 to 1 and from 1 to 0). In
  one's complement, an integer -n is complemented to get n, and
  only integers whose first bit is 1 represent negative values.
  For example, (100110)' = (011001) = 25, so (100110) = -25.
  (More generally, if b_{n-1} = 1, then ( b_{n-1} ... b_1 b_0 )
  represents the integer n = - ( b'_{n-2} ... b'_1 b'_0 ). For
  example, for n = 6:

      (000000) =   0      Unfortunately, we still have the same
      (000001) =   1      problem: we are using two different bit
           ...            strings to represent the same number
      (011110) =  30      since (111111) = -0 = 0 = (000000).
      (011111) =  31      
      (100000) = -31      Ideally, we would like to be able to
      (100001) = -30      still represent 2^n-1 *distinct* values,
           ...            but right now we're only representing
      (111110) = - 1      2^n-2.  But there's now a simple way
      (111111) = - 0      to solve the problem!

- Luckily, we can use the idea of one's complement and modify it
  just a little bit to get what is called "two's complement": to
  represent -n, we complement +n and ADD 1. For example, to
  represent -25, we take 25 = (011001), complement it to get
  (100110) and add 1 to get (100111). In the other direction,
  given a bit string that starts with 1, we first subtract 1, then
  take the complement to get a value n, and the original bit
  string represents -n. For example, starting with (111000), we
  subtract 1 to get (110111) and take the complement to get
  (001000) = 8, so (111000) = -8. For n = 6, this gives us the
  following table of values:

      (000000) =   0      You can see that this is just a simple 
      (000001) =   1      "shift" of the second half of the table
           ...            for one's complement, so that we're not
      (011110) =  30      wasting the last value. This introduces
      (011111) =  31      some assymetry in the table, but at    
      (100000) = -32      least now we *do* represent 2^n-1      
      (100001) = -31      distinct values.                       
           ...            
      (111110) = - 2      Note also the special case of (100000):
      (111111) = - 1      we get back exactly (100000)!

- Why is this called "two's complement"?  Well, it turns out that
  with this representation of negative integers, when we want to
  compute n - m, we simply have to compute n + (-m) (i.e., we
  simply *add* the two bit strings representing n and -m)! For
  example, if we want to compute 5 - 13:

       (000101)      What if there is a carry-bit past the last
     + (110011)      position? Simply ignore it! This makes
       --------      most computation much simpler, as we only
       (111000)      need to write adders.