Binary Representation of Numbers

From ComputingForScientists

Jump to: navigation, search

Contents

  1. Representations of Numbers
  2. Decimal to Decimal
  3. Binary to Decimal
  4. Decimal to Binary
  5. Alternative Decimal to Binary Algorithm
  6. Counting Patterns
  7. Problems
    1. Ambiguous Base
    2. Notation
    3. Notation
    4. Binary to Decimal
    5. Binary to Decimal
    6. Binary to Decimal
    7. Binary to Decimal
    8. Binary to Decimal
    9. Binary to Decimal
    10. Decimal to Binary
    11. Decimal to Binary
    12. Decimal to Binary
    13. Decimal to Binary
    14. Decimal to Binary
    15. Decimal to Binary
    16. Decimal to Binary
    17. Counting Patterns
    18. Counting Patterns
    19. Counting Patterns
    20. Counting Patterns
    21. Counting Patterns
    22. Counting Patterns
    23. Counting Patterns
    24. Counting Patterns
    25. Counting Patterns
    26. Counting Patterns
    27. Counting Patterns
    28. Counting Patterns
  8. Activities
    1. Guess-based Approach for Decimal to Binary
    2. Lighthouse
    3. Scoreboard
      1. Version 1
      2. Version 2
      3. Version 3
      4. Version 4
    4. 20 Questions
    5. Addition Algorithm
  9. Resources
  10. Review: Exponential Notation

1. Representations of Numbers

On paper, nearly all numbers are written as combinations of the ten decimal symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Numbers represented with combinations of the ten decimal symbols are said to be numbers in base 10.

Numbers represented as a list of the two symbols 0 and 1 are said to be numbers in base 2 (binary). For example, the base 10 (decimal) number 13 is written as 1101 in base 2. To remove ambiguity, binary numbers are sometimes followed with a subscript of 2, e.g., 11012.

In a digital computer, numbers are represented as combinations of two symbols, 0 and 1. A digital computer may be thought of as machine that stores in its memory numbers as a sequence of 1s and 0s, has an input that is a series of "on" (represented symbolically as 1) and "off" (represented symbolically as 0) switches, and has an output that is a series of light bulbs that are either on or off. In the Transistors section, the reason why numbers are represented as only two symbols will be given.

In this section, methods are described that allow for the conversion of numbers from the human-familiar base 10 to the computer-used base 2.

2. Decimal to Decimal

Before showing how a list of binary numbers are interpreted, recall how a list of decimal numbers are interpreted. The decimal number 1492 is interpreted as having four components that are added together:

  • 2 - is in the ones place, so multiply it by 1 = 100
  • 9 - 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

Adding all of the numbers after multiplication of a power of ten gives 2·1 + 9·10 + 4·100 + 1·1000 = 1492.

This process for interpreting a decimal number can be written in five steps.

Step 1: Create a table with the number in the first row.
1 4 9 2
103 102 101 100
1·103 4·102 9·101 2·100
1000 400 90 2
Step 2: Write down powers of 10, increasing from right to left and starting with 100 in the second row.
1 4 9 2
103 102 101 100
1·103 4·102 9·101 2·100
1000 400 90 2
Step 3: Write multiplication of the values in the first row with the values in the second row in the third row.
1 4 9 2
103 102 101 100
1·103 4·102 9·101 2·100
1000 400 90 2
Step 4: Do the multiplication in the third row and the result in the fourth row.
1 4 9 2
103 102 101 100
1·103 4·102 9·101 2·100
1000 400 90 2

Step 5: Add all values in the fourth row to get an answer. Answer: 1000+400+90+2 = 1492.

3. Binary to Decimal

The same algorithm may be used to convert a binary number to decimal. The only difference is the second row has powers of two instead of powers of ten.

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 in the second row. Place the result 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 multiplication in the third row and put result in the fourth row.
1 1 0 1
23 22 21 20
1·23 1·22 0·21 1·20
8 4 0 1

Step 5: Add all values in the fourth row to get an answer. Answer: 8+4+0+1=13.

4. Decimal to Binary

In principle the algorithm used to convert binary to decimal can be used to do the inverse conversion - decimal to binary - by guessing the binary representation of a desired decimal number and then using the five steps of the binary to decimal algorithm to determine if the guess is correct. Randomly guessing and checking is inefficient, however. After attempting a few guesses, one would probably discover a more efficient algorithm similar to what follows.

Decimal to Binary Algorithm

First, find a binary number whose decimal representation is equal to or less than the desired decimal number by working from left to right in the top row:

  1. Write a 1 in the right-most column of the top row of a table and zeros in all other columns;
  2. Compute the decimal representation of this number using the binary to decimal algorithm;
  3. If the decimal value is too small, put a 1 in the next column to the left of the previous guess and zeros in all other columns; and
  4. Repeat steps 2.-3. until the decimal value is greater than or equal to the desired value.

