CSC165H1, Winter 2022 CSC165H1: Worksheet 10—Number Representations (Partial Solutions)
Learning Objectives
By the end of this worksheet, you will:
• Understand how to represent natural numbers in different bases and convert between representations in different bases.
Copyright By PowCoder代写 加微信 powcoder
• Represent fractional numbers in binary.
1. Representing the natural numbers. Recall that we can represent the natural numbers using decimal (base 10) and binary (base 2); we can generalize this to arbitrary bases. Let b ∈ Z+, and suppose b ≥ 2. For k ∈ Z+ and d0,d1,…,dk−1 ∈{0,1,…,b−1},theexpression(dk−1dk−2…d1d0)b representsthenumber
x = di × bi
Now we are going to look at two specific bases that are useful in computer science: octal (base 8) and hexadecimal
(base 16).
(a) Octal numbers are base 8. For example, (11)8 represents the number 9. What number does (165)8 represent?1
(b) Hexadecimal numbers are base 16. Since we only have the digits 0-9, hexadecimal uses letters to stand in for 10-15: A = 10, B = 11, and so on. For example, (1F)16 is the hexadecimal representation of the number 31. What number does (B4)16 represent?2
2. Converting between bases. Since binary, octal, decimal, and hexadecimal number representations frequently come up in computer science, it is useful to know how to convert between them.
We will first look at converting from decimal to binary and then consider converting to octal or hex from there. One way to convert a decimal number into binary is to repeatedly divide it by two. The remainder from each division is then a bit in the binary representation and we continue with the quotient.
For example, if we want to convert 29 into binary, we proceed as follows:
29÷2=14, 14÷2 = 7, 7÷2=3, 3÷2=1, 1÷2=0,
remainder1 remainder 0 remainder1 remainder1 remainder1
The binary representation of 29 is the sequence of remainders read bottom to top: 29 = (11101)2. (a) Find the binary representation of 357.
1In Python, you can input numbers in octal format by putting 0o in front of the octal representation. For example, 0o11 is Python’s octal representation of the number 9.
2In Python, you can input numbers in hexadecmial format by putting 0x in front of the representation. For example, 0x1F is Python’s hexadecimal representation of the number 31.
CSC165H1, Winter 2022 CSC165H1: Worksheet 10—Number Representations (Partial Solutions)
357 = (101100101)2
(b) Now let’s look at converting from binary to octal. Since 8 = 23, every three binary bits correspond to one octal digit (starting from the right). For example, (111 110)2 = (76)8 (we used a space to divide the binary representation into groups of three bits).
Using your answer to the previous part, find the octal representation of 357.
(c) Using the same idea, find the hexadecimal representation of 357. (Hint: 16 = 24.)
3. Representing fractions. We have previously considered how we can represent the natural numbers using different bases. What if we want to represent real numbers instead? It turns out we can approach it in the same way. In this exercise, we’ll consider how to represent a number between zero and one.
Let b ∈ Z+, and suppose b ≥ 2. For k ∈ Z+ and d1,…,dk−1 ∈ {0,1,…,b − 1}, the expression (0.d1d2 …dk)b represents the number
357 = (101 100 101)2 = (545)8
357 = (0001 0110 0101)2 = (165)16
x=di×b−i= i
bi i=1 i=1
How do we convert fractional numbers from decimal to binary? The conversion algorithm is essentially the same as the one for natural numbers, but we instead multiply by 2: if the result goes over 1, we record a 1 and keep going with the fractional part.
For example, here is how we can convert 0.8125 to binary:
0.8125×2 = 0.625 +1
0.625×2 = 0.25 0.25×2 = 0.5 0.5 × 2 = 0
We are done when we reach 0. The binary representation is now the sequence of whole numbers on the right-hand
side, read top to bottom, placed after the decimal point. So 0.8125 = (0.1101)2.
(a) Find the binary representation of 0.375. Explicitly write out the sum to verify your answer.
0.375 = (0.011)2. We can check this by computing 0 × 0.5 + 1 × 0.25 + 1 × 0.125 = 0.375.
CSC165H1, Winter 2022 CSC165H1: Worksheet 10—Number Representations (Partial Solutions)
Even though the last example worked out cleanly, this conversion process doesn’t always reach zero! Just like decimal representation, binary representations sometimes have repeating bits after the decimal point. For example,
13 has representation 0.3 in decimal, where the overline indicates that the 3 repeats. This is true in binary as well: 31 = (0.01)2. Let’s see how we would obtain this using the algorithm we learned at the start of this section:
13 × 2 = 32 + 0 23 × 2 = 31 + 1 13 × 2 = . . .
After the second step, we’ve returned to 13, and the sequence 01 we obtained up to this point repeats.
(b) Find the binary representation of 1 .3 10
Pay attention to when the pattern starts to repeat—it’s not the entire sequence of bits!
0.1 × 2 = 0.2 + 0 0.2 × 2 = 0.4 + 0 0.4 × 2 = 0.8 + 0 0.8 × 2 = 0.6 + 1 0.6 × 2 = 0.2 + 1
0.2 × 2 = . . .
So the binary representation is 0.1 = (0.00011)2.
Note that what repeats is the sequence of values [0.2, 0.4, 0.8, 0.6], and so the four bits corresponding to those steps repeat as well. The first bit 0, corresponding to the first step for 0.1, doesn’t repeat.
3You should find that this has an infinitely repeating binary representation, even though its decimal representation requires just one decimal place! Since computers have a finite amount of memory, this infinite sequence of bits needs to be truncated, and so the 0.1 stored in a Python program isn’t exactly 0.1, but it is close.
CSC165H1, Winter 2022 CSC165H1: Worksheet 10—Number Representations (Partial Solutions)
4. Infinite geometric series.
Given an infinite repeating binary representation, how can we verify that it is correct? To do this, we need to be
able to sum an infinite geometric series, using the following formula (valid for all a, r ∈ R when |r| < 1):4 ∞ ar
(a) As a warm-up, use the formula to verify that (0.1)2 = 1. You’ll need to determine the appropriate values for a and r; writing out the first few terms in the summation may be helpful.
ari = 1 − r i=1
(0.11)2 = 12 + 41 + 81 + . . .
(b) Now, show that (0.00011)2 = 1 . This is a bit more complex: to find the a and r, write out the first few terms 10
in the summation, group the terms into pairs, and pull out common factors (powers of 1 ). 24
1 11 11 1 (0.00011)2 = 24 +25 + 28 +29 + 212 +213 ...
1 1 1 1 1 1
=24 1+2 +28 1+2 +212 1+2 +...
1 3 12 3 13 3
=24 ·2+ 24 ·2+ 24 ·2+...
= ∞ 3 1 i
(wherea= ,r= ) 2 24
24 (multiplying by 24 )
= 2 24 1−1
= 1.5 15 = 0.1
4Note that this version starts with i = 1. If we started from i = 0, the right-hand side would be a instead. 1−r
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com