Binary Representation of Numbers
From CDS 130
1. Objectives
 To understand why the binary representation of numbers is important
 To understand different ways of representing numbers including base 10 and base 2
 To be able to convert from binary to decimal and decimal to binary
 To be able to implement several algorithms
2. Motivation
 Understanding how computers represent numbers is important for solving science problems with computation.
 You may think of a digital computer as being composed of many, many on (represented numerically as the number 1) and off (represented numerically as the number 0) switches. In order to understand how a computer works, you must understand the binary representation of numbers.
 Math done on (almost all) computers is in binary.
 Numerical (roundoff) errors in computers are caused by the way numbers are represented in a computer's memory.
 To convert from binary to decimal and viceversa, you need to implement an algorithm. Much of scientific computing involves the development of algorithms to solve problems.
3. Priming questions
 How many ways can you represent the decimal number 10? (For example, hold up ten fingers, the word "sawbuck", etc.)
 Every medical doctor is required to understand the cell before they enroll in medical school. How often do you think a primary care physician thinks about cell during their work day? Same question for the neurologist and neuron.
 Moses lived in ancient Egypt ca. 3500 years ago. He herded 138 sheep in the wilderness. Suppose back then there wasn't a numbering system (e.g., decimal symbols 0, 1, ... 9). If you were Moses, how do you count the number of sheep he herds, and how do you communicate the number to his wife?
 You are a lighthouse operator and you would like to communicate a number to someone in the distance. You do not have a phone or internet connection. So you decide to turn your light on and off. So you sit down and devise a scheme with your friend that translates light on/off to a number. As a group, devise a "code" that allows you to communicate any number between one and one million. Unfortunately, your light switch will break after 100 uses. After 5 minutes of discussion I will ask a few groups to give their code.
4. Notes
4.1. Overview
A key concept emphasized throughout this section is the algorithm.
4.2. Representations of numbers
 On paper, virtually all numbers are written as combinations of the ten decimal symbols
0
1
2
3
4
5
6
7
8
9
.  Numbers represented with combinations of the ten decimal numbers are said to be numbers in base 10.
 On computer memory, virtually all numbers are written as combinations of two symbols (e.g.,

and+
, off and on, down and up, 0 and 1).  Numbers represented with combinations of the two symbols
0
and1
are said to be numbers in base 2.  Important: Any number that you can represent in base 10 can be represented in base 2.
 For example, the base 10 (decimal) number
13
is written as1101
in base 2 (binary).
4.3. Exponent Notation Review


Comment  

Many people forget the rule for multiplying or dividing numbers represented as exponents. Here is how to figure the rule out on your own:

4.4. Decimal Numbers
Before we can understand binary numbers, we need to review how decimal numbers work. 
In decimal, 1472 means
The result is 2·1 + 7·10 + 4·100 + 1·1000 = 1472 
4.5. Decimal to Decimal
 Before trying to convert binary (base 2) numbers to decimal (base 10) numbers, let's break the above process outlined for decimal number into four steps.




4.6. Binary to Decimal Example




4.7. Decimal to Binary
In this module, two algorithms were given.
 An algorithm for interpreting the symbols
0
,1
, ...,9
placed sidebyside, e.g.,1472
.  An algorithm for converting from base 2 to base 10 (binary to decimal)
Now we need an algorithm for converting from base 10 to base 2 (decimal to binaryl).
Question: What is the binary representation of the decimal number 16
? (Hint  think about how you could work backwards starting with the fourth row in table.)
Answer: Use a ("guessbased") algorithm to determine the binary representation of a decimal number:
 Put a
1
in the rightmost box in top row and zeros in all other boxes.  Compute decimal representation.
 If decimal representation of guess is too small, put a
1
in the next rightmost box in top row and zeros in all other boxes.  Repeat steps 2.3. until guess is too large.
4.8. Decimal to Binary Example





 What steps should you follow if the guess is too large?
 That is, what is your algorithm for the case where a guess is larger than the target number?
 You will consider this question in either the homework or in a inclass activity.
