Java Bitwise and Shift Operators
---------------------------------

- Computers work in binary - 1s and 0s. 
- Java uses binary internally to represent
  integral numeric types: byte, short, int
  and long:

  Type    Number of bits
  ----    --------------
  byte       8
  short     16
  int       32
  long      64

- Java also uses binary internally to
  represent chars (16 bits) and 
  floating-point types, but the format
  of these is more complex

- Java provides three bitwise operators
  that work on integral types:

-AND (&). When you AND bits, the result is
    one only if both inputs are one:
    

  &    0     1
    + ---   ---
  0 |  0     0
  1 |  0     1

  So if we AND two bytes:

     01001100
 &   11001100
    ---------
     01001100

- OR (|). When you OR bits, the result
    is one if either input is one:

  |    0     1
    + ---   ---
  0 |  0     1
  1 |  1     1

  So if we OR the same two bytes:

     01001100
 |   11001100
    ---------
     11001100

- XOR (^). When you XOR bits, the result
    is one if the inputs are different:

  ^    0     1
    + ---   ---
  0 |  0     1
  1 |  1     0

  So if we XOR the same two bytes:

     01001100
 ^   11001100
    ---------
     10000000

- What good are these crazy operators?
  AND is useful for ensuring that bits
  are ZERO in the output. For example,
  given a byte, if we want to be sure
  the bottom four bits are all zero,
  we use a mask with AND:

     01001100   -- input byte
   & 11110000   -- mask
     --------
     01000000   -- bottom four bits off

  That technique is useful for working
  with devices and for cases where you want
  to pack two four-bit values into a byte
  to save space - in four bits, we can represent
  values 0-15. So if we had to store millions 
  of business codes of some sort that were in that
  range, we could cut storage space in half as
  opposed to using a complete byte for each code
  value.

  Similarly, we can use OR to ensure that bits
  are ONE in the output:

     01001100   -- input byte
   | 00001111   -- mask
     --------
     01001111   -- bottom four bits on

  Finally, XOR has two interesting uses. One
  is to flip individual bits in a byte, a 
  technique thats useful for device drivers:

     01001100   -- input byte
   ^ 00001000   -- mask
     --------
     01000100   -- one bit flipped

  The other interesting application of XOR is
  that if you repeat it, you can recover the
  initial value!

     01001100   -- input byte
   ^ 00001000   -- mask
     --------
     01000100   -- one bit flipped

     01000100   -- result of XOR
   ^ 00001000   -- same mask
     --------
     01001100   -- original input byte

  That's useful for certain kinds of animations -
  you can draw a figure in XOR mode and then
  draw it again to restore the previous background.
  If you then draw in XOR mode at a different position,
  the figure appears to move.

- Java provides three shift operators that 
  move the bits around within integral types:

- LEFT-SHIFT (<<). This operator moves bits to the
  left, shifting zero(s) on the right. So in a byte, if
  we shift left once:

     01001100   -- input byte
  << 1 
     --------
     10011000   result
  
  If we shift left twice:

     01001100   -- input byte
  << 2 
     --------
     00110000   result

  Note that in the latter case, we lose the topmost
  one value - if we cast the byte into a short before
   shifting, we wouldn't lose it.

- ARITHMETIC RIGHT-SHIFT (>>). This operator moves bits
  to the right. It shifts in either ones or zeros matching
  the previous value of the topmost bit - that bit is
  where Java stores the numbers sign (positive or 
  negative). So we say this operator maintains the original
  values sign.

     01001100   -- input byte
  >> 1 
     --------
     00100110   result

   Another example:

     11000001   -- input byte
  >> 1 
     --------
     11100000   result

- NON-ARITHMETIC RIGHT SHIFT (>>>). This operator moves
  bits to the right, always shifting in zero(s) on the
  left. Thus the result of this operator is always 
  positive (the topmost bit will be zero). So we use this
  if we don't care about the inputs sign (e.g., we might
  just be working with positive values).

     01001100   -- input byte
  >>> 1 
     --------
     00100110   result

   Another example:

     11000001   -- input byte
  >>> 1 
     --------
     01100000   result

  These shift operators are useful to do quick and
  dirty multiplication/division by powers of two or
  to move bits around within integral types for
  further manipulation (see exercise below).

Exercise
--------

Suppose our business has 16 employee-type codes:

  0 - peon
  1 - serf
  2 - trader
  . . .
  15 - emperor

Write two Java methods:

 One that accepts two bytes containing employee
 codes. This method should return a byte with 
 the two codes packed into it.

 One that accepts a byte containing packed codes
 and returns an array with two bytes containing
 the individual codes.

 Test using code like:

	byte t1 = 3;	// 0000 0011
	byte t2 = 4;    // 0000 0100
		
	byte b1 = pack(t1, t2);		
	byte[] arr = unpack(b1);		
	System.out.printf("B1: %d, B2: %d\n", arr[0], arr[1]);
	System.out.println();
		
	t1 = 12;      	// 0000 1100
	t2 = 2;		// 0000 0010
		
	b1 = pack(t1, t2);		// 1100 0010
	arr = unpack(b1);		
	System.out.printf("B1: %d, B2: %d\n", arr[0], arr[1]);

 Hint: Java treats the results of bitwise and
 shifts as int, and has a nasty habit of using
 sign-extension on cast from byte to int. So part
 of the trick here is to do all of the manipulation
 using ints and then cast result to byte.