Waste less time on Facebook — follow Brilliant.

Investigation: Faster Conversion through Bases

Before reading this, you may want to look over this article on Number Base Representation.

Let's start with a simple problem: Convert \(10100111_2\) to base \(4\).

We first convert \(10100111_2\) to base \(10\), then convert that to base \(4\), as shown by the Number Base Representation article.

We see that \(10100111_2=1+2+4+32+128=167\). Now we convert this into base \(4\):

How many times does \(4^4=256\) go into \(167\)? None, we go down to test the next place.

How many times does \(4^3=64\) go into \(167\)? \(2\) times. Now we multiply \(2\) by \(64\) to get \(128\), and subtract this from \(167\) to get \(39\).

How many times does \(4^2=16\) go into \(39\)? Twice, so we multiply \(16\) by \(2\) to get \(32\), and subtract that from \(39\) to get \(7\).

How many times does \(4^1=4\) go into \(7\)? \(1\) time, so we subtract \(4\) from \(7\) to get \(3\).

How many times does \(4^0=1\) go into \(3\)? \(3\) times. Finally, our answer is \(2213_4\).

Phew, that was a pretty calculation-heavy problem. If only there was an easier way...

Let's look at our original base \(2\) number and our base \(4\) number more closely: \(10100111\iff 2213\). Do you notice anything interesting?

How about if I do this: \(10|10|01|11\iff 2|2|1|3\)?

We notice that in each little subdivision, the base \(2\) representation is automatically converted to the base \(4\) representation, independent of anything else! For example, \(10_2=2_4\), \(01_2=1_4\), and \(11_2=3_4\).

Why does this work? Let's observe what is happening, fundamentally: We can represent

\(10100111_2=1\times 2^7+0\times 2^6+1\times 2^5+0\times 2^4+\)\(0\times 2^3+1\times 2^2+1\times 2^1+1\times 2^0\).

Let's see what happens when we group this as follows: \(10100111_2=(1\times 2^7+0\times 2^6)+(1\times 2^5+0\times 2^4)+\) \((0\times 2^3+1\times 2^2)+(1\times 2^1+1\times 2^0)\)

Now we factor out the common multiple in each box:

\(10100111_2=2^6(1\times 2^1+0\times 2^0)+2^4(1\times 2^1+0\times 2^0)+\) \(2^2(0\times 2^1+1\times 2^0)+2^0(1\times 2^1+1\times 2^0)\)

Simplifying, we get that \(10100111_2=2\times 4^3+2\times 4^2+1\times 4^1+3\times 4^0\)

But wait a minute! The stuff on the \(\text{RHS}\) is exactly what a base \(4\) representation looks like! Therefore, we can clearly see that \(10100111_2=2213_4\).

Here is the trick in practice: We see that to convert base \(2\) to base \(4\), we group into groups of 2. So we have \(10100111\implies 10|10|01|11\).

We see that \(10_2=2_4\), \(10_2=2_4\), \(01_2=1_4\), and \(11_2=3_4\). Therefore our answer is \(\boxed{2213_4}\). You can see how much faster this is than to convert to base \(10\), then back to base \(4\).

It turns out that to convert a base \(2\) number to a base \(2^x\) number, we group the original number's digits into groups of \(x\). I'll prove this later.

How about this problem: Convert \(10100111_2\) to base \(8\).

Thinking along the lines of our previous exercise, we try to group the digits in \(10100111_2\) to get the base representation of a number base \(8\).

Seeing that \(2^3=8\), let's try groupings of threes.

We try to group \(10100111_2\) into groups of threes, but we can't, because there are \(8\) digits and \(8\) isn't divisible by \(3\). What do we do?

Well, we want there to be \(9\) digits, so we simply add a \(0\) at the beginning and there will be \(9\) digits. It won't change the value of the number, so we are safe in doing this.

Now we can group as follows: \(10100111_2\implies 010|100|111\).

Writing this out as the definition of a base number, we see that \(10100111_2=(0\times 2^8+1\times 2^7+0\times 2^6)+\)\((1\times 2^5+0\times 2^4+0\times 2^3)+(1\times 2^2+1\times 2^1+1\times 2^0)\)

Factoring out and simplifying, we get that \(10100111_2=2\times 2^6+4\times 2^3 + 7\times 2^0\).

Simplifying, we get that \(10100111_2=2\times 8^2 + 4\times 8^1+ 7\times 8^0=247_8\) and we are done.

In practice, you won't go through all of these steps. You'll just see:

\(10_2=2_8\), so the leftmost digit is \(2\).

\(100_2=4_8\), so the middle digit is \(4\).

\(111_2=7_8\), so the last digit is \(7\) and our final answer is \(247_8\).

This isn't limited to just powers of two; try this problem for yourself: Convert \(12002210_3\) to base \(9\).

Warning: Intense Math Ahead!

Now we'll prove this cool trick for any arbitrary starting base \(b\) converted into base \(b^x\) for some positive integer \(x\).

Let the starting number be \((d_1d_2\cdots d_{nx})_b\).

We are assuming that there is a multiple of \(x\) digits in the number; if this is not the case, add leading \(0\)'s to the beginning of the number until this is the case.