4.9. Binary Patterns
Suppose that you were told that you have a deck of playing cards with either the numbers 0 or 1 on it. If you play a game with in which you are dealt two cards, how many possible hands could you have? To determine this, write out all possible patterns.
0 0 0 1 1 0 1 1
So there are a total of four possible hands that you could be dealt. Note that list of patterns above corresponds to the decimal numbers 0, 1, 2, and 3.
What happens if you were dealt three cards. How many possible hands could you have? The first hand would be
0 0 0
and the last hand would be
1 1 1
Thus, there are a total of eight possible hands, because you can represent the decimal numbers 0, 1, 2, 3, 4, 5, 6, and 7 with three 0's and 1's.
In general, if you are asked to create a list of N
0's and 1's, there are a total of 2^{N} possible binary patterns. In the first case, N=2
and there were 2^{2}=4 possible patterns. In the second case, N=3
and there were 2^{3}=8 possible patterns.
Note that in the above example, we could have said that instead of playing cards, you were asked how many possible configuration there were for N
light switches that could be either on or off. The answer is the same  just associate on with 1 and off with 0. If there are two light switches, there are 4 possible configurations. If there are three light switches there are 8 possible configurations. If there are 10 light switches, there are 2^{10} = 1024 possible configurations.
5. Questions
5.1. Why Binary?
List reasons of why the binary system is used to represent numbers in computer memory.
5.2. Notation
Why do we sometimes see 011
written for the binary representation of the decimal number 3
in binary instead of just 11
?
Answer 


5.3. Decimaltobinary conversion
What is the decimal representation of the binary number 0101?
5.4. Binarytodecimal conversion
What is the binary representation of the decimal number 31?
5.5. Decimaltobinary conversion
What is the number 77 in binary?
5.6. Binarytodecimal conversion
What is the number 10101 in decimal?
5.7. Binary and nonbinary people
Explain the following quote: "There are only 10 people in the world, those who understand binary and those who do not."
5.8. Ratio of numbers with exponents
Explain why 2^{3} isn't just one half of 2^{6}?
5.9. Exponents
We learned in class that 2^{8} is 32 times larger than 2^{3}. How many times larger than 2^{6} is 2^{11}?
A. 8 times larger 
B. 16 times larger 
C. 32 times larger 
D. 64 times larger 
5.10. Exponents
What is the value of x in the following equation: (2^{x})(2^{3})(2^{4})(2^{5}) = 2^{10}
A. x = 2 
B. x = 12 
C. x = 2 
D. x = 12 
E. None of the above 
5.11. Exponents
What is the value of x in the following equation: 2^{17}/2^{x} = 2^{5}
A. x = 22 
B. x = 10 
C. x = 8 
D. x = 12 
E. None of the above 
5.12. Powers of Two
2^{10} divided by 2^{3}
A. 2^{12} 
B. 2^{7} 
C. 2^{7 } 
D. 2^{12} 
E. None of the above 
5.13. Powers of two
2^{10} multiplied by 2^{3}
A. 2^{13} 
B. 2^{13} 
C. 2^{7} 
D. 2^{7} 
E. None of the above 
5.14. Bases
What is the decimal (base 10) number 315, written in binary (base two)?
A. 100111011 
B. 101111011 
C. 100111001 
D. 101111010 
E. None of the above 
5.15. Bases
What is the binary (base 2) number 100111111, written in decimal (base 10)?
A. 318 
B. 319 
C. 320 
D. 321 
E. None of the above 
5.16. Bases
What is the binary (base 2) number 100010001, written in decimal (base 10)?
A. 272 
B. 219 
C. 256 
D. 273 
E. None of the above 
5.17. Ambiguous base
Suppose you read the number 1011110001
in a notebook. Is the number binary or decimal? Is one more likely than the other?
5.18. Lighthouse revisited
You have a switch with three options: red, green, and blue. The light may not be turned off. Develop a "code" that uses all three options.
5.19. The 20 Questions game
Let’s say that your classmate chooses an integer between 1 and 1,000,000 (inclusive). By asking your classmate no more than 20 simple questions in which they must answer either yes or no, it’s possible for you to determine the exact integer she chose. How?
Answer 

