# Convert numbers from one base to another using repeated divisions.

I have a homework assignment for my programming class to implement an algorithm that can convert from bases 2 trough 16 to any other base from 2 trough 16 but with a few twists.

What I need to understand though is how do I convert from a greater base to a lesser one (ex: 16 - 5 / 12 - 4) using repeated divisions. I would prefer if the examples have un-natural bases (so no decimal and no quick conversions 2-4-6-8-16).

I simply don't understand how this works so I'd appreciate a very basic explanation (dumbed down as much as possible)

I also don't need very general explanations(at first any way) but rather a very detailed step by step example.

I tried 156 (base 16) to base 10 but I know I didn't do it right: 156 / 10 = 15 r6 15 / 10 = 1 r5 1 / 10 = 0 r1 but result should be 324 not 651 (what I got) soooo what am I doing wrong ? (I'm guessing everything)

or is it something like this ??? 156 / 10 = 0 r1 (using just first number) => 1*16+5= 21 (which then has or doesn't have to be converted to base 16 ???) 21 / 10 = 2 r1 6 / 10 = 0 r6 and this would give me 620 but not 342.

I am just 100% confused, have no idea what is going on.

-
Psychologically, I think the easiest thing to do would be to convert everything into base $10$ and then convert to the new base, but this seems inefficient. – Dylan Moreland Dec 18 '11 at 22:56
I need to be able to change directly from bases 2-16 to, again, 2-16 directly ... I also have a to do what you mentioned, but first thing's first – Kalec Dec 18 '11 at 23:06
Also: in your example, $156_{16} = (1\cdot 16^2 + 5\cdot 15 + 6)_{10} = 342_{10}$ is the decimal representation. I think this use of subscripts to keep track of bases is pretty common. – Dylan Moreland Dec 18 '11 at 23:09
Thank you all very much, now I fully understand how this works. For anyone else having trouble, the answer by Brian M. Scott (the accepted answer) should explain everything you needed to know. – Kalec Dec 28 '11 at 12:37
I'm curious. How are you going to implement the general case of the accepted answer in an actual program? Will you be putting all the multiplication tables for all the bases into lookups? I would agree with the other answers that, for actual implementation, you will have to use base 10 (int/long/bigint/...) for intermediate values in almost any language. – Rick Goldstein May 13 '14 at 23:26

Here are a couple of examples, the first with almost full detail, the second with less.

First I’ll convert $156_{\text{sixteen}}$ to base ten using repeated division in base sixteen. I’ll use $A,B,C,D,E$, and $F$ for the base sixteen digits corresponding to base ten $10,11,12,13,14$, and $15$. I’ll also use a subscript $s$ to indicate that a number is to be interpreted in base sixteen.

Divide $156_s$ by $A_s$. Do this just as you would in base ten: $A_s$ won’t go into $1_s$, but it will go into $15_s$. In fact $15_s=1\cdot 16+5=21$, and $A_s=10$, so it goes twice. The first digit of your quotient is $2_s$, so you need to subtract $2_s\cdot A_s$ from $15_s$.

$2_s\cdot A_s=2\cdot 10=20=1\cdot16+4=16_s$, and $15_s-14_s=1_s$, so after you bring down the $6_s$, you’re left dividing $A_s$ into $16_s$.

Similarly, $16_s=1\cdot 16+6=22$, so $A_s$ goes in twice. After you repeat the previous step (with suitable minor modifications) you have your full quotient $22_s$ and overall remainder $2_s$, as shown below.

$$\begin{array}{} &&&2&2\\ &&\text{_}&\text{_}&\text{_}\\ A&)&1&5&6\\ &&1&4\\ &&-&-&-\\ &&&1&6\\ &&&1&4\\ &&&-&-\\ &&&&\color{red}2 \end{array}$$

Now divide $22_s$ by $A_s$. $22_s=2\cdot 16+2=34$, so the integer part of the quotient is $3_s$:

$$\begin{array}{} &&&3\\ &&\text{_}&\text{_}\\ A&)&2&2\\ &&1&E\\ &&-&-\\ &&&\color{red}4\\ \end{array}$$

Finally, divide this last quotient, $3_s$, by $A_s$:

$$\begin{array}{} &&0\\ &&\text{_}\\ A&)&3\\ &&0\\ &&-\\ &&\color{red}3\\ \end{array}$$

Read off the red remainders in reverse order: $156_s=342$.

Here’s one a little more complicated, the conversion of $2BA_s$ to base three.

$$\begin{array}{ccccc|cccc|cccc|cccc|ccc} &&&E&8&&&4&D&&&1&9&&&&8&&&\color{red}2\\ &&\text{_}&\text{_}&\text{_}&&&\text{_}&\text{_}&&&\text{_}&\text{_}&&&\text{_}&\text{_}&&&\text{_}\\ 3&)&2&B&A&3&)&E&8&3&)&4&D&3&)&1&9&3&)&8\\ &&2&A&&&&C&&&&3&&&&1&8&&&6\\ &&-&-&-&&&-&-&&&-&-&&&-&-&&&-\\ &&&1&A&&&2&8&&&1&D&&&&\color{red}1&&&\color{red}2\\ &&&1&8&&&2&7&&&1&B\\ &&&&-&&&-&-&&&-&-\\ &&&&\color{red}2&&&&\color{red}1&&&&\color{red}2 \end{array}$$