Second, if after the last step the decimal value is greater than the desired value, find the exact value by working from right to left:

  1. Write down the last tested binary number that corresponded to a decimal number smaller than the desired number and place a one in the column to its right;
  2. Compute the decimal representation of this new number; and
    • If the decimal value is too large, replace this one with a zero and put a one in the next most column to the right;
    • If the decimal value is too small, keep this one and place a one in the next column to the right of the previous one that was entered into the table.
  3. Repeat step 2. until the decimal value is equal to the desired value.

Example

Determine the binary representation of the decimal number 16.

First, follow the right-to-left steps:

First guess: 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: 0⁣+0⁣+2⁣+0⁣=2 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: 0⁣+4⁣+0⁣+0⁣=4 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: 8⁣+0⁣+0⁣+0⁣=8 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: 16⁣+0⁣+0⁣+0⁣+0⁣=16, so done.
1 0 0 0 0
24 23 22 21 20
1·16 0·8 0·4 0·2 0·1
16 0 0 0 0

In this example, only the right-to-left steps were required because the desired value was found (as opposed to a value larger than the desired value). Note that an additional column was added for the fifth guess.

Example

Determine the binary representation of the decimal number 21.

In this case, we would follow the same right-to-left steps in the previous example and arrive at the fifth guess.

Sixth guess: 32⁣+0⁣+0⁣+0⁣+0⁣+0⁣=32 is too large.
0 1 0 0 0 0
25 24 23 22 21 20
0·32 1·16 0·8 0·4 0·2 0·1
0 16 0 0 0 0

Because the fifth guess was too small, we place a one in the column to the left of the last guess and zeros in all other columns.

Sixth guess: 32⁣+0⁣+0⁣+0⁣+0⁣+0⁣=32 is too large.
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


Because the sixth guess was too large, we must begin to work from right to left. The next step is to build on the guess before the sixth guess by placing a 1 in the box to the right of the existing 1. This is shown as the seventh guess.

Seventh guess: 0⁣+16⁣+8⁣+0⁣+0⁣+0⁣=24, which is too large.
0 1 1 0 0 0
25 24 23 22 21 20
0·32 1·16 1·8 0·4 0·2 0·1
0 16 8 0 0 0


Because the seventh guess was too large, for the eighth guess, replace the last 1 entered with a 0 and place a 1 in the next column to the right.

Eighth guess: 0⁣+16⁣+0⁣+4⁣+0⁣+0⁣=20, which is too small.
0 1 0 1 0 0
25 24 23 22 21 20
0·32 1·16 0·8 1·4 0·2 0·1
0 16 0 4 0 0


Ninth guess: 0⁣+16⁣+0⁣+4⁣+2⁣+0⁣=22, which is too large.
0 1 0 1 1 0
25 24 23 22 21 20
0·32 1·16 0·8 1·4 1·2 0·1
0 16 0 4 2 0


The binary representation of 21 is 010101 or simply 10101. Note that it is not necessary to include additional 0s to the left of the binary number unless the number of bits is specified and the 0s are needed.

Tenth guess: 0⁣+16⁣+0⁣+4⁣+0⁣+1⁣=21, which is the desired result.
0 1 0 1 0 1
25 24 23 22 21 20
0·32 1·16 0·8 1·4 0·2 1·1
0 16 0 4 0 1


5. Alternative Decimal to Binary Algorithm

A algorithm that is more efficient than both randomly guessing and the left-to-right and right-to-left algorithm is

  1. Let A be the given decimal number.
  2. Compute the difference between A and the largest power of two (i.e., 1, 2, 4, 8, 16, ....) that is less than or equal to it. Rename A to be this difference.
  3. Repeat 2. using the computed difference until the difference is zero. The binary representation of the decimal number is obtained by placing ones in the columns associated with all of the powers of two that were used for subtraction in step 2.

Example

Answer: 16 + 4 + 1 = 21, which is the desired result.
0 1 0 1 0 1
25 24 23 22 21 20
0·32 1·16 0·8 1·4 0·2 1·1
0 16 0 4 0 1

Convert the decimal number 21 to binary.

The largest power of two that is less than or equal to A = 21 is 16, and 21 - 16 = 5, so set A = 5. The largest power of two that is less than or equal to 5 is 4, and 5 - 4 = 1, so set A = 1. The largest power of two that is less than or equal to 1 is 1, so A = 1 - 1 = 0.

In this example, the powers of two that were used were 24 (=16), 22 (= 4), and 20 (=1). The columns in which these powers occur have a one in the top row.

To the right, the powers of 2 that were used are indicated in bold and in the row above them, a 1 was entered. The binary representation of 21 is the top row of the table with all other values set to 0. The answer has been checked by following the binary to decimal steps.

6. Counting Patterns

