Binary Representation of Numbers
From ComputingForScientists
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., 1101_{2}
.
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 1
s and 0
s, 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 humanfamiliar base 10 to the computerused 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 = 10^{0} 
9
 is in the tens place, so multiply it by 10 = 10^{1} 
4
 is in the onehundreds place, so multiply it by 100 = 10^{2} 
1
 is in the onethousands place, so multiply it by 1000 = 10^{3}
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.
1  4  9  2 

1  4  9  2 

10^{3}  10^{2}  10^{1}  10^{0} 
1  4  9  2 

10^{3}  10^{2}  10^{1}  10^{0} 
1·10^{3}  4·10^{2}  9·10^{1}  2·10^{0} 
1  4  9  2 

10^{3}  10^{2}  10^{1}  10^{0} 
1·10^{3}  4·10^{2}  9·10^{1}  2·10^{0} 
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.
1  1  0  1 

1  1  0  1 

2^{3}  2^{2}  2^{1}  2^{0} 
1  1  0  1 

2^{3}  2^{2}  2^{1}  2^{0} 
1·2^{3}  1·2^{2}  0·2^{1}  1·2^{0} 
8  4  0  1 
1  1  0  1 

2^{3}  2^{2}  2^{1}  2^{0} 
1·2^{3}  1·2^{2}  0·2^{1}  1·2^{0} 
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:
 Write a
1
in the rightmost column of the top row of a table and zeros in all other columns;  Compute the decimal representation of this number using the binary to decimal algorithm;
 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  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:
 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;
 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.
 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 righttoleft steps:
0  0  0  1 
2^{3}  2^{2}  2^{1}  2^{0} 
0·8  0·4  0·2  1·1 
0  0  0  1 
0  0  1  0 
2^{3}  2^{2}  2^{1}  2^{0} 
0·8  0·4  1·2  0·1 
0  0  2  0 
0  1  0  0 
2^{3}  2^{2}  2^{1}  2^{0} 
0·8  1·4  0·2  0·1 
0  4  0  0 
1  0  0  0 
2^{3}  2^{2}  2^{1}  2^{0} 
1·8  0·4  0·2  0·1 
8  0  0  0 
1  0  0  0  0 
2^{4}  2^{3}  2^{2}  2^{1}  2^{0} 
1·16  0·8  0·4  0·2  0·1 
16  0  0  0  0 
In this example, only the righttoleft 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 righttoleft steps in the previous example and arrive at the fifth guess. 

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. 

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 

Because the seventh guess was too large, for the eighth guess, replace the last 


The binary representation of 

5. Alternative Decimal to Binary Algorithm
A algorithm that is more efficient than both randomly guessing and the lefttoright and righttoleft algorithm is
 Let
