1.4: Binary Representation of Positive Integers

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

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 17.1

1. Start with an empty list of bits.
2. Assign the variable \(k\) the value \(n\text{.}\)
3. While \(k\)'s value is positive, continue performing the following three steps until \(k\) becomes zero and then stop.
   1. divide \(k\) by 2, obtaining a quotient \(q\) (often denoted \(k \textrm{ div } 2\)) and a remainder \(r\) (denoted \((k \bmod 2)\)).
   2. attach \(r\) to the left-hand side of the list of bits.
   3. assign the variable \(k\) the value \(q\text{.}\)

Example \(\PageIndex{1}\): An Example of Conversion to Binary

To determine the binary representation of 41 we take the following steps:

• \(\displaystyle 41 = 2 \times 20+ 1 \quad List = 1 \)
• \(\displaystyle 20 = 2 \times 10+0 \quad List = 01 \)
• \(\displaystyle 10 = 2\times 5 + 0 \quad List = 001 \)
• \(\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.

Algorithm \(\PageIndex{1}\): 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.

1. k := n \(\qquad \) //initialize k
2. L := { } \(\qquad \) //initialize L to an empty list
3. While k > 0 do
   1. q := k div 2 \(\qquad \) //divide k by 2
   2. r:= k mod 2
   3. L: = prepend r to L \(\qquad \) //add r to the front of L
   4. 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.

def binary_rep(n):
    if n==0:
        return '0'
    else:
        k=abs(n)
        s=''
        while k>0:
            s=str(k%2)+s
            k=k//2
        if n < 0:
            s='-'+s
        return s
 
binary_rep(41)

Now that you've read this section, you should get this joke.

Figure \(\PageIndex{1}\): With permission from Randall Munroe, http://xkcd.com.

Exercises

Exercise \(\PageIndex{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.

1. \(31\)
2. \(32\)
3. \(10\)
4. \(100\)

Answer

1. \(\displaystyle 11111\)
2. \(\displaystyle 100000\)
3. \(\displaystyle 1010\)
4. \(\displaystyle 1100100\)

Exercise \(\PageIndex{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.

1. \(64\)
2. \(67\)
3. \(28\)
4. \(256\)

Exercise \(\PageIndex{3}\)

What positive integers have the following binary representations?

1. \(10010\)
2. \(10011\)
3. \(101010\)
4. \(10011110000\)

Answer

1. \(\displaystyle 18\)
2. \(\displaystyle 19\)
3. \(\displaystyle 42\)
4. \(\displaystyle 1264\)

Exercise \(\PageIndex{4}\)

What positive integers have the following binary representations?

1. \(100001\)
2. \(1001001\)
3. \(1000000000\)
4. \(1001110000\)

Exercise \(\PageIndex{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.

1. \(2017\)
2. \(4000\)
3. \(4500\)
4. \(\displaystyle 2^{50}\)

Answer

1. 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.
2. \(\displaystyle 11\)
3. \(\displaystyle 12\)
4. \(\displaystyle 13\)
5. \(51\)

Exercise \(\PageIndex{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?

Exercise \(\PageIndex{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{.}\)

Exercise \(\PageIndex{8}\)

Can a multiple of ten be easily identified from its binary representation?