A list of zeros and ones is called a bit pattern. The number of unique bit patterns, Npatterns, that can be formed from a bit pattern length N increases as the length of the list increases. For example, for a list of length two, the unique bit patterns are 00, 01, 10, and 11, and Npatterns = 4.

Example

How many unique bit patterns can be formed with three bits?

One possible bit pattern is 000. Another possible bit pattern is 111. To determine all of the other possible bit patterns, we could first write down all of the unique patterns for the first two digits along with the possibilities for the last digit:

00: Last digit could be 0 or 1, e.g., 000, 001
01: Last digit could be 0 or 1, e.g., 010, 011
10: Last digit could be 0 or 1, e.g., 100, 101
11: Last digit could be 0 or 1, e.g., 110, 111

The total number of unique patterns is thus 8. There is a simpler way of writing down all of the possible bit patterns. Note that each of the 8 bit patterns has a decimal representation. The first, 000 corresponds to decimal 0. The last, 111, corresponds to decimal 7. So, to determine the patterns, write out the binary pattern for the decimal numbers 0 through 7:

0 000    1 001    2 010    3 011    5 101    6 110    7 111

More generally, for bit pattern of length N, there are a total of

Npatterns = 2N

unique possible binary patterns. In the previous example, the bit pattern had a length of N = 3 and there were 23 = 8 unique possible bit patterns. The possible bit patterns had a decimal equivalent corresponding to the numbers 0 through 7.

In general, the number of unique patterns that can be formed by placing N symbols side-by-side is

Npatterns = SN,

where S is the number of unique symbols. In the case of binary, the number of unique symbols S is 2. In the case of decimal, the number of unique symbols S is 10, corresponding to the symbols 0, 1, ..., 9.

Example

A wall has 7 light switches that can be either up or down. How many unique configurations of light switches are possible?

This question is equivalent to "how many unique patterns can be formed with a list of seven 0's and 1's". The answer is

Npatterns = 27 = 128.

Alternatively, the bit pattern 1111111 corresponds to the decimal number 127, so there are 127 + 1 = 128 possible patterns.

Example

How many unique patterns can be formed with two decimal symbols placed side-by-side?

Npatterns = 102 = 100

The patterns are 00, 01, 02, ..., 99. Note that the number of patterns (100) is equal to the the numeric value of the last pattern (99) plus 1.

7. Problems

7.1. Ambiguous Base

Suppose you read the number 1011110001 in a notebook. Is the number binary or decimal?

7.2. Notation

Why do we sometimes see 011 written for the binary representation of the decimal number 3 in binary instead of just 11?

7.3. Notation

Explain the statement that "There are only 10 people in the world, those who understand binary and those who do not."

7.4. Binary to Decimal

Convert the binary number 100111111 to a decimal number.

A. 318
B. 319
C. 320
D. 321
E. None of the above

7.5. Binary to Decimal

Convert the binary number 100010001 to a decimal number.

A. 272
B. 219
C. 256
D. 273
E. None of the above

7.6. Binary to Decimal

Convert the binary number 0101 to a decimal number.

7.7. Binary to Decimal

Convert the binary number 10101 to decimal.

7.8. Binary to Decimal

Convert the binary number 10111 to decimal.

7.9. Binary to Decimal

Convert the binary number 00111 to decimal.

7.10. Decimal to Binary

Convert the decimal number 31 to binary.

7.11. Decimal to Binary

Convert the decimal number 315 to binary.

A. 100111011
B. 101111011
C. 100111001
D. 101111010
E. None of the above

7.12. Decimal to Binary

Convert the decimal number 49 to binary.

7.13. Decimal to Binary

Convert the decimal number 77 to binary.

7.14. Decimal to Binary

Convert the decimal number 83 to binary.

7.15. Decimal to Binary

Convert the decimal number 99 to binary

7.16. Decimal to Binary

Convert the decimal number 103 to binary

7.17. Counting Patterns

How many unique patterns can be formed with a single bit?

7.18. Counting Patterns

How many unique patterns can be formed from three bits?

7.19. Counting Patterns

How many unique patterns can be formed by placing 9 decimal numbers side-by-side?

7.20. Counting Patterns

You are asked to give students in a class an identification pattern that is formed by placing two squares side-by-side. The square may be either red, green, or blue. What is the largest class size for which each student can be given an unique identification pattern?

7.21. Counting Patterns

An apple vendor has 1000 apples and 10 empty boxes. He asks his son to distribute the 1000 apples among the 10 boxes so that if a customer asks for any number of apples from 1 to 1000, his should be able to give the customer a set of boxes without needing modify the number of apples in any of the boxes. How many apples did the son place in each box?

7.22. Counting Patterns

How many unique patterns composed of four octal digits can be formed?.

7.23. Counting Patterns

You are in a room with a panel of 8 light switches that can be either up or down. How many possible configurations are there?

