Binary Representation of Numbers

From CDS 130

Jump to: navigation, search

The binary representation of numbers

Contents

  1. Objectives
  2. Motivation
  3. Priming questions
  4. Notes
    1. Overview
    2. Representations of numbers
    3. Exponent Notation Review
    4. Decimal Numbers
    5. Decimal to Decimal
    6. Binary to Decimal Example
    7. Decimal to Binary
    8. Decimal to Binary Example
    9. Binary Patterns
  5. Questions
    1. Why Binary?
    2. Notation
    3. Decimal-to-binary conversion
    4. Binary-to-decimal conversion
    5. Decimal-to-binary conversion
    6. Binary-to-decimal conversion
    7. Binary and non-binary people
    8. Ratio of numbers with exponents
    9. Exponents
    10. Exponents
    11. Exponents
    12. Powers of Two
    13. Powers of two
    14. Bases
    15. Bases
    16. Bases
    17. Ambiguous base
    18. Lighthouse revisited
    19. The 20 Questions game
    20. Other questions
  6. Activities
    1. Guess-based approach for decimal to binary
    2. The Bubble Experiment
    3. Scoreboard
      1. Version 1
      2. Version 2
      3. Version 3
      4. Version 4
    4. Powers of Two
  7. Resources

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 vice-versa, 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 and 1 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 as 1101 in base 2 (binary).

4.3. Exponent Notation Review

  • 20 is "shorthand" for 1
  • 21 is "shorthand" for 2
  • 22 is "shorthand" for 2·2
  • 100 is "shorthand" for 1
  • 101 is "shorthand" for 10
  • 102 is "shorthand" for 10·10

4.4. Decimal Numbers

Before we can understand binary numbers, we need to review how decimal numbers work.

In decimal, 1472 means

  • 2 - is in the ones place so multiply it by 1 = 100
  • 7 - is in the tens place so multiply it by 10=101
  • 4 - is in the one-hundreds place so multiply it by 100=102
  • 1 - is in the one-thousands place so multiply it by 1000=103; add it to all of the numbers above

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.
Step 1: Create a table with the number in the first row.
1 4 7 2
103 102 101 100
1·103 4·102 7·101 2·100
1000 400 70 2
Step 2: Write down the powers of 10, increasing from right to left, in the second row.
1 4 7 2
103 102 101 100
1·103 4·102 7·101 2·100
1000 400 70 2
Step 3: Multiply the values in the first row with the values below it in the second row. Place the values in the third row.
1 4 7 2
103 102 101 100
1·103 4·102 7·101 2·100
1000 400 70 2
Step 4: Do the math in the third row and put values in the fourth row. Add all values in the fourth row to get an answer. Answer: 1000+400+70+2 = 1472.
1 4 7 2
103 102 101 100
1·103 4·102 7·101 2·100
1000 400 70 2

4.6. Binary to Decimal Example

Step 1: Create a table with a binary number to be converted to decimal in the first row.
1 1 0 1
23 22 21 20
1·23 1·22 0·21 1·20
8 4 0 1
Step 2: Write down the powers of two in the second row.
1 1 0 1
23 22 21 20
1·23 1·22 0·21 1·20
8 4 0 1
Step 3: Multiply the values in the first row with the values below it in the second row. Place the values in the third row.
1 1 0 1
23 22 21 20
1·23 1·22 0·21 1·20
8 4 0 1
Step 4: Do the math in row 3 and put values in row 4. Add all values in row 4 to get answer. Answer: 8+4+0+1=13.
1 1 0 1
23 22 21 20
1·23 1·22 0·21 1·20
8 4 0 1

4.7. Decimal to Binary

In this module, two algorithms were given.

  1. An algorithm for interpreting the symbols 0, 1, ..., 9 placed side-by-side, e.g., 1472.
  2. 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 ("guess-based") algorithm to determine the binary representation of a decimal number:

  1. Put a 1 in the right-most box in top row and zeros in all other boxes.
  2. Compute decimal representation.
  3. If decimal representation of guess is too small, put a 1 in the next right-most box in top row and zeros in all other boxes.
  4. Repeat steps 2.-3. until guess is too large.