A
be the given decimal number.  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. RenameA
to be this difference.  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
0  1  0  1  0  1 
2^{5}  2^{4}  2^{3}  2^{2}  2^{1}  2^{0} 
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 2^{4} (=16), 2^{2} (= 4), and 2^{0} (=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, N_{patterns}, 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 N_{patterns} = 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
N_{patterns} = 2^{N}
unique possible binary patterns. In the previous example, the bit pattern had a length of N = 3 and there were 2^{3} = 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 sidebyside is
N_{patterns} = S^{N},
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
N_{patterns} = 2^{7} = 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 sidebyside?
N_{patterns} = 10^{2} = 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?
Answer 

Without additional information, you cannot determine the answer. Binary numbers consist of 0s and 1s, so you may look at this number and say it is binary. Because there is no subscript after the number (2 for binary or 10 for decimal), there is no way of knowing for certain if the number is binary or decimal (or any other base). However, if the notebook was for a class related to computing, you may want to guess that it is a binary number. In addition, a randomly selected decimal number is unlikely to be all 0s and 1s, and most of the time long decimal numbers have commas to make them easier to read. 
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
?
Answer 

The leading zero is a hint that the number is a binary number and not a decimal number because decimal numbers are rarely written with a zero on the left (we never write: "I gave a 010 dollar donation" when we donated ten dollars). The leading zero does not change the meaning of the binary number. For clarification, sometimes we write 
7.3. Notation
Explain the statement that "There are only 10 people in the world, those who understand binary and those who do not."
Answer 

There are 10 decimal numbers (09) but only 0 and 1 are used in binary numbers. 
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 
Answer  

B. One way of solving this problem is to try the decimal to binary conversion algorithm for all possible answers. Alternatively, the Binary to Decimal conversion steps can be followed, which are: Step 1: Create a table with a binary number to be converted to decimal in the first row. Step 2: Write down the powers of two in the second row. Step 3: Multiply the values in the first row with the values in the second row. Place the result in the third row. Step 4: Do the multiplication in row 3 and put values in row 4. Step 5: Add all values in row 4 to get answer. Answer: 256+0+0+32+16+8+4+2+1=319.

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 
Answer  

D. Step 1: Create a table with a binary number to be converted to decimal in the first row. Step 2: Write down the powers of two in the second row. Step 3: Multiply the values in the first row with the values in the second row. Place the result in the third row. Step 4: Do the math in row 3 and put values in row 4. Add all values in row 4 to get answer. Answer:

7.6. Binary to Decimal
Convert the binary number 0101
to a decimal number.
Answer  

Answer: 0+4+0+1=5.

7.7. Binary to Decimal
Convert the binary number 10101
to decimal.
Answer 

21 
7.8. Binary to Decimal
Convert the binary number 10111
to decimal.
Answer 

23 
7.9. Binary to Decimal
Convert the binary number 00111
to decimal.
Answer 

7 
7.10. Decimal to Binary
Convert the decimal number 31
to binary.
Answer  

11111  
In the following, we solve this problem using two approaches. The first is the lefttoright and righttoleft method. The second is the more efficient method.
A third method is to note that  
Method 1: The lefttoright and righttoleft method:
Method 2: The more efficient method is

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 
Answer 

A. 
7.12. Decimal to Binary
Convert the decimal number 49
to binary.
Answer 

110001 
7.13. Decimal to Binary
Convert the decimal number 77
to binary.
Answer 

1001101 
7.14. Decimal to Binary
Convert the decimal number 83
to binary.
Answer 

1010011 
7.15. Decimal to Binary
Convert the decimal number 99
to binary
Answer 

1100011 
7.16. Decimal to Binary
Convert the decimal number 103
to binary
Answer 

1100111 
7.17. Counting Patterns
How many unique patterns can be formed with a single bit?
Answer 

N = 2, so N_{patterns} = 2^{N} = 2^{1} = 2. 
7.18. Counting Patterns
How many unique patterns can be formed from three bits?
Answer 

N = 3, so N_{patterns} = 2^{N} = 2^{3} = 8. 
7.19. Counting Patterns
How many unique patterns can be formed by placing 9 decimal numbers sidebyside?
Answer 

N = 9 and S = 10, so N_{patterns} = S^{N} = 10^{9} = 1,000,000,000. 
7.20. Counting Patterns
You are asked to give students in a class an identification pattern that is formed by placing two squares sidebyside. 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?
Answer 

N = 2 and S = 3, so N_{patterns} = S^{N} = 3^{2} = 9, so the largest class size would be 9 students. 
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?
Answer 

The customer can ask for 1 apple so 1 box (box 1) must have 1 apple. The customer can ask for 2 apples so box 2 must have 2 apples. If the customer asks for 3 apples, the vendor can hand him boxes 1 and 2. Continuing with this pattern, the first nine boxes should have 1, 2, 4, 8, 16, 32, 64, 128, and 256 apples. The last box must have 1000(1+2+4+8+16+52+64+128+256) = 489 apples. 
7.22. Counting Patterns
How many unique patterns composed of four octal digits can be formed?.
Answer 

4096 
N = 8, so N_{patterns} = 8^{N} = 8^{4} = 4096. 
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?
Answer 

N_{patterns} = 2^{8} = 256 possible configurations Another way to answer this question is: the largest binary number is 
7.24. Counting Patterns
How many distinct combinations of zeros and ones can be made with
 2 bits
 4 bits
 7 bits
 8 bits
Answer 

Use the equation N_{patterns} = 2^{N} or find the largest decimal number associated with the bit patterns and add one to it.

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

256 
16^{N} = 16^{2} = 256. 
7.26. Counting Patterns
Can every decimal number has a binary representation? If so, is the binary representation of a number unique?
Answer 

Yes, this was shown using the algorithm covered in this section. (Technically, the algorithm covered in this section only shows that all whole decimal numbers have a binary equivalent. However, every decimal number does have a binary representation if one allows for infinitely long binary patterns. For example, the decimal number 1.2 has the binary equivalent of 1.0011 0011 0011 0011 0011 ...) 
7.27. Counting Patterns
 Can 682_{7} be rewritten in base 10 notation?
Answer 

Yes. A method similar to that used for computing base 2 numbers to base 10 could be used to do this. 
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.
Answer 

Suppose that you had a LED display [1] (similar to that on digital alarm clocks) that could only display one digit. This display would be limited to communicating the decimal numbers 0 through 9. With hexidecimal, the display could show numbers corresponding to the decimal values 0 through 15. 
8. Activities
8.1. Guessbased Approach for Decimal to Binary
Work on these three questions for five minutes:


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
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 07 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.
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 07 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.
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.
8.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.
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 twodigit 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.
10. Review: Exponential Notation


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, rewrite 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^{AB}\) because \(AB = 42 = 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^{AB}\) because \(AB = 52 = 3\).
So it looks like the rule is to subtract the top exponent from the bottom exponent.
\(\frac{10^9}{10^6} = \)
A. 10^{1.5} 
B. 10^{3} 
C. 10^{3} 
D. 10^{54} 
Answer 

B. Use the rule: $$\frac{10^A}{10^B}=10^{AB}$$ so $$\frac{10^9}{10^6} = 10^{96} = 10^3$$ 
Explain why 2^{3} isn't just one half of 2^{6}?
Answer 

You are not multiplying 2 by 3 (2·3=6) and 2 by 6 (2·6=12), which would be half. You are multiplying 2 by itself 3 times (2·2·2=8) and 2 by itself 6 times (2·2·2·2·2·2=64). 
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 
Answer 

C. This can be solved 2 different ways:
2^{11} is 32 times larger than 2^{6} 
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 
Answer 

C. If dealing with the same base (in this case 2) when multiplying exponents, just add the exponents. Using the rules of algebra, complete the following: x+3+4+5=10 => x+12=10 => x=1012, therefore, x = 2 
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 
Answer 

D. If dealing with the same base (in this problem, base 2) when dividing exponents, subtract the exponents. Exponent in numerator  Exponent in denominator 17x=5 => x=175, therefore, x = 12 
2^{10} divided by 2^{3}
A. 2^{12} 
B. 2^{7} 
C. 2^{7 } 
D. 2^{12} 
E. None of the above 
Answer 

B. If dealing with the same base (in this problem, 2) when dividing exponents, subtract the exponents. Exponent in numerator  Exponent in denominator 103=7 so answer is 2^{7} 
2^{10} multiplied by 2^{3}
A. 2^{13} 
B. 2^{13} 
C. 2^{7} 
D. 2^{7} 
E. None of the above 
Answer 

A. When multiplying exponents that have the same base, add the exponents. 10+3=13 so answer is 2^{13} 