L01: Binary CMPT 295
Lecture Outline
! Binary
” Decimal, Binary, and Hexadecimal ” Base Conversion
” Binary Encoding
1
L01: Binary CMPT 295
Decimal Numbering System
! Ten symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
! Represent larger numbers as a sequence of digits
” Each digit is one of the available symbols
! Example: 7061 in decimal (base 10)
” 706110 = (7 × 103) + (0 × 102) + (6 × 101) + (1 × 100)
2
L01: Binary CMPT 295
Octal Numbering System
!Eightsymbols: 0,1,2,3,4,5,6,7 ” Notice that we no longer use 8 or 9
! Base comparison:
” Base 10: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12…
” Base 8: 0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14…
! Example: What is 70618 in base 10?
“70618 =(7×83)+(0×82)+(6×81)+(1×80)=363310
3
L01: Binary CMPT 295
Warmup Question
! What is 348 in base 10?
A. 3210 B. 3410 C. 710 D. 2810 E. 3510
4
L01: Binary CMPT 295
Binary and Hexadecimal
! Binary is base 2
“Symbols: 0,1
” Convention: 210 = 102 = 0b10
! Example: What is 0b110 in base 10? “0b110=1102 =(1×22)+(1×21)+(0×20)=610
! Hexadecimal (hex, for short) is base 16 “Symbols? 0,1,2,3,4,5,6,7,8,9,A…,?B,C,D,E,F ” Convention: 1610 = 1016 = 0x10
! Example: What is 0xA5 in base 10? “0xA5=A516 =(10×161)+(5×160)=16510
5
L01: Binary CMPT 295
Peer Instruction Question
! Which of the following orderings is correct?
A. 0xC < 0b1010 < 11
B. 0xC < 11 < 0b1010
C. 11 < 0b1010 < 0xC
D. 0b1010<11<0xC
E. 0b1010 < 0xC < 11
6
L01: Binary CMPT 295
Converting to Base 10
! Can convert from any base to base 10 "0b110=1102 =(1×22)+(1×21)+(0×20)=610 "0xA5=A516 =(10×161)+(5×160)=16510
! We learned to think in base 10, so this is fairly natural for us
! Challenge: Convert into other bases (e.g. 2, 16)
7
L01: Binary CMPT 295
Challenge Question
! Convert 1310 into binary
! Hints: " 23 = 8 " 22 = 4 " 21 = 2 " 20 = 1
8
L01: Binary CMPT 295
Converting from Decimal to Binary
! Given a decimal number N:
" List increasing powers of 2 from right to left until ≥ N
" Then from left to right, ask is that (power of 2) ≤ N?
• If YES, put a 1 below and subtract that power from N
• If NO, put a 0 below and keep going
! Example: 13 to binary
24=16
23=8
22=4
21=2
20=1
9
L01: Binary CMPT 295
Converting from Decimal to Base B
! Given a decimal number N:
" List increasing powers of B from right to left until ≥ N
" Then from left to right, ask is that (power of B) ≤ N?
• If YES, put how many of that power go into N and subtract from N
• If NO, put a 0 below and keep going
! Example: 165 to hex
162=256
161=16
160=1
10
L01: Binary CMPT 295
Converting Binary ↔ Hexadecimal ! Hex → Binary
" Substitute hex digits, then drop any leading zeros
"Example: 0x2Dtobinary
• 0x2 is 0b0010, 0xD is 0b1101
• Drop two leading zeros, answer is 0b101101
! Binary → Hex
" Pad with leading zeros until multiple of
4, then substitute each group of 4
"Example: 0b101101
• Pad to 0b 0010 1101
• Substitute to get 0x2D
11
Base 10
Base 2
Base 16
0
0000
0
1
0001
1
2
0010
2
3
0011
3
4
0100
4
5
0101
5
6
0110
6
7
0111
7
8
1000
8
9
1001
9
10
1010
A
11
1011
B
12
1100
C
13
1101
D
14
1110
E
15
1111
F
L01: Binary CMPT 295
Binary → Hex Practice
! Convert 0b100110110101101 " How many digits?
" Pad:
" Substitute:
Base 10
Base 2
Base 16
0
0000
0
1
0001
1
2
0010
2
3
0011
3
4
0100
4
5
0101
5
6
0110
6
7
0111
7
8
1000
8
9
1001
9
10
1010
A
11
1011
B
12
1100
C
13
1101
D
14
1110
E
15
1111
F
12
L01: Binary CMPT 295
Base Comparison
! Why does all of this matter?
" Humans think about numbers in base 10, but computers “think” about numbers in base 2
" Binary encoding is what allows computers to do all of the amazing things that they do!
! You should have this table memorized by the end of the class
" Might as well start now!
Base 10
Base 2
Base 16
0
0000
0
1
0001
1
2
0010
2
3
0011
3
4
0100
4
5
0101
5
6
0110
6
7
0111
7
8
1000
8
9
1001
9
10
1010
A
11
1011
B
12
1100
C
13
1101
D
14
1110
E
15
1111
F
13
L01: Binary CMPT 295
Numerical Encoding
! AMAZING FACT: You can represent anything countable using numbers!
" Need to agree on an encoding
" Kind of like learning a new language
! Examples:
" Decimal Integers: 0→0b0, 1→0b1, 2→0b10, etc.
"EnglishLetters: CSE→0x435345,yay→0x796179
" Emoticons: 😃 0x0, 😞 0x1, 😎 0x2, 😇 0x3, 😈 0x4, 🙋 0x5
14
L01: Binary CMPT 295
Binary Encoding
! With N binary digits, how many “things” can you represent?
" Need N binary digits to represent 𝑛 things, where 2N ≥ 𝑛 " Example: 5 binary digits for alphabet because 25 = 32 > 26
! A binary digit is known as a bit
! A group of 4 bits (1 hex digit) is called a nibble
! A group of 8 bits (2 hex digits) is called a byte
” 1 bit → 2 things, 1 nibble → 16 things, 1 byte → 256 things
15
L01: Binary CMPT 295
Binary Encoding – Colors
! RGB – Red, Green, Blue
” Additive color model (light): byte (8 bits) for each color ” Commonly seen in hex (in HTML, photo editing, etc.)
“Examples: Blue→0x0000FF,Gold→0xFFD700, White→0xFFFFFF, Deep Pink→0xFF1493
16
L01: Binary CMPT 295
Binary Encoding – Characters/Text
! ASCII Encoding (www.asciitable.com)
” American Standard Code for Information Interchange
17
L01: Binary CMPT 295
Binary Encoding – Files and Programs
! At the lowest level, all digital data is stored as bits!
! Layers of abstraction keep everything comprehensible
” Data/files are groups of bits interpreted by program
” Program is actually groups of bits being interpreted by your CPU
18
L01: Binary CMPT 295
Summary
! Humans think about numbers in decimal; computers think about numbers in binary
” Base conversion to go between them
” Hexadecimal is more human-readable than binary
! All information on a computer is binary ! Binary encoding can represent anything!
” Computer/program needs to know how to interpret the bits
19