From Decimal to Binary

Section 11.3 From Decimal to Binary

Now we study how we can convert a number in base 10 representation to base 2 representation. From the previous section it is easy to see 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 continue 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{.}\)

🔗

Now we 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 later quotients and remainders will also be \(0\) and thus we are done with the conversion.

🔗

We show 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 get:

🔗

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

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*}

We found the base \(2\) digits from the lowest power to the highest power. By convention, we write the digits in the opposite order, with the highest power of \(2\) on the left:

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

This order makes the base \(2\) representation of \(13\) easy to read:

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

🔗

In base \(2\text{,}\) we use only the symbols \(0\) and \(1\text{.}\) We can easily convert a base \(2\) representation into a sum of powers of \(2\) 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 2+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

🔗

Now we show 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{.}\) So the base \(2\) representation of \(13\) is \(1101_2\text{.}\)

🔗

Study more 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.

🔗

described in detail following the image — Figure 11.3.7. *1 to 10* by Randall Munroe (`https://xkcd.com/953`)
🔗

🔗

Prev Top Next