15-213 recitation Mon 13 Sep 2004
Section D  1:30p - 2:20p
Minglong Shao

* Preliminaries
  - my name: Minglong Shao
  - contact info
	Wean 1315, Office hours: Thu 5-6pm, shaoml+213@cs.cmu.edu, 412-268-5941
  - starting (and ending) on time
  - feel free to ask questions
	- Stop by at my office during the office hour
	- Call me or send me email for appointments
	- Bring them to the recitation
  - feel free to send me comments, suggestions, etc.
    - propose topics you are interested in
  - login to FISH machines
     - Anyone has problems logging in?
     - Please check and make sure you can work.

* Quick tour of Autolab
  - create your lab account TODAY if you haven't done it
  - download lab materials, submit your solutions, check class status
	view your handin files and reports, check messages board

* Lesson for the Day: It's All Bits
  - purpose of this lab: to get you thinking in terms of bits
  - regardless of the values stored or their interpretation, at the lowest
    level, everything is just a bunch of bits.
  - we use 2's complement to represent integers

* Tricks for bit manipulation:
  - Ints with special properties
  - Masking
  - Shifting
  - Walking around if-then-else structure
  - Doing things in parallel
    MENTION that: important tricks for Lab 1 

* Ints with Special properties:
  - 0 : 0x00000000
      Twos complement is the same as itself
  - TMin : 0x80000000
      - Suppose we wanted to calculate TMin using restricted operators
        as in Lab 1
        Answer: (0x1 << 31)
      - Twos complement is the same as itself
  - TMax : 0x7FFFFFFF
      All ones after the 0 sign bit
  - negation
	-x = ~x + 1
  - -1 : 0xFFFFFFFF
      - Doing Negation 
           -x is (~x + 1)
      - so -1 is (~0x1 + 1)
      - Easier way: Obtained by Complementing 0 bit-wise
  - (1 << n) is 2 raised to n
  - x ^ 0xFFFFFFFF is same as ~x
  - x ^ 0 is same as x
  - Multiplying:
    + x*2^n: x << n
    + x*5: (x << 2) + 1 

* Some example masks
    1. Selecting the least significant byte: 0xFF
    2. Selecting bits 16 to 23: 0xFF << 16
    3. All ones: ~0
    4. Top n bits are 1s, rest 0s
         ~0 << (32-n)
    5. Even bits: i.e. 0th, 2nd, 4th, ....
         0x55 | (0x55 << 8) | (0x55 << 16) | (0x55 << 24)

* Masking & Shifting
  - logical shift vs. arithmetic shift

    reverseBytes
  - problem: take a four byte word abcd and output dcba

             abcd  is 0x61626364
      we want
             dcba     0x64636261
 
  - ASK: how to solve this?
  - solution: dismantle the word into separate bytes, then reassemble

    int reverseBytes(int x) {
    	int fourth = x & 0xFF;
    	int third = (x >> 8) & 0xFF; 
    	int second = (x >> 16) & 0xFF; 
    	int first = (x >> 24) & 0xFF; 

    	return (fourth << 24) | (third << 16) | (second << 8) | first;
    } 

* Walking around if-then-else structure
	abs(int x)
  - problem: return the absolute value of x
    in C:
	if ( x >= 0 ) return x
	else return -x;

	Or
	return x >= 0 ? x:-x

  - ASK: how to solve this?
  - solution: rewrite simple if-then-else with (cond1 & exp1) | (cond2 & exp2)

    if (cond1)
		exp1;
	else if (cond2)
		exp2;

	rewrite as (cond1 & exp1) | (cond2 & exp2)
	be careful with the value of cond. It should have the same length of the
	exp.

	int abs(int x){
		int sign = x >> 31;
		int neg_x = (~x) + 1;
		
		return ((~sign) & x)) | (sign & neg_x);
	}

	int abs(int x){
		int sign = x >> 31;

		return (x ^ sign) + (sign & 1);
	}

* Doing things in parallel bitCount(unsigned int n)
  - problem: count the # of 1's in unsigned integer n
  - ASK: how to solve this? 
  - solution:
        a_31 a_30 a_29 a_28 ... a_3 a_2 a_1 a_0
         |____|    |____|        |___|   |___|
            |_________|             |_______|
	       ...                    ...
                |______________________|
                           |
                       # of 1's
		      
    split n into pairs of bits a_i + a_i-1 = number of 1's
    then sum up these counts step by step
	
	unsigned int bitCount(unsigned int n)
	{
		unsigned int c;

		c = n;
		c = ((c >> 1) & 0x55555555) + (c & 0x55555555);
		c = ((c >> 2) & 0x33333333) + (c & 0x33333333);
		c = ((c >> 4) & 0x0F0F0F0F) + (c & 0x0F0F0F0F);
		c = ((c >> 8) & 0x00FF00FF) + (c & 0x00FF00FF);
		c = ((c >> 16) & 0x0000FFFF) + (c & 0x0000FFFF);

		return c;
	}

	unsigned int bitCount(unsigned int n)
	{
		unsigned int c;

		c = n;
		c = ((c >> 1) & 0x55555555) + (c & 0x55555555);
		c = ((c >> 2) & 0x33333333) + (c & 0x33333333);
		c = ((c >> 4) & 0x0F0F0F0F) + (c & 0x0F0F0F0F);
		c = c % 255; // why?
		return c;
	}

  - more interesting solutions:
	http://www-db.stanford.edu/~manku/bitcount/bitcount.html

  - explore parallelism in bitParity(int x) 

* Overflow
  - Integer sum: If the sign of the result differs from the expected sign
  - Floating point sum: Explicitly represented as "infinity"

* Misc
  - dividing by powers of 2
	quotient of x/pwr2k = ( x<0 ? (x + (1<<k) - 1) : x ) >> k (CS:APP P78)
  - a useful link on bit operations
	http://graphics.stanford.edu/~seander/bithacks.html

* Ask questions
  - provide us with as much as possible information
	command(s) you execute
	error messages returned
	running environment (e.g. Andrew machine or FISH machine)