7.24. Counting Patterns

How many distinct combinations of zeros and ones can be made with

  • 2 bits
  • 4 bits
  • 7 bits
  • 8 bits

7.25. Counting Patterns

A hexidecimal digit may be any one of the following 16 symbols: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F. How many unique patterns composed of two hexidecimal digits can be formed? For example, one pattern is 00, and another pattern could be FF.

7.26. Counting Patterns

Can every decimal number has a binary representation? If so, is the binary representation of a number unique?

7.27. Counting Patterns

  1. Can 6827 be rewritten in base 10 notation?

7.28. Counting Patterns

A commonly used method for representing a number is base 16, which uses the symbols 0, 1, ..., 9, A, B, C, D, E, and F. The letter A corresponds to the decimal number 10. Give a situation in which this numbering system would have an advantage over binary or decimal.

8. Activities

8.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)?
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

8.2. Lighthouse

You are a lighthouse operator and you would like to communicate a single number to someone far away. You do not have a phone or internet connection. Devise a method that will allow you to communicate any number between one and one million using the light bulb. Unfortunately, your light switch will not function after being switched 100 times.

8.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 proposed and named Version 1.

8.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.
Score=0
Score=0
Score=1
Score=1
Score=2
Score=2
Score=3
Score=3
Score=4
Score=4
Score=5
Score=5
Score=6
Score=6
Score=7
Score=7


8.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.
Score = 0
Score = 0
Score = 1
Score = 1
Score = 2
Score = 2
Score = 3
Score = 3
Score = 4
Score = 4
Score = 5
Score = 5
Score = 6
Score = 6
Score = 7
Score = 7


8.3.3. Version 3

The Version 2 display has been declared "not green enough" (uses too many bulbs). A new algorithm is proposed 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.
Score = 0
Score = 0
Score = 1
Score = 1
Score = 2
Score = 2
Score = 3
Score = 3
Score = 4
Score = 4
Score = 5
Score = 5
Score = 6
Score = 6
Score = 7
Score = 7


8.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.

8.4. 20 Questions

Have a partner choose an integer between 1 and 1,000,000 (inclusive). Your task is to guess this number by asking 20 or fewer questions that may only be answered with "yes" or "no".

8.5. Addition Algorithm

Write down a set of steps that must be followed to perform the addition of two two-digit decimal numbers in the same style as the steps given for converting from decimal to binary and vice versa. Write out each step explicitly. Assume that the reader only knows how to add two decimal numbers, e.g., 9+9. Have your partner test your algorithm by following the steps exactly as written.

9. Resources

  • "The Definitive Guide to How Computers Do Math" [2]. This book delivers on its promise to be "... a modest attempt at introducing the basics of computer arithmetic in words that we can all understand.". It also covers advanced topics such as assembly language and building your own calculator.
  • An explanation of the binary number system and binary addition at the level of this chapter [3].
  • Wikipedia entry for binary numbers: [4].
  • Explanation for motivation for using bits: [5].
  • A compact counting alternative to vertical lines [6].
  • A 1-hour youTube video explaining basic computer science topics, including binary numbers, to grade-school students: [7].
  • Historical note - One of the co-inventors of the Calculus was fond of using binary [8]:
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.

10. Review: Exponential Notation

  • 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

The rule for multiplying or dividing numbers represented as exponents is easily forgotten. To "derive" the rule, first write a few typical fractions of exponents, expand out the exponents in the numerator and denominator, and then cancel terms. Finally, re-write the result in exponential notation:

$$\frac{2^4}{2^2} = \frac{2\cdot 2\cdot 2\cdot 2}{2\cdot 2} = 2\cdot 2 = 2^2$$

Based on inspection, it appears the rule could be

\(\frac{2^A}{2^B}=2^{A/B}\) because \(A/B = 4/2 = 2\)

or

\(\frac{2^A}{2^B}=2^{A-B}\) because \(A-B = 4-2 = 2\)

Try another example:

$$\frac{2^5}{2^2} = \frac{2\cdot 2\cdot 2\cdot 2\cdot 2}{2\cdot 2} = 2\cdot 2\cdot 2 = 2^3$$

Based on inspection, it appears the rule is not

\(\frac{2^A}{2^B}=2^{A/B}\) because \(A/B = 5/2 = 2.5\)

but is rather

\(\frac{2^A}{2^B}=2^{A-B}\) because \(A-B = 5-2 = 3\).

So it looks like the rule is to subtract the top exponent from the bottom exponent.


\(\frac{10^9}{10^6} = \)

A. 101.5
B. 103
C. 10-3
D. 1054

Explain why 23 isn't just one half of 26?


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

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

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

210 divided by 23

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

210 multiplied by 23

A. 213
B. 2-13
C. 27
D. 2-7
E. None of the above

Personal tools