Algorithm:
Most students asked a variety of questions of which the "is it greater than" question in the algorithm above was included (the other questions were often "is the number prime?" or "is the number even?"). If you were to implement this algorithm in a computer program, it would be easier if you always asked the same question. It is also easier to prove that you would be able to guess the correct number in at worst 20 questions if the question is always the same. Note that this approach to guessing is a fundamental algorithm in computer programs [1]. It is also a good algorithm to keep in mind when trying to figure out where an error is located in your computer program. Suppose that you feed a list of 1,000,000 commands into a computer program. The computer responds "one of the commands is not valid". To figure out which command is invalid, you could try all of the commands onebyone starting with the first. On average, finding the invalid command would take 500,000 tries. With the approach given for this problem, you would be able to figure out the invalid command in, at most, 20 commands. That is, you would feed the first 1/2 of the commands into the computer. If the computer said "all of the commands are valid", then you would know that the invalid command is one of the other 1/2 of the commands. Approach to proving that the algorithm will get the correct answer:
Suppose the problem stated asked for numbers between 1 and 2 inclusive instead of 1 and 1,000,000.
The middle value is 1.5, so ask "is the number greater than 1.5?" If the response is yes or no, you know the answer after asking at most Suppose the problem asked for number between 1 and 4 inclusive.
The middle value is 2.5. Is the number greater than 2.5? If the answer is no, you know the value is between
From before, you know that this list requires at worst one guess. Therefore, if the worst case for guessing the numbers 1 through 4 is Next, double the length of the possible numbers to eight:
First ask "is the number greater than 4.5? If no, then you know the number is in the list
From before, you know that this list requires at worst two guesses. Therefore, the worst case for guessing the numbers 1 through 8 is Summary of results:
In inspecting the above summary, a pattern appears: Given N guesses, you can always figure out the that number someone picked in a list of 2^{N} numbers. The original question asked about the numbers 1 through 1,000,000. Note that 2^{20} = 1,048,576. This means that with 20 guesses, you could figure out the number someone picked in a list of 1,048,576 numbers. There is a second method for solving this problem. 1,000,000 has the binary representation 
5.20. Other questions
 Is it true that every number has a binary representation? And if so, is the binary representation of a number unique?
 How many patterns can be formed with a single bit?
 Is the pattern 0 1 different from the pattern 1 0?
 How many patterns can be formed from three bits?
 In the past, some computers used 16 bits to form memory addresses. Assuming no special tricks (which such limited machines often used), how many bytes maximum could be held in main storage?
 What else (besides characters and integers) can be represented with bit patterns?
 Do some files contain bit patterns that represent things other than characters?
 Can the bit patterns that are used to represent characters represent other things in other contexts?
 Can 682_{7} be rewritten in base 10 notation?
 An apple vendor has 1000 apples and 10 empty boxes. He asks his son to place all the 1000 apples in all the 10 boxes in such a manner that if he asks for any number of apples from 1 to 1000, his son should be able to pick them in terms of boxes. How did the son place all the apples among the 10 boxes, given that any number of apples can be put in one box.
6. Activities
6.1. Guessbased approach for decimal to binary
Work on these three questions for five minutes:
if you finish early, try the question on the next slide or start working on #Questions. 

6.2. The Bubble Experiment
Instructions: You are given several bubble wraps in class. On each bubble wrap sheet, there are several rows of bubbles. By working with the bubbles you are able to generate a number. Pair up with a partner in class, and try to figure out how to generate numbers requested by the instructor. Explain how the number is represented. Objectives This experiment is to familiarize you with

6.3. Scoreboard
A scoreboard needs to display the numbers 0 through 7. An initial design was created and is shown in Version 1.
6.3.1. Version 1
The Version 1 scoreboard uses 15 bulbs. The eight configurations corresponding to the numbers 07 are shown. Algorithm for converting view to a score:

6.3.2. Version 2
The Version 1 display has been declared "not green" because it uses so many light bulbs. An alternative scoreboard is proposed that has eight bulbs aligned vertically. The configurations corresponding to the numbers 07 are shown. Algorithm for converting view to a score:

6.3.3. Version 3
The Version 2 display has been declared "not green enough". A new algorithm is presented that requires three fewer bulbs and can still represent the number 0 through 7. Algorithm for converting view to a score:

