From Binary to Octal, Base 4 to Base 16

Date: 01/20/2003 at 01:43:50
From: Marc Schulman
Subject: Converting from one base (base 2) to base 8

How do I convert numbers from one base to another without converting 
to a base 10 equivalent first?  Is there a shortcut or formula for 
this?

Date: 01/20/2003 at 02:46:48
From: Doctor Mike
Subject: Re: Converting from one base (base 2) to base 8

Marc,

From your Subject line, you want to go from binary to octal, that is, 
from base 2 to base 8. Fortunately that is very fast and simple.  

Given a binary number you start by grouping the binary "1" and "0" 
digits in groups of 3, starting at the right. Then convert each of 
these groups into one octal digit. Done!

Example:

      binary number = 11001100010
      grouped in 3s = 11 001 100 010
      3s into octal =  3   1   4   2

So, the base 2 number 11001100010 equals 3142 in base 8.

I hope this is what you were looking for. If your interest is broader, 
like converting form base 5 to base 7, then there is no shortcut.

- Doctor Mike, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 01/20/2003 at 20:39:51
From: Marc Schulman
Subject: Converting from one base (base 2) to base 8

Dr. Mike,

Thanks for your helpful reply. Does the same type of grouping help 
for bases that are multiples of other bases? For example, from base 
5 to base 20 or base 4 to base 16?  Thanks.

Marc Schulman

Date: 01/21/2003 at 01:07:11
From: Doctor Mike
Subject: Re: Converting from one base (base 2) to base 8
  
Marc,

Glad it helped.  Here's some additional info.
  
It does not work for 5 and 20 but it does work for 4 and 16. If you 
have a number like 12132 in base 4, you group the digits in pairs from 
the right, as "01 21 32" and rewrite converting each of those 2-digit 
base 4 numbers to one base-16 digit, giving 19E in hexadecimal.  
  
Perhaps you don't see right off why we take pairs in this situation 
and groups of 3 in the other. Here is why it works. It is all related 
to the Distributive Law, which says that for any 3 numbers x, y, and 
z, (x + y)*z = x*z + y*z. That is how you "multiply out" if you go 
from the left side to the right side. If you have something like what 
is on the right side, this tells you how to "factor out" the z. Let's 
use that. The base 4 number 12132 stands for the base 10 expression
  
   1*4^4 + 2*4^3 + 1*4^2 + 3*4^1 + 2*4^0
  
where the "^" indicates a power or exponent. Since 4^1 is just 4 and 
4^0 is 1, this can also be written as 
  
   1*4^4 + 2*4^3 + 1*4^2 + 3*4 + 2  
  
Now, to make the next step clearer, I'll add some parentheses to focus 
attention on parts of the expression.
   
   1*4^4 + (2*4^3 + 1*4^2) + (3*4 + 2)
  
Here is a clue as to where we are heading. All this is in terms of 
powers of 4. That makes sense, because it is in base 4. But if we want 
to convert to base 16, we want to have things in terms of powers of 
16.  So, what I am going to do is to convert the powers of 4 to powers 
of 16 as much as possible. I will do one very small step here first, 
so you can see the kind of thing I'm up to.
  
   1*4^4 + (2*4*16 + 1*16) + (3*4 + 2)  
   
It's important that you understand why this change gives an equivalent 
expression. (Also, this shows why the method works only when the 
larger base is a power of the smaller base, as 8 is a power of 2 for 
the original example, and 16 is a power of 4 in this example.) Now we
factor out the 16 to get another equivalent expression.
   
   1*4^4 + (2*4 + 1)*16 + (3*4 + 2)   
  
Next, I'll rewrite the 4^4 as 16^2 on the left to get 
  
   1*16^2 + (2*4 + 1)*16 + (3*4 + 2) 
  
and then evaluate the expressions in parentheses to get
  
   1*16^2 + (9)*16 + (14)  
  
We're almost there.  Because 16^1=16 and 16^0=1, we get
   
   1*16^2 + 9*16^1 + 14*16^0  
  
This is now an expression involving powers of 16, each of which is 
multiplied by a number less than 16.  From the definition of base 16 
number representation, and using the symbols 0, 1, 2, 3, 4, 5, 6, 7, 
8, 9, A, B, C, D, E, and F to represent all the required digit values 
from 0 up to one less than the base, we can automatically read off 
that the hexadecimal representation for this expression is 
  
   19E   
  
Similar logic works to show why the original binary to octal technique 
works. Follow the example above and do it to satisfy yourself why and 
how that works. In that case, you are going from powers of 2 to powers 
of 8. 
  
I said this type of conversion technique works only when the larger 
base is a power of the smaller. Strictly, that is true. But a closely 
related process works when the two bases are BOTH powers of something 
smaller.  Converting from octal to hexadecimal is fairly easy if you 
do it in two steps. First convert from octal to binary, and then 
convert from binary to hexadecimal.

Note that octal to binary is just the opposite of binary to octal. 
When going in that direction, you don't "group" but you "un-group." 
Example:  For octal 275, expand all the octal digits to get 10 111 
101, to see that the binary equivalent is 10111101. Then re-group in 
bunches of four as 1011 1101, from which you get BD in base 16.

You will have to work out a number of concrete examples yourself to 
really absorb all of this.  But now you have the tools and basic ideas 
for doing that.

Go to it.  

- Doctor Mike, The Math Forum
  http://mathforum.org/dr.math/