CPSC 121 – Models of Computation
Module 03. Representing Values in a Computer
Prof. Karina Mochetti
2020.W1
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 1 / 45
Announcements
What is new!
http://www.cs.ubc.ca/~mochetti/CPSC121.html
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 2 / 45
Goals
Understand how computers represent numerical data and other types of data, including real number and its imprecise representation.
Critique the choice of a digital representation scheme, including describing its strengths, weaknesses, and flaws.
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 3 / 45
Reading Review
Binary
A binary number is a representation of an integer as a sum of products of the form d · 2n, where each d is either 0 or 1 (called bits).
Binary to Decimal: multiply each digit for its correspondence power of two.
(11011)2 = (1·24 +1·23 +0·22 +1·21 +1·20)10 = (27)10 Decimal to Binary: Find the highest power of 2 that is less than
the number.
(209)10 = (128+81)10 = (128+64+17)10 = (128+64+16+1)10 (128+64+16+1)10 = (1·27 +1·26 +1·24 +1·20)10 = (11010001)2
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 4 / 45
Reading Review
Adding: adding 1+1 is 0 and has a carry of 1.
111
1101 + 111 10100
Subtracting: when you borrow 1 from 10, what remains is 1. 11
0 10 10 10
1 1e 0e 0e 0e – 1011 1101
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 5 / 45
Reading Review
Two’s Complement
The two complement of an integer a in a n-bit representation is
2n − a. An easy algorithm is to write the n-bit binary representation for a, flip the bits and add 1 in binary notation.
The 8-bit two’s complement of 27:
(27)10 = (16 + 8 + 2 + 1)10 = (00011011)2
(−27)10 = 00011011 → 11100100 → 11100100 + 1 = (11100101)2
From two’s complement to decimal: first convert back to positive and then convert to decimal.
(11010110)2 → 00101001 → 00101001 + 1 → 00101010 = (42)10
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 6 / 45
Reading Review
Two’s Complement
The two complement of an integer a in a n-bit representation is
2n − a. An easy algorithm is to write the n-bit binary representation for a, flip the bits and add 1 in binary notation.
Add two’s complement:
Convert both integers to their n-bit representations (representing negative integers by using two’s complements).
Add the resulting integers using ordinary binary addition. Truncate any leading 1 on the 2n-th position.
Convert the result back to decimal form.
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 7 / 45
Reading Review
Hexadecimal
An hexadecimal number is a representation of an integer as a sum of products of the form d · 16n, where each d is an integer from 0 to 15 (integers 10 through 15 are represented by the symbols A, B, C, D, E, and F).
Hexadecimal to Decimal: multiply each digit for its correspondence power of 16.
(3CF)16 = (3·162 +12·161 +15·160)10 = (975)10 Hexadecimal to Binary: convert each digit to binary and
concatenate the results.
(3CF )16 = 001111001111 = (1111001111)2
Binary to Hexadecimal: group the digits in sets of four from right to left, adding leading 0’s if necessary, and convert each set.
(100110110101001)2 = 0100110110101001 = (4DA9)16
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 8 / 45
Quiz #03 Feedback
Very well done overall!!! \o/
Question 6: What is the decimal value of the signed 6-bit binary number 101110?
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 9 / 45
Unsigned and Signed Integer
Notice the similarities:
number a b c d number b3 b2 b1 b0 0F00 1T11 2F20 3T31 4F40 5T51 6F60 7T71 8F80 9T91
F
F
F
F
F
F
F
F
T
F
F
T
F
T
F
F
T
F
F
T
T
F
T
T
T
F
F
T
F
F
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
1
0
1
1
1
0
0
1
0
0
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 10 / 45
Unsigned and Signed Integer
A sequence of bits is intrinsically neither signed nor unsigned (nor anything else). It’s us who give it its meaning.
An unsigned integer is one we have decided will only represent integer values that are 0 or larger.
A signed integer is one we have decided can represent either a positive value or a negative one.
Other representations are real numbers and characters, for example.
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 11 / 45
Unsigned and Signed Integer
We can use any base to represent a number (10, 2, 24, 13). Humans use 10 and computers use 2.
n-bit unsigned binary number:
bn−1bn−2…b2b1b0
n−1
bi 2i = bn−12n−1 + bn−22n−2…b222 + b121 + b020
i=0
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 12 / 45
Unsigned and Signed Integer
We can use any base to represent a number (10, 2, 24, 13). Humans use 10 and computers use 2.
n-bit unsigned binary number:
bn−1bn−2…b2b1b0
bi 2i = bn−12n−1 + bn−22n−2…b222 + b121 + b020
n−1 i=0
We use two’s complement to to negate a signed binary integer. Why?
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 12 / 45
Unsigned and Signed Integer
For 3-bit integers, what is 111 + 1? Hint: think of a 24 hour clock. a. 110
b. 111
c. 1000
d. 000
e. Error: we can not add these two values.
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 13 / 45
Unsigned and Signed Integer
Considering a 3-bit representation, starting from 010 = (000)2.
CPSC 121 – Models of Computation 14 / 45
Module 03. Representing Values in a Computer
Unsigned and Signed Integer
Considering a 3-bit representation, starting from 010 = (000)2. Let’s add 1 and create the numbers 1 through 11.
CPSC 121 – Models of Computation 14 / 45
Module 03. Representing Values in a Computer
Unsigned and Signed Integer
Considering a 3-bit representation, starting from 010 = (000)2. Let’s add 1 and create the numbers 1 through 11.
Now, let’s copy that to subtract 1 and create the numbers -1 to -8.
CPSC 121 – Models of Computation
14 / 45
Module 03. Representing Values in a Computer
Unsigned and Signed Integer
Considering a 3-bit representation, starting from 010 = (000)2. Let’s add 1 and create the numbers 1 through 11.
Now, let’s copy that to subtract 1 and create the numbers -1 to -8.
This are the numbers that can be represented by 3-bit unsigned integers.
CPSC 121 – Models of Computation
14 / 45
Module 03. Representing Values in a Computer
Unsigned and Signed Integer
Considering a 3-bit representation, starting from 010 = (000)2. Let’s add 1 and create the numbers 1 through 11.
Now, let’s copy that to subtract 1 and create the numbers -1 to -8.
This are the numbers that can be represented by 3-bit unsigned integers.
This are the numbers that can be represented by 3-bit signed integers.
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 14 / 45
Unsigned and Signed Integer
Overflow
It happens when the addition of two positive operands produces negative sum
(2 + 3)10 = (010 + 011)2 = (101)2
Underflow
It happens when the addition of two negative operands produces positive sum
(−2 + −3)10 = (110 + 101)2 = (011)2
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 15 / 45
Unsigned and Signed Integer
Binary to Decimal: multiply each digit by its correspondent power of two.
(1011011001)2 = 1·29 +0·28 +1·27 +1·26 +0·25 +1·24 +1· 23 +0·22 +0·21 +1·20 = 512+128+64+16+8+1 = (729)10
Decimal to Binary: Divide by 2 and write down the remainder and keep going until you reach 0. Write down the remainders from right to left.
729 = 364 = 182 = 91 = 45 = 22 = 11 = 5 = 2 = 1 = 0 2222222222
1001101101 (729)10 = (1011011001)2
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 16 / 45
Unsigned and Signed Integer
With n bits, how many distinct values can we represent?
What are the smallest and largest n-bit unsigned binary integers?
What are the smallest and largest n-bit signed binary integers?
Why are there more negative n-bit signed integers than positive ones?
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 17 / 45
Unsigned and Signed Integer
How do we tell quickly if a signed binary integer is negative, positive, or zero?
There is one signed n-bit binary integer that we should not try to negate. Which one?
What do we get if we try negating it?
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 18 / 45
Modular Arithmetic
24 hour clock
Some places, like Brazil, use the 24 hours clock, where 0 is midnight, 1-11 is 1-11 am, 12 is noon, and 13-23 is 1-11 pm.
Imagine the time is currently 15:00 (or 3:00 pm).
– What time was it 8·21 hours ago?
– What time will it be 13·23 hours from now?
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 19 / 45
Modular Arithmetic
Modular
Given an integer m, we partition integers based on their remainder after division by m.
So a 24 hour clock uses m = 24, and has 24 classes.
For m = 5 we have the classes {0, 1, 2, 3, 4}, with: [0] = {…, −15, −10, −5, 0, 5, 10, 15, …}
[1] = {…, −14, −9, −4, 1, 6, 11, 16, …}
[2] = {…, −13, −8, −3, 2, 7, 12, 17, …}
[3] = {…, −12, −7, −2, 3, 8, 13, 18, …} [4] = {…, −11, −6, −1, 4, 9, 14, 19, …}
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 20 / 45
Modular Arithmetic
Modular Operation
We write x mod m to denote the representative for the class of m that x belongs to given by the remainder we get after dividing x by m.
27 mod 4 = 3, because 27 = 6 · 4 + 3 52 mod 11 = 8, because 52 = 4 · 11 + 8
Equivalence
If x and y belong to the same class modulo m (have the same remainder) then we write x ≡ y mod m.
27 ≡ 55 mod 4, because 55 mod 4 = 3 52 ≡ 162 mod 11, because 162 mod 11 = 8
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 21 / 45
Modular Arithmetic
What is 57 mod 8? a. 1
b. 3 c. 5 d. 7
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 22 / 45
Modular Arithmetic
Suppose that x ≡ 34 mod 6. Which are possible values for x? a. 4, 17 and 28.
b. 12, 28 and 38.
c. 36, 72 and 216.
d. 10, 16 and 52.
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 23 / 45
Modular Arithmetic
Fundamental Theorem of Modular Arithmetic
If a ≡ c mod m and b ≡ d mod m then ab ≡ cd mod m.
This theorem means that it doesn’t matter if you do a sequence of operations, and then take the remainder mod m at the end or take the remainder mod m every time you perform an operation in the sequence.
(10 · 15 · 23) mod 7 = (10 mod 7) · (15 mod 7) · (23 mod 7) 3450 mod 7 = 3 · 1 · 2
6=6
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 24 / 45
Questions?
Ask CPSC 121
http://www.cs.ubc.ca/~mochetti/askCPSC121.html
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 25 / 45
Characters
Computers use sequences of bits to represent all data, including characters. Since there is no natural representation for it, people created arbitrary mappings.
EBCDIC: earliest, now used only for IBM mainframes.
ASCII: American Standard Code for Information Interchange, 7-bit per character, sufficient for upper/lowercase, digits, punctuation and a few special characters.
UNICODE: 16 or 32 bits, extended ASCII for languages other than English.
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 26 / 45
Characters: ASCII table
00101011
00110100
?
00111111
+ 01100111 , 01101000 – 01101001 . 01101010 / 01101011
0 01101100
1 01101101
2 01101110
3 01101111
4 01110000
5 01110001
6 01110010
7 01110011
8 01110100
9 01110101
: 01110110 ; 01110111
< 01111000 = 01111001 > 01111010
01001000
S
01010011
01011100
g
00101100
@
01000000
T
01010100
h
00101101
A
01000001
U
01010101
i
00101110
B
01000010
V
01010110
j
00101111
C
01000011
01000100
W
01010111
k
00110000
D
X
01011000
l
00110001
E
01000101
Y
01011001
m
00110010
F
01000110
Z
01011010
n
00110011
G
01000111
[
01011011
o
H
\
p
00110101
I
01001001
]
01011101
q
00110110
J
01001010
ˆ
01011110
r
00110111
K
01001011
_
01011111
s
00111000
L
01001100
‘
01100000
t
00111001
M
01001101
a
01100001
u
00111010
N
01001110
b
01100010
v
00111011
O
01001111
c
01100011
w
00111100
P
01010000
01010001
d
01100100
x
00111101
Q
e
01100101
y
00111110
R
01010010
f
01100110
z
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 27 / 45
Characters
What does the 8-bit binary value 11111000 represent? a. -8
b. The character ◦
c. 248
d. More than one of the above. e. None of the above.
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 28 / 45
Real numbers
Can someone be 1/3rd Belgian?
Here is a fun answer from this term:
No, because you have to have two parents that have a fraction of an ethnicity and the denominator has to be a number that is a power of 2. You would need three parents for that to be possible. However, there is a medical procedure where you replace the nucleus of an egg with bad mitochondria into a nucleus-less egg with working mitochondria, which can then be fertilized with sperm. This procedure involves three people and if one of them is Scottish, then you can technically be one-third Scottish.
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 29 / 45
Real numbers
Can someone be 1/3rd Belgian?
In a mathematical sense, you can create 1/3 using infinite sums of inverse powers of 2:
1/2 isn’t very close
1/4 isn’t either
3/8 is getting there
5/16 is yet closer, so is 11/32, 21/64, 43/128 etc
85/256 is 0.33203125, which is much closer, but which also implies eight generations of very careful romance amongst your elders.
5461/16384 is 0.33331298828125, which is still getting there, but this needs fourteen generations and a heck of a lot of Scots and non-Scots.
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 30 / 45
Real numbers
Can someone be 1/3rd Belgian?
While debated, Scotland is traditionally said to be founded in 843 AD, approximately 45 generations ago. Your mix of Scottish, will therefore be n/245.
Using 245/3 (rounded to the nearest integer) as the numerator gives us n = 11728124029611.
11728124029611/245 gives us approximately 0.333333333333342807236476801 which is no more than 1/1013-th away from 1/3.
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 31 / 45
Real numbers
Representing (finite) fractional values in binary still works analogously to decimal:
Decimal:
Binary:
3.57=3·100 +5·10−1 +7·10−2
0.00101=1·2−3+1·2−5=1+ 1 = 5 8 32 32
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 32 / 45
Real numbers
Which of the following values have a finite binary expansion? a. 1/3
b. 1/4
c. 1/5
d. More than one of the above. e. None of the above.
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 33 / 45
Real numbers
Numbers with fractional components:
Decimal:
1/3 = 0.3333333333333333333333333333… 1/4 = 0.25
1/5 = 0.2
Binary:
1/3 = 1/4 = 1/5 =
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 34 / 45
Real numbers
Scientific Notation
Expressing numbers that are too big or too small in the form
m · be , where b gives the base (usually 10 for decimal numbers).
Decimal Representation:
1724 = 1.724 · 103
Binary Representation:
172410 = 110101111002 = 1.1010111100 · 21010
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 35 / 45
Real numbers
Scientific Notation
Expressing numbers that are too big or too small in the form
m · be , where b gives the base (usually 10 for decimal numbers).
exponent
1. 1010111100 ·2 1010
mantissa
C and other languages store only the mantissa and exponent. The mantissa has a fixed number of bits (24 for float, 53 for double).
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 36 / 45
Real numbers
Scheme/Racket also uses this for inexact numbers!
Computations involving floating point numbers are imprecise.
The computer does not store 1/3, but a number that’s very close to 1/3.
The more computations we perform, the further away from the “real” value we are.
What is the output of the following code?
(* (sqrt 2) (sqrt 2))
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 37 / 45
Real numbers
Scheme/Racket also uses this for inexact numbers!
Computations involving floating point numbers are imprecise.
The computer does not store 1/3, but a number that’s very close to 1/3.
The more computations we perform, the further away from the “real” value we are.
What is the output of the following code?
(* (sqrt 2) (sqrt 2))
It will not be exact 2.0! It is 2.0000000000000004!
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 37 / 45
Real numbers
Consider the following:
(define (addfractions x)
(if (= x 1.0)
0
(+ 1 (addfractions (+ x #i0.1)))))
What value will (addfractions 0) return? a. 10
b. 11
c. Less than 10
d. More than 11
e. No value will be printed
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 38 / 45
Hexadecimal
Binary to Hexadecimal
0000 – 0 0001 – 1 0010 – 2 0011 – 3
0100 – 4 0101 – 5 0110 – 6 0111 – 7
1000 – 8 1001 – 9 1010 – A 1011 – B
1100 – C 1101 – D 1110 – E 1111 – F
As you learned in CPSC 110, a program can be:
Interpreted: another program is reading your code and performing the operations indicated. Example: Scheme/Racket
Compiled: the program is translated into machine language. Then the machine language version is executed directly by the computer. Example: C
Computers use bytes (8-bits) as their basic data.
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 39 / 45
Hexadecimal: Instructions
A machine instruction is a sequence of bits that is different for each processor.
Y86 example of adding two values:
Human-readable form: addl %ebx %ecx Binary: 0110000000110001
Decimal: 24625 → information is hard to see! Hexadecimal: 6031
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 40 / 45
Hexadecimal: Colors
The 3 basic colors in a computer are red, blue and green (RGB). Other colors are create by combining this 3 colors.
RED: FF0000 GREEN: 00FF00 BLUE: 0000FF YELLOW: FFFF00 LAVENDER: B57EDC BLACK: 000000
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 41 / 45
Questions?
Ask CPSC 121
http://www.cs.ubc.ca/~mochetti/askCPSC121.html
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 42 / 45
Exercise
Indicate for the following operations on 4-bit with two’s complement, if it produces an overflow, an underflow or a correct answer:
1 0101 + 0010
2 1000 + 1010
3 1111 + 1100
4 0110 + 0011
5 0000 + 1101
6 1010 + 0101
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 43 / 45
Exercise: Solution
Indicate for the following operations on 4-bit with two’s complement, if it produces an overflow, an underflow or a correct answer:
1 0101 + 0010 = 0111 CORRECT
2 1000 + 1010 = 0010 UNDERFLOW
3 1111 + 1100 = 1011 CORRECT
4 0110 + 0011 = 1001 OVERFLOW
5 0000 + 1101 = 1101 CORRECT
6 1010 + 0101 = 1111 CORRECT
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 44 / 45
Meme
Module 03. Representing Values in a Computer
CPSC 121 – Models of Computation 45 / 45