Tips and Tricks: Converting numbers between bases faster

If you find the methods of conversion traditionally taught at school boring and slow, you are not the only one.

From Binary to Decimal

Tip 1: Double dabble

Consider the integer D_nD_n-1...D₁D₀ with (n+1) digits.

Starting with the most significant bit, carry out the following algorithm:

1. Result = D_n
2. Result = Result * 2
3. Result = Result + D_n-1
4. Repeat steps 2 and 3 until you have added the least significant bit to ResultD₀to Result

For example, the number 10100101₂ = 165₁₀

1. Result = 1
2. Result = Result * 2 = 2
3. Result = Result + 0 = 2
4. Result = Result * 2 = 4
5. Result = Result + 1 = 5
6. Result = Result * 2 = 10
7. Result = Result + 0 = 10
8. Result = Result * 2 = 20
9. Result = Result + 0 = 20
10. Result = Result * 2 = 40
11. Result = Result + 1 = 41
12. Result = Result * 2 = 82
13. Result = Result + 0 = 82
14. Result = Result * 2 = 164
15. Result = Result + 1 = 165

This method is essentially the reverse of the repeated division algorithm that we are used to for converting from base 10 and base 2.

Tip 2: Mind the zeros!

Who said you should always use the positional weight of 1s in your calculations? If there are fewer 0s than 1s in the number, consider the following approach:

For example, in the number 11011101₂, there are only 2 zeros. Knowing that 11111111₂ = 255₁₀, and that the missing 1s in 11011101₂ have a simple sum of 32 + 2 = 34. It's relatively easier to calculate the difference between 255 and 34 than to add 128, 64, 16, 8, 4 and 1. Both lead to the same result.

That's it for the time being. Stay tuned for more tips!

Coming up:
- Two's complement conversion tips
- Derivation of the iterative formula