## Section11.3From 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.

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{.}$$

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.

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

We now illustrate how the algorithm works with an example.

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.

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{.}$$

With the conversion algorithm find the base $$15$$ representation of the decimal number $$43537\text{.}$$

Input: Base $$b :=$$ and a base 10 number $$a :=$$

Let $$q_0:=a\text{.}$$

Let $$r_{0} := q_{0}\bmod b =$$ . Let $$q_{1} := a_{0}\;\mathrm{div}\; b =$$ .

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

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

Let $$r_{3} := q_{3}\bmod b =$$ . Let $$q_{4} := a_{3}\;\mathrm{div}\; b =$$ .

Output: The expanded base $$15$$ representation of the decimal number $$43537$$ is:

$$43537=r_{3}\cdot 15^{3}$$

$$+r_{2}\cdot 15^{2}$$

$$+r_{1}\cdot 15^{1}$$

$$+r_{0}\cdot 15^{0}$$

$$\phantom{43537}=$$$$\cdot 15^{3}$$

$$+$$$$\cdot 15^{2}$$

$$+$$$$\cdot 15^{1}$$

$$+$$$$\cdot 15^{0}$$

Now give the base $$15$$ representation of $$43537\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.

Be careful to write $$A$$ for $$10$$ and $$B$$ for $$11$$ and $$C$$ for $$12$$ and so on.

]

$$43537 =$$$${}_{15}$$

$$15$$

$$43537$$

$$7$$

$$2902$$

$$7$$

$$193$$

$$13$$

$$12$$

$$12$$

$$0$$

$$12$$

$$13$$

$$7$$
$$7$$