4.8. Decimal to Binary Example

First guess. Answer: 0+0+0+1=1, which is smaller than 16, so continue.
0 0 0 1
23 22 21 20
0·8 0·4 0·2 1·1
0 0 0 1
Second guess. Answer: 0+0+2+0=2, which is smaller than 16, so continue.
0 0 1 0
23 22 21 20
0·8 0·4 1·2 0·1
0 0 2 0
Third guess. Answer: 0+4+0+0=4, which is smaller than 16, so continue.
0 1 0 0
23 22 21 20
0·8 1·4 0·2 0·1
0 4 0 0
Fourth guess. Answer: 8+0+0+0=8, which is smaller than 16, so continue.
1 0 0 0
23 22 21 20
1·8 0·4 0·2 0·1
8 0 0 0
Fifth guess (note that we needed to add another column on the left). Answer: 16+0+0+0+0=16 - equal to 16, so done.
1 0 0 0 0
24 23 22 21 20
1·16 1·8 0·4 0·2 0·1
16 0 0 0 0


  • 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 in-class 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 2N possible binary patterns. In the first case, N=2 and there were 22=4 possible patterns. In the second case, N=3 and there were 23=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 210 = 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?

5.3. Decimal-to-binary conversion

What is the decimal representation of the binary number 0101?

5.4. Binary-to-decimal conversion

What is the binary representation of the decimal number 31?

5.5. Decimal-to-binary conversion

What is the number 77 in binary?

5.6. Binary-to-decimal conversion

What is the number 10101 in decimal?

5.7. Binary and non-binary 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 23 isn't just one half of 26?

5.9. Exponents

We learned in class that 28 is 32 times larger than 23. How many times larger than 26 is 211?

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: (2x)(23)(24)(25) = 210

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: 217/2x = 25

A. x = 22
B. x = 10
C. x = 8
D. x = 12
E. None of the above

5.12. Powers of Two

210 divided by 23

A. 2-12
B. 27
C. 2-7
D. 212
E. None of the above

5.13. Powers of two

210 multiplied by 23

A. 213
B. 2-13
C. 27
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?

5.20. Other questions

  1. Is it true that every number has a binary representation? And if so, is the binary representation of a number unique?
  2. How many patterns can be formed with a single bit?
  3. Is the pattern 0 1 different from the pattern 1 0?
  4. How many patterns can be formed from three bits?
  5. 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?
  6. What else (besides characters and integers) can be represented with bit patterns?
  7. Do some files contain bit patterns that represent things other than characters?
  8. Can the bit patterns that are used to represent characters represent other things in other contexts?
  9. Can 6827 be rewritten in base 10 notation?
  10. 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. Guess-based approach for decimal to binary

Work on these three questions for five minutes:

  1. What is the decimal number 31 in binary?
  2. What is your algorithm. That is, finish this sentence: "Repeat steps 2.-3. until guess is too large. If guess is too large, ??"
  3. Can you think of a more efficient algorithm (one that will require fewer calculations to get an answer)?

if you finish early, try the question on the next slide or start working on #Questions.

1 0 0 0 0 0
25 24 23 22 21 20
1·32 0·16 0·8 0·4 0·2 0·1
32 0 0 0 0 0

6.2. The Bubble Experiment

I used this activity to introduce the concept of unary numeral system and positional numeral system. At the beginning of class, I asked students to pair with their neighbors to form a group. Each group was given a pre-tailored bubble wrap. On each bubble sheet, I designed to have 9 bubbles in each row (10 rows on each bubble sheet). I challenged students to represent a decimal number by popping the bubbles. For example, I asked them "How would you represent 38 by popping the bubbles"? Students started popping the bubbles. One or two groups quickly raised their hands to show their results. What they did was pop 38 bubbles on the bubble sheet. I then asked them "what would you do if you are asked to represent 138"? It posed a challenge to them because there were not enough bubbles on the bubble wrap. I gave them a hint by asking "Are you familiar with the abacus"? I interacted with the students and asked them to briefly introduce the mechanism of an abacus. Having introduced the concept of positional notation of numbers, I asked students to represent 138 using the bubble sheet. Most groups correctly represented decimal number 138 by popping 1 bubble in the first row, 3 bubbles in the second row and 8 bubbles in the third row. They started understanding each bubble in the first row represents 1, each bubble in the second row 10, each bubble in the third row 100.

