Bits and Bytes

By convention:

• 0 is off
• 1 is on

A byte is 8 bits, this is the basic unit of memory in a computer.

• nibble: 4 bits, that's half a byte
• word: 32 or 64 bits. Your system is described by its word size.

Information is bits + context. Everything is stored as bits. The context is HOW they are read.

Numbers

Problem Given collections of objects A and B, tell which has more itmes in it without counting.

Solution Pair them off.

• A could hhave leftovers: A is bigger
• B could have leftovers: B is bigger
• No leftovers: A and B have same size

This "same-sizeness" is the real, abstract notion of number.

The symbol 256 is a reprsentation of a number. Our numbering system is a base system with a base of 10. This is because we have 10 fingers. We parse it as follows.

256 -> 2 units of 100, 5 units of 10, 6 units of 1.

parse(v.t.) to extract meaning from symbols

• 100000000 is a binary representation of the same number
• CCLVI is a Roman Numeral representation of the same number.
• This is the tally-mark representation of the same number:

  IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
  IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
  IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
  IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
  

Base Conversions

The modern way to reprsent numbers is a Base system, like our base 10 system.

Computers don't have fingers. They are big dumb piles of switches. They understand two things: on and off. So computers grok base 2.

Greedy (bigendian) algoritm To count out an integer number of dollars in US currency with as few bills as possible you use this scheme: Use as many of the largest bill as you can. Then move down a denomination and repeat until it's all counted.

We can use this scheme to convert a decimal representation of a number to binary. The "denominatons" are powers of 2.

In this table, we start at the bottom and work upwards.

73
denom  numUsed  whatsLeft
$
1       1           0
2       0
4       0
8       1           1
16      0
32      0
64      1           9
128     0          73

To see the binary representation, read UP: 73 = 0b1001001. This is the bigendian method since we start at the big end and work our way down.

Here is the little endian method. Notice this phenomenon.

365//10 = 36

Integer dividing a number by its base amputates its last digit.

In this algorithm, we keep dividing by 2 and checking for evenness or oddness. The * is a wildcard standing for any sequence of 0s and 1s.

73 is odd  *1
36 is even *01
18 is even *001
9  is odd  *1001
4  is even *01001
2  is even *001001
1 is odd   *1001001
0          1001001

This works for ANY BASE.

321

1    1     0
5    4     1
25   3    21
125  2    71
625  0   321

321 = 23415