CSC161 2010F, Class 12: Binary Representation and Bitwise Operators

Overview:
* Why study underlying representations?
* Basics of binary.
* Unsigned integers.
* Signed integers.
* Some of C's bitwise operations.

Admin:
* EC for attending tomorrow's Thursday extra: 
  Dr. Davis on Participatory Design.
* EC for attending tomorrow's Scholars' Convocation on Iran.
* When is the first exam?
  * Distributed next Wednesday
  * Due the following Wednesday
* Silly note: C is still insanely popular.  See langpop.com.
* Reading for Friday: IEEE Floating-Point Representation of Real Numbers.
  + Sam added links for readings to the Web site
* Although I have a lab listed for today, we are unlikely to do that lab.
* Are there questions on Assignment 3?

Questions on HW 3
* In what order should we approach topics?  How do we divide things up?
  + Think about what would have served you best
* How do I use code from math.h?
  + See Examples/HW3/
* Can you show us some examples of atoi?
  * Done
* Do we have to include things we learned only yesterday, like argc and argv?
  * No
* What do you mean about "our implementation of C"
  * I mean things like "our implementation of C uses 32 bit ints, but not all do."
* How should I refer to "our implmeentation of C"?  "The implementation of C that exists in the MathLAN as of 2010.09.15, aka 32 bit GCC."

Internal Representation: Why Learn It?
* Better understand the inner workings of a computer
* We run across it regularly (e.g., K&R assume that you understand it)
* C programmers like to write code that takes advantage of underlying
  representation
* "Street Cred" - If you can't look at binary, you're street crud.  Lack
  of knowledge loses you respect.
* Some interesting design challenges/puzzles
* It's beautiful, or at least very nice.  

Binary
* Behind the scenes on most computers, we have a basic representation of
  values as one of two states
  * Electronically: On or off
  * Numerically: 1 or 0
  * Logically: True or False 
  * Bit - binary digit
* We combine bits into groups
  * Bytes - smallest unit that the CPU computes with
    8 bits
  * Words - typically the number of bits necessary for an address
    32 bits
    64 bits
* What do the bits mean?  It's up to the context and the designer!
  * They could be an integer or a character or a floating point number or
    some flags or ...
  * Even after we know that they're an integer, the designer has made some
    choices on how to represent integers
* Things we should know about
  * Unsigned integers
  * Signed integers
  * Floating point numbers / real numbers
  * Characters
  * ...

Unsigned Integers

* Standard base-two notation
* Columnns are organized from left to right
* Rightmost column 1's column
* Next-to-rightmost is 2's column
* Next is 4's column

Columns:8421
Number: 1001

Largest number: 15
How do I represent 127 in 8 bits?

01111111

Signed Integers
* Need to be able to say "Is this negative or is this positive?"
* Need to be able to say "What is the value of this number?"

Natural way to represent sign: Leftmost bit
* A leftmost 1 means "negative"
* A leftmost 0 means "positive"

Next question: How do we interpret the remaining bits (for positive
numbers, for negative numbers, ...)

* Obvious answer: Just like we do in unsigned numbers
  Signed Magnitude
* Silly answer 1: Flip all the bits
  One's complement
* Outside the box answer: Since we know how to represent positive numbers,
  just convert to positive numbers!
  * For eight bits: Convert the range -128 to 127 to the range 0 to 255
    by adding 128
  * Generally: For N bits, add 2^(N-1)
  Excess 2 to the N-1
* Operational one: To negate a number, flip all the bits and add 1
  Two's complement

How would you decide which one to use?  You would like at a variety of
issues:
* How easy is it for me to build the add circuitry?  
  * And how big is it?
  * And how fast is it?
* How easy is it for me to build the negate circuitry?
  * And how big is it?
  * And how fast is it?
* Note: subtract = negate 2nd argument + add
* Maybe other operations, too