From Decimal to Binary

Section 11.3 From Decimal to Binary

Now we investigate how we can convert a number in base 10 representation to base 2 representation. From the previous section it is evident that when we write a number in base 2 representation we write it as the sum of powers of 2.

Let \(a\in\N\text{.}\) Finding the base \(2\) expansion of \(a\) means finding integers \(r_0\text{,}\) \(r_1\text{,}\) \(r_2\text{,}\) \(\ldots\text{,}\) \(r_{m-1}\text{,}\) and \(r_m\) that are either \(0\) or \(1\) such that

\begin{equation*} a=r_m\cdot 2^m+r_{m-1}2^{m-1}+\dots+r_3\cdot 2^3+r_2\cdot 2^2+r_1\cdot 2+r_0. \end{equation*}

We proceed from right to left, that is we first find \(r_0\text{,}\) then \(r_1\text{,}\) and so on.

Let \(r_0=a\fmod 2\) be the remainder of the division of \(a\) by \(2\text{.}\) Then

\begin{equation*} a=q_0\cdot 2+r_0\text{.} \end{equation*}

As \(q_0\cdot 2\) is divisible by \(2\) we have that \(r_0\) the rightmost base \(2\) digit of \(a\text{.}\)

We now continue this procedure with \(q_0=a\fdiv 2\text{.}\) Let \(r_1=q_0\fmod 2\) be the remainder of the division of \(q_0\) by \(2\) and \(q_1=q_0\fdiv 2\text{.}\) Then \(q_0=q_1\cdot 2+r_1\text{.}\) Replacing \(q_0\) by \(q_0=q_1\cdot 2+r_1\) in \(a=q_0\cdot 2+r_0\) we get

\begin{equation*} a=q_0\cdot 2+r_0=(q_1\cdot 2+r_1)2+r_0=q_1\cdot 2^2+r_1\cdot 2+r_0\text{.} \end{equation*}

Continuing in this way, we successively compute the digits \(r_2\text{,}\) \(r_3\) and so on of the base \(b\) expansion of \(a\) using division with remainder. The quotient becomes smaller in every step. As the quotient is a non-negative integer, it eventually has to become \(0\text{.}\) In this case all subsequent quotients and remainders will also be \(0\) and thus we are done with the conversion.

We illustrate this process with an example.

Example 11.3.1. Conversion of \(13\) to binary representation..

We find the base \(2\) representation of \(a=13\text{.}\) Instead of writing \(q_0\text{,}\) \(q_1\text{,}\) and so on we reuse the variable \(a\) So that when we add a new row the number in the \(a\) column is the number in the \(a \fdiv 2\) column from the previous row. We stop when the number in the \(a \fdiv 2\) column becomes \(0\text{.}\)

Step	Power of \(2\)	\(a\)	\(a \fmod 2\)	\(a \fdiv 2\)
\(0\)	\(2^0\)	\(13\)

Filling in the last two columns we obtain:

Step	Power of \(2\)	\(a\)	\(a \fmod 2\)	\(a \fdiv 2\)
\(0\)	\(2^0\)	\(13\)	\(r_0=1\)	\(6\)

In the next step, \(n = 13\) is replaced by \(13 \fdiv 2 = 6\text{.}\)

Step	Power of \(2\)	\(a\)	\(a \fmod 2\)	\(a \fdiv 2\)
\(0\)	\(2^0\)	\(13\)	\(r_0=1\)	\(6\)
\(1\)	\(2^1\)	\(6\)	\(r_1=0\)	\(3\)

Continuing this process, we fill out the rest of the table. We stop when \(a \fdiv 2 = 0\text{.}\)

Step	Power of \(2\)	\(a\)	\(a\fmod 2\)	\(a \fdiv 2\)
\(0\)	\(2^0\)	\(13\)	\(r_0=1\)	\(6\)
\(1\)	\(2^1\)	\(6\)	\(r_1=0\)	\(3\)
\(2\)	\(2^2\)	\(3\)	\(r_2=1\)	\(1\)
\(3\)	\(2^3\)	\(1\)	\(r_3=1\)	\(0\)

Thus the base \(2\) expansion of \(13\) is

\begin{equation*} 13 = (1\cdot 2^0) + (0 \cdot 2^1) + (1 \cdot 2^2) + (1 \cdot 2^3). \end{equation*}

Although we computed the base \(2\) digits in this order, it is customary to write the last significant digit, that is the digit with the lowest power of \(2\) last:

\begin{equation*} 13 = (1\cdot 2^2) + (1 \cdot 2^2) + (0 \cdot 2^1) + (1 \cdot 2^0). \end{equation*}

This ordering also makes it easy to read off the base \(2\) representation of \(13\text{:}\)

\begin{equation*} 13=1101_2 \end{equation*}

As in base \(2\) we only use the symbols \(0\) and \(1\) the base \(2\) representation of a number can be easily converted to a representation of the number by the sum of powers of \(2\text{,}\) namely by leaving out the powers of \(2\) that are multiplied by \(0\text{.}\)

Problem 11.3.2. Represent \(37\) as a sum of powers of two.

Write \(37\) as a sum of powers of two.

Solution.

We proceed in the same manner as in Example 11.3.1.