We represent this number as \(d_1b^{nx-1}+d_2b^{nx-2}+\cdots +d_{nx}b^0\).

Now we group the digits into groups of \(x\) each: \((d_1b^{nx-1}+\cdots + d_xb^{(n-1)x})+\)\((d_{x+1}b^{(n-1)x-1}+\cdots +d_{2x}b^{(n-2)x})+\cdots +\)\((d_{(n-1)x+1}b^{x-1}+\cdots +d_{nx}b^0)\).

Factoring each group, we get \(b^{(n-1)x}(d_1b^{x-1}+\cdots +d_xb^0)+\)\(b^{(n-2)x}(d_{x+1}b^{x-1}+\cdots +d_{2x}b^0)+\cdots +\)\(b^0(d_{(n-1)x+1}b^{x-1}+\cdots +d_{nx}b^0)\).

Changing \(b^{(n-i)x}\) to \((b^x)^{n-i}\) for all \(i=1\rightarrow n\), we get that \((d_1d_2\cdots d_{nx})_b=(b^x)^{n-1}(d_1b^{x-1}+\cdots +d_xb^0)+\)\((b^x)^{n-2}(d_{x+1}b^{x-1}+\cdots +d_{2x}b^0)+\cdots +\)\((b^x)^0(d_{(n-1)x+1}b^{x-1}+\cdots +d_{nx}b^0)\). This is exactly the base representation of a base \(b^x\) number, so we are done.

You may think, after reading all of this, that this way of converting bases is way easier; you won't ever need to use the classic convert-to-10-then-to-desired-base trick. However, this is unfortunately not the case. This trick only works for converting a base \(b\) number to a base \(b^x\) number, i.e this trick will not work for converting a base \(6\) number into a base \(3\) number. This is because there is not way to group the digits so that one base turns into the other.

However, when in the occasion of changing a base \(b\) number to a base \(b^x\) number, you will know a neat and fast trick to do so. (These occasions happen frequently in competition math.)


*1. * Convert \(12321_4\) to base \(16\).

*2. * Convert \(112010032_4\) to base \(8\). Hint: do an intermediate conversion first.

*3. * Convert \(12345678_9\) to base \(3\).

*4. * Prove the formula for converting a base \(b^x\) number to a base \(b^y\) number.

Note by Daniel Liu
2 years, 10 months ago

No vote yet
2 votes


Sort by:

Top Newest

Thanks for reading through my third #CosinesGroup post. I know this one is an especially long one, but it takes some explaining.

Sorry for any bad explaining on my part; I felt that my explaining for this was under par.

Feedback is appreciated. If you have any questions, feel free to ask.

I hope you learned something from this post,

~Daniel Daniel Liu · 2 years, 10 months ago

Log in to reply

@Daniel Liu Thank you Daniel! It was great :) Happy Melodies · 2 years, 10 months ago

Log in to reply

@Daniel Liu This is a useful trick in special scenarios. Another extention, is to convert from base \( b^x \) to base \( b^y \) by going through base \(b\) as opposed to base 10. This is much faster, and avoids a bunch of arithmetic. Try the following:

Convert \( (1234567)_8\) to base 4.

As a suggestion for improvement, it is generally best to clearly illustrate why this method is great. In the first example, I might have given the entire working, to show how this method is a one-step process which is much easier than the standard approach.

The usual method of converting between bases, is to work through base 10. We have ....

Calvin Lin Staff · 2 years, 10 months ago

Log in to reply

@Calvin Lin Yea, I think that was one of my problems on clarity. I realized that I didn't organize my article that well. I'll go add the fast way to the first example problem.

EDIT: also added the calculation for converting to base 10 then to the desired base. Daniel Liu · 2 years, 10 months ago

Log in to reply

To learn the very basics, see This Article Akshaj Kadaveru · 2 years, 10 months ago

Log in to reply

@Akshaj Kadaveru Fixed the link (there was a weird semicolon in that url) David Lee · 2 years, 6 months ago

Log in to reply

@David Lee you didn't fix it? Daniel Liu · 2 years, 6 months ago

Log in to reply

@Akshaj Kadaveru Yes. This. +1 You are amazing. Daniel Liu · 2 years, 9 months ago

Log in to reply

@Daniel Liu huh? this is screwed up. http://www.artofproblemsolving.com/Forum/viewtopic.php?f=721&t=566684 David Lee · 2 years, 5 months ago

Log in to reply

I often resort to this technique in multiple-choice-questions and it saves a lot of time! Another great post! Mursalin Habib · 2 years, 10 months ago

Log in to reply

you are quite interesting! I .......think so....... Archiet Dev · 2 years, 7 months ago

Log in to reply

This is a very fast method for conversion of bases Rohit Nair · 2 years, 10 months ago

Log in to reply

Thanks a lot for shortcut method for answering quickly. Sunil Pradhan · 2 years, 10 months ago

Log in to reply

Thanks a lot for sharing the trick ... :) ... Kiran Dey · 2 years, 10 months ago

Log in to reply

I never knew this before, so yes thank you! The intense math section got a little messy but it was great; thanks for the post. Justin Wong · 2 years, 10 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...