The simple math behind decimal-binary conversion algorithms

Post Editor

This article explains the very basic math behind four simple algorithms to convert binary to decimal: two for integer and two for fractions.

12 min read
4 comments
post

The simple math behind decimal-binary conversion algorithms

This article explains the very basic math behind four simple algorithms to convert binary to decimal: two for integer and two for fractions.

post
post
12 min read
4 comments
4 comments

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:

Content imageContent image

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.

Content imageContent image

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.

Content imageContent image

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.

Content imageContent image

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:

Content imageContent image

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:

Content imageContent image

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

Content imageContent image

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:

Content imageContent image

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:

Content imageContent image

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:

Content imageContent image

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:

Content imageContent image

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:

Content imageContent image

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

Content imageContent image

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:

Content imageContent image

So, our second step is:

Content imageContent image

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.

Content imageContent image

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

Content imageContent image

So, our third step is:

Content imageContent image

So, we end up with the following:

Content imageContent image

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:

Content imageContent image

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:

Content imageContent image

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

Content imageContent image

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:

Content imageContent image

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

Content imageContent image

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:

Content imageContent image

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:

Content imageContent image

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

Content imageContent image

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

Content imageContent image

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:

Content imageContent image

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:

Content imageContent image

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:

Content imageContent image

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.

Content imageContent image

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

Content imageContent image

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

Content imageContent image

and move 1/2 to the left:

Content imageContent image

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:

Content imageContent image

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

Content imageContent image

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

Content imageContent image

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

Content imageContent image

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

Content imageContent image

So let’s write out all steps again:

Content imageContent image

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:

Content imageContent image

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:

Content imageContent image

and can’t finitely represent 1/3:

Content imageContent image

The same goes for the base-2 system:

Content imageContent image

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:

Content imageContent image

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

Content imageContent image

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:

Content imageContent image

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

Content imageContent image

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:

Content imageContent image
Content imageContent image

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:

Content imageContent image

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:

Content imageContent image

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

Content imageContent image
Content imageContent image

In this way 0.1011 in binary is 0.6875 in decimal.

Comments (4)

authorasarkar
20 August 2021

Very well explained, but it seems the last term of the polynomial for fractional number is wrong. It should be x^n.q^-n.

authormaxkoretskyi
26 August 2021

Yep, a typo, thanks for noticing it! Updated the article

authorareuie
10 March 2022

This article was so helpful! I had trouble understanding why it was that decimals needed to *2. Thank you for taking the time to explain not only how to do it but also how it works. :)

authoradrianandon
8 April 2022

"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 x1 must be 1 and the remaining part 0.5." - @maxkoretskyi I think you meant "x2 must be 1", right?

authormaxkoretskyi
9 April 2022

yes, thanks! corrected it

Share

About the author

author_image

Max is a self-taught software engineer that believes in fundamental knowledge and hardcore learning. He’s the founder of inDepth.dev community and one of the top users on StackOverflow (70k rep).

author_image

About the author

Max Koretskyi

Max is a self-taught software engineer that believes in fundamental knowledge and hardcore learning. He’s the founder of inDepth.dev community and one of the top users on StackOverflow (70k rep).

About the author

author_image

Max is a self-taught software engineer that believes in fundamental knowledge and hardcore learning. He’s the founder of inDepth.dev community and one of the top users on StackOverflow (70k rep).

Looking for a JS job?
Job logo
.Net Software Developer (.Net, JavaScript, Azure)

Pure Integration - Consulting

Worldwide
Remote
$96k - $110k
Job logo
JavaScript-Full Stack Developer

NEXGEN TECHNOLOGIES INC.

Worldwide
Remote
$70k - $85k
Job logo
JavaScript developer

Planner 5D

Worldwide
Remote
$74k - $94k
Job logo
A/B Test Developer | Front-end Javascript Developer

Conversion Sciences

United States
Remote
$70k - $85k
More jobs
NxAngularCli
NxAngularCli
NxAngularCli

Featured articles

blockchainpost
19 July 202212 min read
An Introduction to Blockchain

Learn the fundamentals of a blockchain starting from first principles. We'll cover hashing, mining, consensus and more. After reading this article, you'll have a solid foundation upon which to explore platforms like Ethereum and Solana.

blockchainpost
19 July 202212 min read
An Introduction to Blockchain

Learn the fundamentals of a blockchain starting from first principles. We'll cover hashing, mining, consensus and more. After reading this article, you'll have a solid foundation upon which to explore platforms like Ethereum and Solana.

Read more
blockchainpostAn Introduction to Blockchain

19 July 2022

12 min read

Learn the fundamentals of a blockchain starting from first principles. We'll cover hashing, mining, consensus and more. After reading this article, you'll have a solid foundation upon which to explore platforms like Ethereum and Solana.

Read more