Step	Power of \(2\)	\(a\)	\(a\fmod 2\)	\(a \fdiv 2\)
\(0\)	\(2^0\)	\(37\)	\(r_0=1\)	\(18\)
\(1\)	\(2^1\)	\(18\)	\(r_1=0\)	\(9\)
\(2\)	\(2^2\)	\(9\)	\(r_2=1\)	\(4\)
\(3\)	\(2^3\)	\(4\)	\(r_3=0\)	\(2\)
\(4\)	\(2^4\)	\(2\)	\(r_4=0\)	\(1\)
\(5\)	\(2^5\)	\(1\)	\(r_5=1\)	\(0\)

So we have

\begin{align*} 37\amp = (r_0\cdot 2^0) + (r_1 \cdot 2^1) + (r_2 \cdot 2^2) + (r_3 \cdot 2^3) + (r_4 \cdot 2^4) + (r_5 \cdot 2^5)\\ \amp = (1\cdot 2^0) + (0 \cdot 2^1) + (1 \cdot 2^2) + (0 \cdot 2^3) + (0 \cdot 2^4) + (1 \cdot 2^5)\\ \amp = 1+2^2+2^5 \end{align*}

We formulate this method for converting natural number from base \(10\) to base \(2\) as an algorithm.

Algorithm 11.3.3. Conversion to Binary.

Input:: \(\displaystyle a\in\N\)
Output:: The base \(2\) digits \(r_0,\dots,r_m\in\Z_2\) of \(a\) such that \(a=r_m\cdot 2^m+r_{m-1}2^{m-1}+\dots+r_3\cdot 2^3+r_2\cdot 2^2+r_1\cdot b+r_0\)

let \(i:=0\)
repeat
1. let \(r_i := a\fmod 2\)
2. let \(a := a\fdiv 2\)
3. let \(i := i+1\)
until \(a=0\)
return \(r_0,\dots,r_{i-1}\)

In the video in Figure 11.3.4 we go through the steps of Algorithm 11.3.3 and work out an example.

Figure 11.3.4. Conversion from Base 10 to Base 2 by Matt Farmer and Stephen Steward

We now illustrate how the algorithm works with an example.

Example 11.3.5. From decimal to binary with Algorithm 11.3.3.

We convert the base 10 number 13 to base 2 using Algorithm 11.3.3.

Input: \(b=2\text{,}\) \(a=13\)

\(i=0\)	\(r_0=13 \fmod 2=1\)	\(a=13\fdiv 2 =6\)
\(i=1\)	\(r_1=6 \fmod 2=0\)	\(a=6\fdiv 2 =3\)
\(i=2\)	\(r_2=3 \fmod 2=1\)	\(a=3\fdiv 2 =1\)
\(i=3\)	\(r_3=1 \fmod 2=1\)	\(a=1\fdiv 2 =0\)

Output: \(r_0 = 1\text{,}\) \(r_1 = 0\text{,}\) \(r_2 = 1\text{,}\) \(r_3 = 1\)

The base 2 expansion of 13 is \(13=1 \cdot 2^3+1 \cdot 2^2 + 0 \cdot 2+1 \cdot 1\text{.}\) Thus the base \(2\) representation of \(13\) is \(1101_2\text{.}\)

Investigate further examples by clicking your way through the steps of the interactive base conversion algorithm in Example 11.3.6.

Example 11.3.6. Conversion to base 2 representation interactive.

In Checkpoint 11.3.7 use the method from Algorithm 11.3.3 to convert a number in base \(10\) representation to base \(2\text{.}\)

Checkpoint 11.3.7. Covert from decimal to binary.

With the conversion algorithm find the base \(2\) representation of the decimal number \(47\text{.}\)

Input: A base 10 number \(a :=\)

Let \(q_0:=a\text{.}\)

Let \(r_{0} := q_{0}\bmod 2 =\) . Let \(q_{1} := a_{0}\;\mathrm{div}\; 2 =\) .

Let \(r_{1} := q_{1}\bmod 2 =\) . Let \(q_{2} := a_{1}\;\mathrm{div}\; 2 =\) .

Let \(r_{2} := q_{2}\bmod 2 =\) . Let \(q_{3} := a_{2}\;\mathrm{div}\; 2 =\) .

Let \(r_{3} := q_{3}\bmod 2 =\) . Let \(q_{4} := a_{3}\;\mathrm{div}\; 2 =\) .

Let \(r_{4} := q_{4}\bmod 2 =\) . Let \(q_{5} := a_{4}\;\mathrm{div}\; 2 =\) .

Let \(r_{5} := q_{5}\bmod 2 =\) . Let \(q_{6} := a_{5}\;\mathrm{div}\; 2 =\) .

Output: The expanded base \(2\) representation of the decimal number \(47\) is:

\(47=r_{5}\cdot 2^{5}\)

\(+r_{4}\cdot 2^{4}\)

\(+r_{3}\cdot 2^{3}\)

\(+r_{2}\cdot 2^{2}\)

\(+r_{1}\cdot 2^{1}\)

\(+r_{0}\cdot 2^{0}\)

\(\phantom{47}=\)\(\cdot 2^{5}\)

\(+\)\(\cdot 2^{4}\)

\(+\)\(\cdot 2^{3}\)

\(+\)\(\cdot 2^{2}\)

\(+\)\(\cdot 2^{1}\)

\(+\)\(\cdot 2^{0}\)

Now give the base \(2\) representation of \(47\text{.}\)

[Although writing leading zeros is mathematically correct, it will be marked as wrong. Do not put extra zeros in front of your answer. For example, you would write 101 instead of 0101.

]

\(47 =\)\({}_{2}\)

\(47\)

\(1\)

\(23\)

\(1\)

\(11\)