That last quotient of $2$ is less than the divisor, so the next division will have a $0$ quotient and remainder of $\color{red}2$, so I’ve skipped the step and colored the quotient instead. Reading the remainders in reverse order, we have $2BA_s=221212_t$ (where the subscript $t$ indicates base three).

Check: $$2BA_s=2\cdot 256+11\cdot16+10=698\;,$$ and $$221212_t=2\cdot 243+2\cdot81+1\cdot27+2\cdot9+1\cdot3+2=698\;.$$

-
thank you very much. I have been so confused even though now it seems simple. Again, thank you. – Kalec Dec 19 '11 at 14:24

I agree with your comment that it is easiest to, as an intermediary, convert to decimal. Note the Wikipedia link that comments on the difficulty of directly converting between two bases that aren't decimal. Computationally, as long as you don't use a recursive algorithm, the conversion should be fast enough that "inelegance" doesn't mean "slowness".

So, convert to decimal first. Reducing to a solved problem is always a good way to do.

Hope that helps, Mike

-

Uh, okay, I think I see the problem: you're seriously mixing up your bases, as well as the order of digits. So for clarity I'll use the standard notation: anytime I mean a base-16 number I'll preface it with 0x (for example 0x42, 0x7A, etc.) and otherwise you can assume I mean base 10.

So let's convert 0x156 into base 10. What you did was actually a conversion from base 16 to base 16:
0x156/0x10=0x15 r 0x6 (this gives you the lowest digit, not the highest)
0x15/0x10=0x1 r 0x5
0x1/0x10=0x0 r 0x1
When you put these three digits together you get 0x156 (not 0x651) which, unsurprisingly, is what you started with. Now let's do a correct conversion to base 10. Note that 10=0xA, so we get (as I encourage you to check):
0x156/0xA=0x22 r 0x2
0x22/0xA=0x3 r 0x4
0x3/0xA=0x0 r 0x3

Complications will arise when converting from one base to a significantly smaller base (for example, base 16 to base 5) but this should at least get you started on the right track.

-
wait ... why is ox156/oxA = ox22 r ox2 ? – Kalec Dec 18 '11 at 23:18
Do long division, keeping track of the base-10 equivalents of the base-16 numbers: 0xA (=10) goes into 0x15 (=16+5=21) twice, with remainder 0x1. Pull down the 0x6; 0xA goes into 0x16 (=16+6=22) twice, with remainder 0x2. So all in all we get 0x156/0xA=0x22 r 0x2. – Skatche Dec 18 '11 at 23:35
Ok, now I finally understand how it works, thank you. But how do we uhm ... re-form the number in it's base 10 equivalent ? – Kalec Dec 18 '11 at 23:46
This works fine for smaller bases. 0x156/0x5=0x44 r2 0x44/0x5=0xD r3 0xD/0x5=0x2 r 3, so $0x156_{16}=2332_5$ – Ross Millikan Dec 19 '11 at 0:00

the issue you have is that $156_{16}/10_{10}\neq 15_{16} \ r6$ but $156_{16}/A_{16} = 22_{16} \ r2$

edit: if we do the long division: ($A_{16}*2 = A_{16}+A_{16} = (A_{16}+ 6_{16}) + 4_{16} = 10_{16} + 4_{16}=14_{16}$)

1 5 6 | A
1 4   | 22
1 6 |
1 4
2


now you just have to memorize the multiplication tables of 1 through 16 in base 16 to do this rapidly

-
wait ... why is ox156/oxA = ox22 r ox2 ? – Kalec Dec 18 '11 at 23:18
check my edit :) – ratchet freak Dec 18 '11 at 23:29
I know I'm being annoying now, but it's just mind boggling how my teachers could have flew trough all this without mentioning almost anything. We had some trite examples and went on. This is just too much for me. why would you even do A*2 ? .... ohhhhh 15 is not consider E but instead it's F + 5 ... so A fits in twice as 14 leaving 1 then you lower 6 ... A fits twice again and you are left with 2. Ok, starting to get this now. – Kalec Dec 18 '11 at 23:33
Oh, but how do we re-form the number into it's base 10 equivalent ? – Kalec Dec 18 '11 at 23:49

To convert hexadecimal to binary you can take the base 16 number, find the largest power of 2 that goes into it, do $x_{16} \bmod 2^y$ and just keep going until you reach the last power of 2 which is $2^0$.

To convert binary to hexadecimal you can divide the binary number into groups of 4 from right to left and convert those nibbles (that's what a group of 4 bits is called) into hexadecimal.

I am using $x_y$ to mean x in base y.

-