Section1.4Binary Representation of Positive Integers
Subsection1.4.1Grouping by Twos
Recall that the set of positive integers, \(\mathbb{P}\text{,}\) is \(\{1, 2, 3, . . . \}\text{.}\) Positive integers are naturally used to count things. There are many ways to count and many ways to record, or represent, the results of counting. For example, if we wanted to count five hundred twenty-three apples, we might group the apples by tens. There would be fifty-two groups of ten with three single apples left over. The fifty-two groups of ten could be put into five groups of ten tens (hundreds), with two tens left over. The five hundreds, two tens, and three units is recorded as 523. This system of counting is called the base ten positional system, or decimal system. It is quite natural for us to do grouping by tens, hundreds, thousands, \(\dots\) since it is the method that all of us use in everyday life.
The term positional refers to the fact that each digit in the decimal representation of a number has a significance based on its position. Of course this means that rearranging digits will change the number being described. You may have learned of numeration systems in which the position of symbols does not have any significance (e.g., the ancient Egyptian system). Most of these systems are merely curiosities to us now.
The binary number system differs from the decimal number system in that units are grouped by twos, fours, eights, etc. That is, the group sizes are powers of two instead of powers of ten. For example, twenty-three can be grouped into eleven groups of two with one left over. The eleven twos can be grouped into five groups of four with one group of two left over. Continuing along the same lines, we find that twenty-three can be described as one sixteen, zero eights, one four, one two, and one one, which is abbreviated \(10111_{\textrm{two}}\text{,}\) or simply \(10111\) if the context is clear.
Subsection1.4.2A Conversion Algorithm
The process that we used to determine the binary representation of \(23\) can be described in general terms to determine the binary representation of any positive integer \(n\text{.}\) A general description of a process such as this one is called an algorithm. Since this is the first algorithm in the book, we will first write it out using less formal language than usual, and then introduce some “algorithmic notation.” If you are unfamiliar with algorithms, we refer you to Section A.1
Start with an empty list of bits.
Assign the variable \(k\) the value \(n\text{.}\)
While \(k\)’s value is positive, continue performing the following three steps until \(k\) becomes zero and then stop.
divide \(k\) by 2, obtaining a quotient \(q\) (often denoted \(k \textrm{ div } 2\)) and a remainder \(r\) (denoted \((k \bmod 2)\)).
attach \(r\) to the left-hand side of the list of bits.
assign the variable \(k\) the value \(q\text{.}\)
Example1.4.1.An example of conversion to binary.
To determine the binary representation of 41 we take the following steps:
\(\displaystyle 5 =\text2\times 2+ 1 \quad List =1001\)
\(\displaystyle 2 =2\times 1+ 0 \quad List = 01001 \)
\(\displaystyle 1 =\text2 \times 0\text+1 \quad List = 101001\)
Therefore, \(41=101001_{\textrm{two}}\)
The notation that we will use to describe this algorithm and all others is called pseudocode, an informal variation of the instructions that are commonly used in many computer languages. Read the following description carefully, comparing it with the informal description above. Appendix B, which contains a general discussion of the components of the algorithms in this book, should clear up any lingering questions. Anything after // are comments.
Algorithm1.4.2.Binary Conversion Algorithm.
An algorithm for determining the binary representation of a positive integer.
Input: a positive integer n.
Output: the binary representation of n in the form of a list of bits, with units bit last, twos bit next to last, etc.
k := n \(\qquad \) //initialize k
L := { } \(\qquad \) //initialize L to an empty list
While k > 0 do
q := k div 2 \(\qquad \) //divide k by 2
r:= k mod 2
L: = prepend r to L \(\qquad \) //add r to the front of L
k:= q \(\qquad \) //reassign k
Here is a Sage version of the algorithm with two alterations. It outputs the binary representation as a string, and it handles all integers, not just positive ones.
Now that you’ve read this section, you should get this joke.
Comic from http://xkcd.com. Two individuals, Megan and Cueball, are conversing. Transcript follows. Megan: On a scale of 1 to 10, how likely is it that this question is using Binary? Cueball: ...4? Megan: What’s a 4?
Figure1.4.3.With permission from Randall Munroe, http://xkcd.com.
Exercises1.4.3Exercises
1.
Find the binary representation of each of the following positive integers by working through the algorithm by hand. You can check your answer using the sage cell above.
31
32
10
100
Answer.
\(\displaystyle 11111\)
\(\displaystyle 100000\)
\(\displaystyle 1010\)
\(\displaystyle 1100100\)
2.
Find the binary representation of each of the following positive integers by working through the algorithm by hand. You can check your answer using the sage cell above.
64
67
28
256
3.
What positive integers have the following binary representations?
10010
10011
101010
10011110000
Answer.
\(\displaystyle 18\)
\(\displaystyle 19\)
\(\displaystyle 42\)
\(\displaystyle 1264\)
4.
What positive integers have the following binary representations?
100001
1001001
1000000000
1001110000
5.
The number of bits in the binary representations of integers increases by one as the numbers double. Using this fact, determine how many bits the binary representations of the following decimal numbers have without actually doing the full conversion.
2017
4000
4500
\(\displaystyle 2^{50}\)
Answer.
There is a bit for each power of 2 up to the largest one needed to represent an integer, and you start counting with the zeroth power. For example, 2017 is between \(2^{10}=1024\) and \(2^{11}=2048\text{,}\) and so the largest power needed is \(2^{10}\text{.}\) Therefore there are \(11\) bits in binary 2017.
\(\displaystyle 11\)
\(\displaystyle 12\)
\(\displaystyle 13\)
51
6.
Let \(m\) be a positive integer with \(n\)-bit binary representation: \(a_{n-1}a_{n-2}\cdots a_1a_0\) with \(a_{n-1}=1\) What are the smallest and largest values that \(m\) could have?
7.
If a positive integer is a multiple of 100, we can identify this fact from its decimal representation, since it will end with two zeros. What can you say about a positive integer if its binary representation ends with two zeros? What if it ends in \(k\) zeros?
Answer.
A number must be a multiple of four if its binary representation ends in two zeros. If it ends in \(k\) zeros, it must be a multiple of \(2^k\text{.}\)
8.
Can a multiple of ten be easily identified from its binary representation?
