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
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
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.
Example11.11.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{.}\)
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:
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{.}\)
Problem11.12.Represent \(37\) as a sum of powers of two.
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.16.
Example11.16.Conversion to base 2 representation interactive.
In Checkpoint 11.17 use the method from Algorithm 11.13 to convert a number in base \(10\) representation to base \(2\text{.}\)
Checkpoint11.17.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} := q_{0}\;\mathrm{div}\; 2 =\) .
Let \(r_{1} := q_{1}\bmod 2 =\) . Let \(q_{2} := q_{1}\;\mathrm{div}\; 2 =\) .
Let \(r_{2} := q_{2}\bmod 2 =\) . Let \(q_{3} := q_{2}\;\mathrm{div}\; 2 =\) .
Let \(r_{3} := q_{3}\bmod 2 =\) . Let \(q_{4} := q_{3}\;\mathrm{div}\; 2 =\) .
Let \(r_{4} := q_{4}\bmod 2 =\) . Let \(q_{5} := q_{4}\;\mathrm{div}\; 2 =\) .
Let \(r_{5} := q_{5}\bmod 2 =\) . Let \(q_{6} := q_{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 should write 101 but not 0101.
]
\(47 =\)\({}_{2}\)
Two people are talking.
Person 1: On a scale of 1 to 10, how likely is it that this question is using Binary? Person 2:...4? Person 1: What’s a 4?
Title text: If you get an 11 out of 100 on a CS test, but you claim it should be counted as a ’C’, they’ll probably decide you deserve the upgrade.
If you get an 11/100 on a CS test, but you claim it should be counted as a ’C’, they’ll probably decide you deserve the upgrade.