Next, I told students that in this positional notation, this is called base 10 and there are many other bases. I handed out pre-tailored bubble wraps to each group, with each row containing 7 bubbles. I asked them "In positional notation, what base number could this be"? There was confusion between base 7 and base 8. After explaining to them that each bubble in the first row represents 1; each bubble in the second row represents 8, and each bubble in the third row represents 64, I asked each group to represent 138 by popping the bubbles. Students were highly engaged, and they had fun popping the bubbles. Several groups were able to give the correct answer: 2 bubbles in the first row, 1 bubble in the second row and 2 bubbles in the third row. This is in fact the base 8 notation (2128) of 138. I then increased the difficulty of the activity by handing out new bubble sheets with each row containing only 4 bubbles. This was to show base-5 notation of numbers.

Finally, I gave them a strip of bubble sheets. On the bubble sheet, there was only one bubble on each row, and there were 8 rows. I asked them "What is the base number of this demonstration"? Most students correctly answered the question "It is base 2", and some students also pointed out that on the first row, each bubble represents 1; on the second row each bubble represents 2; on the third row each bubble represents 4...

With this activity, students began to understand binary number representation.

Sheng 18:40, 24 February 2011 (EST)

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

  • Unary numeral system
  • Positional numeral system
  • Different bases used in numbering
  • Interpretation of the base
  • Representation of numbers with different bases

6.3. Scoreboard

I used this activity prior to starting my lecture on the binary representation of numbers. Overall it went quite well. If I do it again, I will modify the images to that in version 3 it is more obvious at first glance that eight scoreboards are shown (some did not read or listen and thought that the entire image was the scoreboard).

About 80% of the groups were able to get the answer, and the solution was not obvious to those who had experience with binary because I just started the activity without even mentioning what the day's lecture was about.

One or two groups did not read the question carefully but heard me mention that version 4 was to be "greener" and then decided that being green meant developing a scoreboard that used less power as opposed to fewer bulbs. I have not decided if it is better to try to clarify this verbally the next time I give this problem or to let students make the mistake. Their mis-reading led to a possibly useful short discussion on how "green" could mean using less raw material and less power over the lifetime of the scoreboard.

And, as always, don't tell the students they are going to do an activity until right before you want them to start. (They stop listening when they hear activity and will miss the instructions. I am reminded of this daily.)

Weigel 17:25, 24 February 2011 (EST)

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 0-7 are shown.

Algorithm for converting view to a score:

  • The score is the number that most looks like the number drawn out by the lit bulbs.

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 0-7 are shown.

Algorithm for converting view to a score:

  • If the score is 0, the bottom bulb is lit.
  • The score is 1 if the second bulb from the bottom is lit.
  • The score is 2 if the third bulb from the bottom is lit, ...,
  • the score is 7 if the top bulb is lit.
A scoreboard with eight vertical bulbs is shown in eight different configurations.
A scoreboard with eight vertical bulbs is shown in eight different configurations.


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:

  • Same as Version 2 except when two lights are lit, add their values (given by the Version 2 scoreboard) together to get the score.
A scoreboard with six bulbs is shown in eight possible configurations.
A scoreboard with six bulbs is shown in eight possible configurations.

6.3.4. Version 4

Work on this with one or two other students for about 15 minutes.

  1. 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.
  2. 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 0-7. 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).

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 = 215). 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 = 20), 2 grains of rice at the end of your first day of work (i.e., 2 = 21), 4 grains of rice at the end of your second day of work (i.e., 4 = 22), 8 grains of rice at the end of your third day of work (i.e., 8 = 23) 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

  1. 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)
  2. 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!)
  3. 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 1-hour youTube video explaining basic Computer Science topics, including binary numbers, to grade-school students: [9].
  • Historical note - One of the co-inventors 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."

Personal tools