1. The digital revolution
   digital: bits of 0s and 1s
   information stored digitally, interface between components is a digital one.
 
   draw an analogue sound system

2. how to encode number in 0s and 1s?

   We've learnt math in decimal notaion
   Decimal ==> base 10

   A (positive) number's decimal representation:
   x = \sum_i a_i * 10^i
  
   103 in decimal means: ...


  Generalize base 10 to other bases
  Base-b representation x = \sum_i a_i * b^i

  12 in base 10 is : 12
  12 in base 2 is: 1100
  12 in base 8 is 14
  12 in base16 is c

  What's number is 1111 1111 ?
  2^7 + 2^6 + 2^5 + 2^4 + ... + 2^1 + 1

  As a computer scientist, you should remember these numbers by heart
  1 2 4 8 16 32 64 128 256 512 1024
  2^10 = kilo
  2^20 = mega
  2^30 = giga
  2^40 = tera
  1 + 2^1 + ... + 2^n = 2^{n+1} - 1 
       
3. how do computers do arithematic?

   CPU has circuitry to compute on numbers of serveral fixed sizes:
   1 byte
   2 bytes
   4 bytes
   8 bytes 

   Byte is the smallest addressable unit 
   1 byte = 8 bits

   Unsigned addition:

     0000 0011
+    0000 0110        
-----------------
     0000 1001


     1000 0000
+    1000 0000
---------------
    10000 0000 (Overflow!)

4. Unsigned Substraction

  illustrate an underflow example

5. Unsigned Multiplication

   8-bit x
   8-bit y
   number of bits required to represent x*y?
   2 * 8 bits
   x: |_______8 bits______________________|
   x: |_______8 bits______________________|
   z: |__8 bits potentially discarded_____|______8 bits_________________|

  More chances for overflow

6.  Negative number representation

  Make most significant bit indicate sign
  0 for non-negative
  1 for negative

  A naive representation:
  represent -x the same as x except with MSB=1

 0000 0001  --> 1
 1000 0001  --> -1


  Why not naive representation?

  Add/substraction/multiplication circuitry has to be different for 
signed and unsigned

  example:
  0000 0001
+ 1000 0000
------------
  0000 0000            


  0000 0001
+ 1000 0000
-------------
  1000 0001


7. 2's complement

   char x = 8;  0000 1000 (first bit is a sign bit)
   char y = -8; 1111 1000 (2's complement)
   -2^7 + 2^6 + 2^5 + ... 

   what's 1111 1111? -1


   x = 3     0000 0011
   y = 6     0000 0110        
   z = x+y   0000 1001

   3         0000 0011
   -3        1111 1101
   3+(-3)    0000 0000 

   3          0000 0011
   -2         1111 1110
   3+(-2)     0000 0001


    67        0100 0011
    67        0100 0011
    67+67     1000 0100
	-122  (overflow!)

    -124           1000 0010
    -124           1000 0010
  (-124)+(-124)	   0000 0100

   Easy way to calculate 2's complement, flip all bits and plus 1
   x + (flip all bits of x) = -1 (1111 1111)
   -x = (flip all bits of x) + 1
   To check your calculation is correct, 8 + (-8) = 0

8. Numerical ranges

  w-bit unsigned number 
  w-bit signed number

  Examples: what's the range of numbers representable by 8 bits? [-2^7,2^7-1]
                                          ...by 32 bits? [-2^31,2^31-1]
 
  8-bit unsigned?
  32-bit unsigned number?

9.  Byte ordering
  Memory is organized (conceptually) as a large array of bytes
  Each byte has an address.
  Our 64-bit machine --> [0,2^63-1]

  CPUs need to load 2,4,8-bytes from memory in its internal state to do arithematic
  Suppose CPU is to load 4 bytes starting at address P as a 32-bit number
  P,  P+1, P+2, P+3
 Question: which byte has the most significant bits?
 Big Endian: Internet transfer's convention
 Little Endian: least significan has lowest address