The simple math behind decimal-binary conversion algorithms

If you search the web for "How to convert from decimal to binary" you will find four simple algorithms: two for the integer and two for fractions. They are presented with examples below in the first part of the article.But while just knowing the algorithms is almost always enough, I’ve decided to try to understand why they work. In the second part this article explains the very basic math behind each of them. Knowing it may help you remember any of the algorithms if you suddenly forget them. I strongly suggest you take a notepad and a pen and perform the operations along with me to better remember the math.Here are the four algorithms with examples that you can find on the web.

Converting decimal integer to binary

Link to this section

To convert integer to binary, start with the integer in question and divide it by 2 keeping notice of the quotient and the remainder. Continue dividing the quotient by 2 until you get a quotient of zero. Then just write out the remainders in the reverse order.

Here is an example of such conversion using the integer 12.
First, let’s divide the number by two specifying quotient and remainder:

Now, we simply need to write out the remainder in the reverse order —1100. So, 12 in decimal system is represented as 1100 in binary.

Converting decimal fraction to binary

Link to this section

To convert fraction to binary, start with the fraction in question and multiply it by 2 keeping notice of the resulting integer and fractional part. Continue multiplying by 2 until you get a resulting fractional part equal to zero. Then just write out the integer parts from the results of each multiplication.

Here is an example of such conversion using the fraction 0.375.

Now, let’s just write out the resulting integer part at each step — 0.011. So, 0.375 in decimal system is represented as 0.011 in binary.

Only fractions with a denominator which is a power of two can be finitely represented in a binary form. For example, denominators of 0.1 (1 / 10) and 0.2 (1 / 5) are not powers of two, so these numbers can’t be finitely represented in a binary format. In order to store them as a IEEE-754 floating point they have to be rounded to the number of available bits for mantissa — 10 bits for half-precision, 23 bits for single-precision or 52 bits for double-precision. Depending on how many bits of precision are available, the floating-point approximations of 0.1 and 0.2 could be slightly less or greater than there corresponding decimal representations, but never equal. Because of that fact, you’re never going to have 0.1+0.2 == 0.3.

Converting binary integer to decimal

Link to this section

To convert binary integer to decimal, start from the left. Take your current total, multiply it by two and add the current digit. Continue until there are no more digits left.Here is an example of such conversion using the fraction 1011.

Converting fraction integer to decimal

Link to this section

To convert binary fraction to decimal, start from the right with the total of 0. Take your current total, add the current digit and divide the result by 2. Continue until there are no more digits left. Here is an example of such conversion using the fraction 0.1011. I’ve simply replaced division by 2 with multiplication by 1/2.

There you have 4 simple algorithms that will allow you to convert binary numbers to decimal and back.

Base-q expansion of a number

Link to this section

The key to understanding why those algorithms work is a base-q expansion of a number. An integer number in any numeric system can be represented in the following form:

where,

• N is integer
• x is the digit (0 through 9 for base-10 system, 0 and 1 for base-2 system)
• q is the base value (10 for base-10 system, 2 for base-2 system)

Throughout this article this form is referred to as base q expansion of the number N, or simply base q expansion. Let’s see how it looks for the number 12 in decimal and binary systems:

Likewise, a fractional number in any numeric system can be represented in the following form:

where,

• N is an fraction
• x is the digit (0 through 9 for base-10 system, 0 and 1 for base-2 system)
• q is the base value (10 for base-10 system, 2 for base-2 system)

For the number 0.375 in decimal and binary systems the representation is the following:

Converting decimal integer to binary

Link to this section

As it turns out, we can use this base-q expansion form to convert a number from decimal to binary system. Let’s do that for the same number 12. First, let’s pretend we don’t know how it is represented in the binary and write it out with unknown digits replaced with x:

Our task is to find all x’s. Let’s see what we can do here. The first thing we need to notice here is all summands except for the last one will be even numbers, because they all are multiples of two. Now, using this information we can infer the digit for the x0 — if the integer being converted is even, then x0 is equal to 0, if it’s odd — then x0 must be 1. Here we have number 12 which is even, so x0 is zero. Let’s write this information down:

Next, we need to find the value for the x1. Since all summands from x1 to xN are multiples of two, we can factor out 2 to single out x1. Let’s do that:

It’s also easy to see the sum of the values inside the parenthesis is equal to 6. So, we can write our first step as:

Let’s continue finding out the remaining x’s. We can write out the polynomial inside the parenthesis as a separate statement:

Here, applying the same logic from above we can see that x1 is equal to 0. Let’s rewrite it and also factor out 2 again:

So, our second step is:

Now, we can see a pattern. We can continue factoring 2 until the quotient is zero. Let’s follow this pattern and see what we get.

Since the quotient is equal to 1, there’s only one summand left, so let’s rewrite the previous expression:

So, our third step is:

So, we end up with the following:

It’s clear that x3 is equal to 1. But, since for our algorithm we need a quotient, let’s rewrite the previous expression so that it has a quotient:

Since we end up with the quotient of 0, there’s nothing else to work with and this was our last step. Let’s write it out:

So now we’ve finished conversion. Here is how our conversion looks by steps:

It’s clear now that the remainder in each step corresponds to the value of x’s in the corresponding positions: first remainder corresponds to the first x, second remainder to the second x and so on. So the number 12 in binary using the algorithm described above is represented as 1100.

Remember that we started with the idea to show why the algorithm that involves diving by 2 works. Let’s take the steps outlined above and move the 2 to the left part of the expressions:

So in this way you can see how we arrived at the algorithm described in in the beginning. We can also put the calculations for those four steps into one representation like this

Make sure you understand how we arrive at that representation as we will need it when exploring how the algorithm of converting from binary to decimal works.

Converting decimal fraction to binary

Link to this section

To show why we multiply by 2 and take the integer part when converting fractions to binary, I’ll also be using base-q expansion form for fractions. I’m going to use the fractional number 0.375 from the first part of the article. Similarly to integer part, let’s pretend we don’t know how this number is represented in the binary and write it out with unknown digits replaced with x:

As with integers, our task is to find all x’s by singling out x’s. Let’s see how we can do that. The first thing to notice here is that negative powers of 2 give us fractions with the denominator of 2 with positive powers. Let’s rewrite the above expression:

It’s immediately obvious that we can simply factor out 1/2 in the right part of expression. Let’s do that:

and we can then move 1/2 to the left part

Okay, here we’ve singled out x1, and we know that it can be either 1 or 0. To determine what digit it has let’s take a look at the remaining summands:

Let’s think of how big the sum of these numbers can be. If the maximum number of x digits is 1, than we can simply replace x’s with 1’s and write the sum as:

Well, this is a geometric series of fractions, and the sum of such series lies in the boundaries [0 < sum < 1], so the maximum number such sum can give us is 1. Let’s now look at our expression again:

Now, this should be clear here that if the right side is less than 1, then x1 can’t be equal to 1 and so it’s equal to 0, while the remaining part is equal to 0.75.

This looks exactly how the first step in the algorithm presented in the beginning:

Let’s take out fractional part of 0.75 and factor out another 1/2 to single out x2:

and move 1/2 to the left:

Now, if x2 is equal to 0, then the sum of left side of the expression cannot be greater than 1, but the left side is 1.5, so x2 must be 1 and the remaining part 0.5. Let’s write it out:

Again, this follows the pattern in the algorithm presented in the beginning:

Let’s repeat the same actions for the remaining fractional part of 0.5.

Using the same logic as above we can see that x3 is equal to 1 and there is no remaining fractional part:

Since the remaining fractional part is equal to 0, this is how our last step looks like:

So let’s write out all steps again:

This exactly the algorithm I presented in the beginning. Just like we did with integers, we can also put the calculations for those three steps into one representation like this:

Again, it is important that you fully grasp this representation as we will need it when exploring binary to decimal conversion.

Why not all fractions can be finitely represented in binary

Link to this section

The fact that some fractions represented finitely in decimal system cannot be represented finitely in binary system comes as surprise to many developers. But this is exactly the confusion that lies in the root of the seemingly weird outcome of adding 0.1 to 0.2. So what determines whether a fraction can be finitely represented in a numeric system? It's quite complicated. But the basic version is this — for a number to be finitely represented the denominator in a fraction should be a power of the system base. For example, for the base-10 system, the denominator should be a power of 10, that’s why we can finitely represent 0.625 in decimal:

and can’t finitely represent 1/3:

The same goes for the base-2 system:

But if we check 0.1, the denominator is 10 and it’s not a power of 2, so 0.1 is going to be an infinite fraction in the binary system. Let’s see it using the algorithm we learnt above:

We can continue doing that infinitely, but let’s write it out as periodic continued fraction:

Converting binary integer to decimal

Link to this section

I’m going to use the same binary integer 1011 from the first section to show you why the algorithm of multiplying by 2 works. Here we also will use the base-q expansion form of the number. Let’s write it down in this form:

Since all summands are multiples of 2, we can keep factoring out 2 until the quotient is zero. Let’s do that:

Now, if you simply follow the order of math operations you’ll end up with exactly the same steps as I’ve shown in the beginning, particularly:

In this way 1011 in binary is 11 in decimal.

Converting binary fraction to decimal

Link to this section

Now, we’ve come to the last algorithm. Probably, you’ve already figured out yourself mechanics behind it. If not, let’s see why it works. The base-q expansion form of the number is the key here as well. We’ll take the number 0.1011 from the first section. Let’s write it down in the expanded form:

Again, since all summands are multiples of 1/2, we can keep factoring out 1/2 until there is no remaining fractional part. Let’s do that:

Following the order of math operations produces the algorithm outlined in the beginning:

In this way 0.1011 in binary is 0.6875 in decimal.