Skip to main content

Read the Online Textbook for the full content.

Section 1.4 Binary Representation of Positive Integers

Subsection 1.4.1 Grouping by Twos

Knowing the binary number representation is key to understanding how computers operate, from high-level programming languages down to registers and electronic circuits.
  • People count things in groups of 1, 10, 100, ...
  • Number 534 is made up of 5 groups of 100, 3 groups of 10 and 4 units. We write that as \(534 = 5 \cdot 100 + 3 \cdot 10 + 4 = 5 \cdot 10^2 + 3 \cdot 10^1 + 4 \cdot 10^0.\)

    These are groups of power of 10.

  • Notice how the coefficients of the power of 10 become the number's digits in base 10.
  • Decimal number system: base 10 positional system. We write 534 in base 10 as \(534_{10}\).
  • Base 10 was natural choice long ago since humans have 10 fingers.
  • However, the base can be an arbitrary positive number. Base 2 uses groups of powers of 2: 2, 4, 8, 16,.... For instance, \begin{equation*} \begin{split} 23_{10} & = 1 \cdot 16 + 0 \cdot 8 + 1 \cdot 4 + 1 \cdot 2 + 1 \cdot 1 \\ & = 1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 10111_2 \end{split}. \end{equation*}
  • Notice again how the coefficients of the power of 2 terms become the number's digits, in base 2.
  • In general, for a representation of a binary number with n digits we have \((b_{n-1}b_{n-2} \ldots b_2 b_1 b_0)_2 = b_{n-1} \cdot 2^{n-1} + b_{n-2} \cdot 2^{n-2} + \dots + b_1 \cdot 2^1 + b_0 \cdot 2^0.\)
  • This is the formula used to convert a number in base 2 (binary number) to another base.
  • The coefficients of the powers of 2 can only be 0 or 1, called binary digits, or bits.
  • A group of 8 bits forms something called a byte.
  • Practical advice: when converting a binary number \(b_{n-1}b_{n-2} \ldots b_2 b_1 b_0\) to decimal by hand, start with the least significant \(b_0\) and go right-to-left. It's easier to keep track of 2's exponent.

Subsection 1.4.2 An Algorithm for Conversion to Binary Representation

  • How to determine the binary representation of any positive integer \(n\text{.}\)

  • General description of a process like this is called an algorithm.
  • First described in a less formal language than usual, and then in an “algorithmic notation” called pseudo-code.
  • Refer to Section A.1 for more on algorithm.
  • Conversion to binary algorithm:

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

  • Pseudo-code is an informal and more readable spacification language for algorithms.
  • It looks like a legit programming language, but syntax and semantic rules are lax and unenforceable.
  • Can mix in English statements and gloss over some details.
  • We denote comments to the end of the current line with //.

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}}\)

  • Python version (in a SageMath cell) 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?
Figure 1.4.3. With permission from Randall Munroe, http://xkcd.com.

Exercises 1.4.3 Exercises

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\)

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

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\)

4.

What positive integers have the following binary representations?

  1. 100001

  2. 1001001

  3. 1000000000

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

  1. 2017

  2. 4000

  3. 4500

  4. \(\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.

  1. \(\displaystyle 11\)

  2. \(\displaystyle 12\)

  3. \(\displaystyle 13\)

  4. 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?