Introductions

• Will Clardy
• Software Engineer @ Leica Biosystems
• I love computers & programming languages

Housekeeping

• Bias
• Questions

Roadmap

• Unit 0: The Computer
• Unit 1: Language
• Unit 2: Data Structures
• Unit 3: Recursion

Themes

• Abstraction
• Simplicity
• Composition

Meet the Bit

• Binary Digit
• 0 | 1
• off | on
• no | yes

Meet the Transistor

• Bistable logic device
• Used in digital circuits as an off/on switch
• First theorized by J. E. Lilienfeld (1925)
• First built by William Shockley et al. (AT&T Bell Labs - 1947)
• MOSFET: Mohamed Atalla & Dawon Kahng (AT&T Bell Labs - 1959)

Meet the Family

• byte: 0000 0000
• nybble: 0000

Representing Unsigned Integers

• hexadecimal = octal = binary = decimal

0 = 00 = 0000 = 0    8 = 10 = 1000 =  8
1 = 01 = 0001 = 1    9 = 11 = 1001 =  9
2 = 02 = 0010 = 2    A = 12 = 1010 = 10
3 = 03 = 0011 = 3    B = 13 = 1011 = 11
4 = 04 = 0100 = 4    C = 14 = 1100 = 12
5 = 05 = 0101 = 5    D = 15 = 1101 = 13
6 = 06 = 0110 = 6    E = 16 = 1110 = 14
7 = 07 = 0111 = 7    F = 17 = 1111 = 15

4 bits  =  2⁴ = 16 values
8 bits  =  2⁸ = 256 values
16 bits = 2¹⁶ = 65536 values
32 bits = 2³² = 4294967296 values
64 bits = 2⁶⁴ = 18446744073709551616 values

Representing Signed Integers

• Two's Complement Encoding
• MSB acts as sign bit
• Method:
  1. Start with corresponding unsigned number
  2. Flip all bits (e.g. 0 => 1, 1 => 0)
  3. Add 1 to the result (ignoring overflow)

1. 0110 =  6
2. 1001
3. 1010 = -6

4 bits  = -8 to 7
8 bits  = -128 to 127
16 bits = -32768 to 32767
32 bits = -2147483648 to 2147483647
64 bits = -9223372036854775808 to 9223372036854775807

Representing Floating Point

• Out of scope!
• Ref: IEEE 754
• Example encoding for single-precision 32-bit floating point

0.15625
----------------------------------------------------------------------
sign   exponent: 8bits   fraction: 23bits
   0   0 1 1 1 1 1 0 0   0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  31   30           23   22                                          0

Representing Switches

Consider the following option switches for a text processing program:

1 0 1 1
│ │ │ └ to lowercase?
│ │ └── alpha only?
│ └──── trim whitespace?
└────── reverse? 

input:  "A man, a plan, a canal. Panama."
output: "amanaplanacanalpanama" 

Representing Colors

24-bit RGB Color Space:

Red:    255 000 000 = 11111111 00000000 00000000 = #FF0000
Green:  000 255 000 = 00000000 11111111 00000000 = #00FF00
Blue:   000 000 255 = 00000000 00000000 11111111 = #0000FF
Orange: 235 127 036 = 11101011 01111111 00100100 = #EB7F24 

Representing Images

• Bitmap Encoding (i.e. BMP): color per pixel - simple but wasteful
• Compression (JPEG, PNG, HEIF)
• Example:

500x500 RGBA Image
PNG: 295KiB
BMP: 977KiB (3.3 times larger than PNG)