CSC152 2005F, Class 11: Representing Numbers

Admin:
* Donuts!
* Homework due tomorrow.  Example.  Questions?

Overview:
* Review of key points from lab
* Description of underlying representation of numbers

/Questions on Homework/

* How do I check permissions?
	ls -l filename
	ls -ld directoryname
* How do I change permissions on lots of files?
	chmod a+x *
* How long should it be?
	Sam, a relatively concise programmer, has 122 lines
	Jacob has 160
	Yes, your code will be repetitious. Deal.
* How do I chop up the line?
	Visit me in office hours or Eryn at 7pm tonight (or both) or the 152 tutor from 9 to 10 pm tonight.

/Notes on the Numbers Lab/

* Basics of arithmetic in Java.
	If a and b are ints, add them with a + b (gives int)
	If a and b are Integers, add them with a + b (gives int)
		Better to use a.intValue() + b.intValue()
	If a and b are BigIntegers, add them with 
		a.intValue() + b.intValue() (gives int) // NO!  Loses information
		a.add(b) (gives BigInteger)
* Use the documentation!
* Sometimes the unexpected happens.
  * E.g., shorts convert to integers when you add them
  * Morals:
    * Don't play near the boundaries
    * Don't anticipate effects for "undefined" operations
  * Evidence that programmers often end up overflowing numeric types
  * When your number gets too large, it becomes negative
* Numbers are more complicated than they should be
* Converting numbers from one type to another is somewhat painful
  To convert 2 to a double
     (new Integer(2)).doubleValue()
   or
     new Double(2).doubleValue();
   or
     (double) 2
* New note: "(TYPE) value" means "convert value to TYPE"


Why adding to large numbers creates negative numbers

* Whenever you represent a number, you need to choose a way to interpret a series of bits (0's and 1's).
* Traditional for positive integers as sequences of bits
  Rightmost bit is 1's
  Next bit is 2's
  Next bit is 4's 

  16 8  4  2  1
  1  0  0  1  0
* Problem: How do you represent negative numbers?
* Observation: If you make the leftmost bit be "sign", you get some odd things
  0 0 1 0 1 : 5 (sign is 0)
  1 0 1 0 1 : -5 (sign is 1)
  0 0 0 0 0 : +0
  1 0 0 0 0 : -0
* (Side question: How do you represent bigger numbers?  More bits.)
  * That's why different "types" in Java have different ranges
* For positive numbers, addition is straightforward (and progresses like addition for decimal numbers)
     1 1 1
   0 0 1 0 1 : 5
   0 0 0 1 1 : 3
   --------------
     1 0 0 0 : 8
* Goal of representation design: Keep addition easy
* 2's complement representation
  * Positive numbers begin with a 0 and are otherwise "normal"
  * To negate a number, flip all the bits and add 1
    Negative five:
      flip the bits: 1 1 0 1 0
      add 1:         1 1 0 1 1: -5
  * Note: negative numbers begin with a 1
      To figure out 1 1 1 0 0: -?
      Flip all the bits: 0 0 0 1 1
      Add 1: 0 0 1 0 0: 4 (so the number was -4)
   * Try it with -5
     Flip: 0 0 1 0 0
     Add 1: 0 0 1 0 1
   * Try it with 4
     Flip: 1 1 0 1 1
     Add 1: 1 1 1 0 0
* Does it work to add negative and positive numbers?
  14 + -2
  14: 0 1 1 1 0
  -2: 1 1 1 1 0
     ----------
      0 1 1 0 0

  -5 + 4
  -5: 1 1 0 1 1
  4:  0 0 1 0 0
     -----------
      1 1 1 1 1
* Java uses 2's complement
  Byte.MAX_VALUE

  0 1 1 1 1 1 1 1 = 2^7 - 1 = 127
+ 0 0 0 0 0 0 0 1
  ---------------
  1 0 0 0 0 0 0 0 = -128
It's negative
  Flip: 0 1 1 1 1 1 1 1
  Add 1: 1 0 0 0 0 0 0 0