6.3.4. Version 4
Work on this with one or two other students for about 15 minutes.
 Think of an algorithm that allows fewer lights to be used than that for Version 3 given the restrictions:
 Lights must be arranged in a straight line;
 Lights may only be on or off and there is not an option for different colors when on; and
 Lights can't be set up to "blink" on and off to indicate a score. For example, a flashing light may not be used to indicate that the score is three.
 Think of an algorithm that allows you to use fewer lights without the above restrictions.
Write down your algorithm (in words!) and draw a diagram showing the configurations for the numbers 07
. At the start of the next class, we will test how easy your algorithm is to follow by asking if students can read your algorithm and determine the score given a scoreboard with no labels to indicate the score.
Turn in your notes at the end of class (this will count as part of your Quiz #1 score and will be graded primarily on participation).
Discussion 

The intention of this activity was to show that the binary representation of numbers is a natural consequence of the simple problem of how to count using a minimal number of objects that can be in one of two states. You can represent the eight digits, 0 through 7 using only three light bulbs. With three bulbs in either the on or off position, you can create 2^{3} unique patterns. A possible set of pattern/score associates are given below.
If you replace the word

6.4. Powers of Two
Background
According to Producer’s Rice Mill [2] there are over 29,000 grains of long grain white rice in a pound of long grain white rice. So, since 32,768 is greater than 29,000, let’s assume that there are actually 32,768 grains of long white rice per pound of long grain white rice. (Note that 32,768 = 2^{15}). On 14 September 2010, a 50 pound bag of long grain white rice was selling for $68.99 on Amazon [3].
Now let’s further assume that you’re seeking employment at Best Buy, and that Best Buy offers you a job paying $12.00 per hour. You decide to make the following deal with Best Buy’s hiring manager. You ask to be paid in grains of rice rather than in dollars for your first month of employment, as follows: you will be paid 1 grain of rice as a signing bonus (that is, on "day zero" before you begin work, i.e., 1 = 2^{0}), 2 grains of rice at the end of your first day of work (i.e., 2 = 2^{1}), 4 grains of rice at the end of your second day of work (i.e., 4 = 2^{2}), 8 grains of rice at the end of your third day of work (i.e., 8 = 2^{3}) and so on, for a month (for 30 total days, i.e., you’ll be paid in rice grains for the last time at the end of your 30th day of work). After your first 30 days with Best Buy, you’ll agree to be paid at $12.00 per hour for the remainder of your employment with Best Buy.
Best Buy’s hiring manager thinks, "Hey, this is a great deal for us! I get to pay this new employee in grains of rice for the first month! I’m going save Best Buy some serious money, which of course will result in my promotion to a comfortable desk job back in Richfield, Minnesota" (Best Buy’s corporate headquarters).
Questions
 If you get paid 1 grain of rice as a signing bonus before starting work, 2 grains of rice at the end of your first day of work, 4 grains of rice at the end of your second day of work and so on, up through the end of your 30th day of work, how many pounds of rice will you end up being paid all together? (ans: you’ll end up being paid 2,147,483,647 grains of rice total, which equals 65,536 pounds of rice)
 How much money will you therefore be paid (at the going rate of $68.99 per 50 pounds of rice) at the end of your first month? (ans: 65,536 pounds of rice, equals 1,310.72 when divided by 50, which equals $90,426.57 when multiplied by $68.99 per 50 pound bag. Not bad for your first month on the job!)
 Will Best Buy’s hiring manager get promoted? (ans: Probably not. But, YOU might get promoted, having demonstrated a keen ability to make money!)
7. Resources
 "The Definitive Guide to How Computers Do Math" [4].
 An explanation of the binary number system: [5].
 Wikipedia entry for binary numbers: [6].
 Explanation for motivation for using bits: [7].
 Another counting system [8].
 A 1hour youTube video explaining basic Computer Science topics, including binary numbers, to gradeschool students: [9].
 Historical note  One of the coinventors of the Calculus was fond of using binary [10]:
But instead of the progression of tens, I have for many years used the simplest progression of all, which proceeds by twos, having found that it is useful for the perfection of the science of numbers.
 Classic Joke: "There are only 10 types of people in this world: those who understand binary and those who do not."