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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.