Transcript PPTX

Module 3: Representing
Values in a Computer
Due Dates
• Assignment #1 is due Thursday January 19th at
4pm
• Pre-class quiz #4 is due Thursday January 19th at
7pm.
• Assigned reading for the quiz:
• Epp, 4th edition: 2.3
• Epp, 3rd edition: 1.3
• Come to my office hours (ICCS X563)!
• Wednesday 4-5pm, Thursday 2-3pm, and
Friday 12-1pm
2
Learning goals: pre-class
• By the start of this class you should be able to
• Convert unsigned integers from decimal to binary
and back.
• Take two's complement of a binary integer.
• Convert signed integers from decimal to binary
and back.
• Convert integers from binary to hexadecimal and
back.
• Add two binary integers.
3
Learning goals: in-class
• By the end of this module, you should be able to:
• Critique the choice of a digital representation
scheme, including describing its strengths,
weaknesses, and flaws (such as imprecise
representation or overflow), for a given type of
data and purpose, such as
• fixed-width binary numbers using a two’s
complement scheme for signed integer arithmetic in
computers
• hexadecimal for human inspection of raw binary
data.
4
CPSC 121: the BIG questions:
• We will make progress on two of them:
• How does the computer (e.g. Dr. Racket) decide if
the characters of your program represent a name,
a number, or something else? How does it figure
out if you have mismatched " " or ( )?
• How can we build a computer that is able to
execute a user-defined program?
5
Module 3 outline
• Unsigned and signed binary integers.
• Characters.
• Real numbers.
• Hexadecimal.
8
Review question
• What does it mean for a binary integer to be
unsigned or signed?
Recall the 7-segment display problem
• Mapping unsigned integers between decimal and
binary
Number
X1
X2
X3
X4
0
0
0
0
0
1
0
0
0
1
2
0
0
1
0
3
0
0
1
1
4
0
1
0
0
5
0
1
0
1
6
0
1
1
0
7
0
1
1
1
8
1
0
0
0
9
1
0
0
1
10
Unsigned binary  decimal
• The binary value
• Represents the decimal value
• Examples:
• 010101 = 24 + 22 + 20 = 16 + 4 + 1 = 21
• 110010 = 25 + 24 + 21 = 32 + 16 + 2 = 50
11
Decimal  unsigned binary
• Divide x by 2 and write down the remainder
• The remainder is 0 if x is even, and 1 if x is odd.
• Repeat this until the quotient is 0.
• Write down the remainders from right (first one)
to left (last one).
Decimal  unsigned binary
• Example: Convert 50 to a 8-bit binary integer
• 50 / 2 = 25with remainder 0
• 25 / 2 = 12 with remainder 1
• 12 / 2 = 6 with remainder 0
• 6 / 2 = 3 with remainder 0
• 3 / 2 = 1 with remainder 1
• 1 / 2 = 0 with remainder 1
• Answer is 00110010.
To negate a (signed) binary integer
The algorithm (also called taking two’s complement
of the binary number):
• Flip all bits: replace every 0 bit by a 1, and every 1
bit by a 0.
• Add 1 to the result.
Why does it make sense to negate a binary integer
by taking its two’s complement?
14
Additive Inverse
• Two numbers x and y are “additive inverses” of
each other if they sum to 0.
• Examples: 3 + (-3) = 0. (-7) + 7 = 0.
15
Clock arithmetic
• Pre-class quiz #3b:
• It is currently 18:00, that is 6pm.
Without using numbers larger than
24 in your calculations, what time
will it be 22 * 7 hours from now?
(Don’t multiply 22 by 7!)
16
Clock arithmetic
• 3:00 is 3 hour from midnight.
• 21:00 is 3 hours to midnight.
• 21 and 3 are additive inverses in
clock arithmetic: 21 + 3 = 0.
• Any two numbers across the clock
are additive inverses of each other.
• 21 is equivalent to -3 in any
calculation.
Clock arithmetic
• Pre-class quiz #3b:
• It is currently 18:00, that is 6pm.
Without using numbers larger than
24 in your calculations, what time
will it be 22 * 7 hours from now?
(Don’t multiply 22 by 7!)
a.
b.
c.
d.
e.
0:00 (midnight)
4:00 (4am)
8:00 (8am)
14:00 (2pm)
None of the above
18
Negative numbers in clock arithmetic
• Put negative numbers
across the clock from
the positive ones
(where the additive
inverses are).
• Since 21 + 3 = 0, we
could put -3 where 21
is.
-3
0
-6
-9
-12
Binary clock arithmetic
• Suppose that we have 3 bits to work with.
• If we are only representing positive values or zero:
000
111
7
0
1
2 010
110 6
5
101
001
4
100
3
011
Binary clock arithmetic
• If we want to represent negative values...
• We can put them across the clock from the
positive ones (where the additive inverses are).
000
111
-1
0
1
2 010
110 -2
-3
101
001
-4
100
3
011
Two’s Complement
Taking two’s complement of B = b1b2b3...bn:
Flip
the
bits
1 1 1 ...1
- b1b2b3...bn
---------x1x2x3...xn
Add
1
one +
----------B
22
A Different View of
Two’s Complement
Taking two’s complement of B = b1b2b3...bk:
Flip
the
bits
1 1 1 ...1
- b1b2b3...bk
---------x1x2x3...xk
Add
1
one +
----------B
1 1 1 ...1
+
1
---------1 0 0 0 ...0
- b1b2b3...bk
----------B
Equivalent to subtracting from 100...000 with k 0s.
23
Two’s Complement vs.
Crossing the Clock
Two’s complement with k
bits:
1 1 1 ...1
1
---------1 0 0 0 ...0
- b1b2b3...bn
----------B
000
+
111
1
-3
001
2 010
110 -2
101
Equivalent to subtracting
from 100...000 with k 0s.
-1
0
-4
3
011
100
24
Advantages of two’s complement
• Which one(s) are the advantages of the two’s
complement representation scheme?
a. There is a unique representation of zero.
b. It is easy to tell a negative integer from
a non-negative integer.
c. Basic operations are easy. For example,
subtracting a number is equivalent to adding the
two’s complement of the number.
d. All of (a), (b), and (c).
e. None of (a), (b), and (c).
Advantages of two’s complement
• Why did we choose to let 100 represent -4 rather
than 4?
000
000
111
-1
0
1
2 010
110 -2
-3
101
001
-4
100
111
-1
1
-3
101
001
2 010
110 -2
3
011
0
4
100
3
011
What does two’s complement mean?
a. Taking two’s complement of a binary integer
means flip all of the bits and then add 1.
b. Taking two’s complement is a mathematical
procedure to negate a binary integer.
c. Two’s complement is a representation scheme
we use to map signed binary integers to decimal
integers.
d. 2 of (a), (b), and (c) are true.
e. All of (a), (b), and (c) are true.
Negative binary  decimal
• Example: convert the 6-bit signed binary integer
101110 to a decimal number.
1. Convert the binary integer directly to decimal
(2 + 4 + 8 + 32 = 46)
2. Subtract 2^6 from it (2^6 because of 6-bit)
(46 – 64 = -18).
3. Answer is -18.
29
Negative binary  decimal
• The signed binary value
• represents the integer
• Example: convert the 6-bit signed binary integer
101110 to a decimal number.
• -25 + 23 + 22 + 21 = -32 + 8 + 4 + 2 = -18.
• Answer is -18.
30
Negative decimal  binary
• Example: convert -18 to a 6-bit signed binary
number.
1. Add 2^6 to it (2^6 because of 6-bit)
(-18 + 2^6 = -18 + 64 = 46).
2. Convert the positive decimal integer directly to
binary. 46 / 2 = 23 … 0, 23 / 2 = 12 ... 1, 12 / 2 = 6
... 0, 6 / 2 = 3 ... 0, 3 / 2 = 1 ... 1, 1 / 2 = 0 ... 1.
3. Answer is 110010.
Questions to ponder:
• 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?
32
More questions to ponder:
• Why are there more negative n-bit signed integers
than positive ones?
• How do we tell if an unsigned binary integer is:
negative, positive, zero?
• How do we tell if a signed binary integer is:
negative, positive, zero?
• How do we negate a signed binary integer?
• On what value does this “negation” not behave
like negation on integers?
• How do we perform the subtraction x – y?
33
Module 3 outline
• Unsigned and signed binary integers.
• Characters.
• Real numbers.
• Hexadecimal.
34
How do computers represent characters?
• It uses sequences of bits (like for everything else).
• Integers have a “natural” representation of this kind.
• There is no natural representation for characters.
• So people created arbitrary mappings:
• EBCDIC: earliest, now used only for IBM mainframes.
• ASCII: American Standard Code for Information
Interchange7-bit per character, sufficient for
upper/lowercase, digits, punctuation and a few special
characters.
• UNICODE:16+ bits, extended ASCII for languages other
than English
35
Representing 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.
Show Answer
36
Module 3 outline
• Unsigned and signed binary integers.
• Characters.
• Real numbers.
• Hexadecimal.
38
Can someone be 1/3rd Scottish?
• No, but what if I once wore a kilt?
• Not normally, since every person's genetic code is
derived from two parents, branching out in halves
going back. However, someone with a
chromosome abnormality that gives them three
chromosomes (trisomy), a person might be said to
be one-third/two-thirds of a particular genetic
marker.
39
Can someone be 1/3rd Scottish?
• I have come to the conclusion that no, you cannot be onethird Scottish. I will provide my reasoning with the
following two examples. Say there are two progenitors, P
and Q. P is Korean and Q is American. If P and Q have a
child, PQ, he will be 1/2 Korean and 1/2 American. Now say
that PQ grows up to the legal age (no pedophillia in here)
and enters a romantic relationship with another progenitor,
R, who is Scottish. PQ and R have a child, PQR, and he will
be 1/2 Scottish, 1/4 Korean, and 1/4 American. The second
example, we can say PQ conceives a child, PQUT, with
someone named UT, who is 1/2 Ethiopian and 1/2 African.
PQUT would be 1/4 of each ethnicity. We can see that you
will only be (1/2)^n - where n is a nonnegative integer - of
an ethnicity (n in this context means which generation it is).
Notice that the denominator will always be a multiple of 2.
Therefore, you can never be 1/3 of any ethnicity.
40
Can someone be 1/3rd Scottish?
While debated, Scotland is traditionally said
to be founded in 843AD, approximately 45
generations ago.45Your mix 45
of Scottish, will
therefore be n/2 ; using 2 /3 (rounded to
the nearest integer) as45the numerator gives
us 11728124029611/2 which give us
approximately
0.333333333333342807236476801
13
which is no more than 1/10 th away from
1/3.
41
Can someone be 1/3rd Scottish?
If we assume that two Scots have a child, and
that child has a child with a non-Scot, and this
continues in the right proportions, then
eventually their Scottishness will approach 1/3:
This is of course discounting the crazy
citizenship laws we have these days, and the
effect of wearing a kilt on one's heritage.
42
Can someone be 1/3rd Scottish?
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.
43
Can someone be 1/3rd Scottish?
• To answer this question, we need to make some
assumptions.
• What does being Scottish mean? Nationality?
Ethic identity?
• How does the Scottish-ness of a parent influence
the Scottish-ness of a child?
• Our model of ancestry: Each parent gives you 50%
of an ancestry.
Can someone be 1/3rd Scottish?
• Suppose we start with people who are either 0%
or 100% Scottish.
• After 1 generation, how Scottish can a child be?
• After 2 generations, how Scottish can a grandchild be?
• What about 3 generations?
• What about n generations?
45
Fractions in base 10 and base 2
• 5/8
= 0.625 (in base 10)
= 5 * 1/23
= 0.101 (in base 2)
• 1/3
= 0.3333333333….........(in base 10)
= 0.25 + 0.0625 + 0.15625 + …
= 1/22 + 1/24 + 1/26 + ...
= 0.010101.....(in base 2)
Representing real numbers in binary
Which of the following values have a finite binary
expansion?
a.1/4
b.1/6
c.1/9
d.More than one of the above.
e.None of the above.
▷
47
Representing real numbers in binary
Which fractions have a finite binary
expansion?
In decimal:
1/8 = 0.125
1/10 = 0.1
In binary:
1/8 =
1/10 =
49
How does computer represent values
of the form xxx.yyyy?
Java uses scientific notation
3
1724 = 1.724 x 10
But in binary, instead of decimal.
1010
1724 = 1.1010111100 x 2
mantissa
exponent
Only the mantissa and exponent need to be
stored.
The mantissa has a fixed number of bits (24 for
float, 53 for double).
Scheme/Racket uses this for inexact numbers.
50
Floating point computations
• 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.
51
Floating point computations
• Predict the output of:
(* #i0.01 0.01 0.01 100 100 100)
a.
b.
c.
d.
1
Not 1, but a value close to 1.
Not 1, but a value far from 1.
I don’t know.
▷
52
Floating point computations
Consider the following:
(define (addfractions x)
(if (= x 1.0)
0
(+ 1 (addfractions (+ x #i0.1)))))
What value will (addfractions 0) return?
a) 10
d) More than 11
b) 11
e) No value will be printed
c) Less than 10
▷
53
Module 3 outline
Summary
Unsigned and signed binary integers.
Characters.
Real numbers.
Hexadecimal.
55
Module 3.4: Hexadecimal
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.
56
Module 3.4: Hexadecimal
What does a machine language instruction look
like?
It is a sequence of bits!
Y86 example: adding two values.
In human-readable form: addl %ebx,
%ecx.
In binary: 0110000000110001
%ecx
%ebx
Addition
57
Arithmetic operation
Module 3.4: Hexadecimal
Long sequences of bits are painful to read and
write, and it's easy to make mistakes.
Should we write this in decimal instead?
Decimal version: 24625.
Problem: We can not tell what operation this is.
Solution: use hexadecimal 6031
%ecx
%ebx
Addition
58
Arithmetic operation
Module 3.4: Hexadecimal
Another example:
Suppose we make the text in a web page
use color 15728778.
What color is this?
Red leaning towards
purple.
Written in hexadecimal: F00084
Red
Green
Blue
59