## Converting a base ten number to base two

Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

### Converting a base ten number to base two

Okay, I have an algorithm that converts binary to base ten, but not vice versa. I can't seem to figure out how to convert a base ten to a base two. My problem is not programming, but the mathematics itself. Please, explain the process of converting a base ten number into binary. I'd prefer if you explained it in a C++ function, but plain English is fine as well.
Lacrimosus

Posts: 5
Joined: Wed May 11, 2005 9:40 pm

A number can be represented as the sum of powers of some base. For example 1604 can be written as 1 * 10^3 + 6 * 10^2 + 0 * 10^1 + 4 * 10^0. A binary number 1101 can be represented in a similar way: 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0. Integer division in C++ can help you find the multiple on each power. For example 1604 / 10^3 = 1, 604 / 10^2 = 6, 4 / 10^1 = 0, 4 / 10^0 = 4 and a similar method works with base 2.

This implies a method of converting between bases. Given a number X, you can convert it to any base N by first finding the largest power of N, we'll say this is p, such that X / N^p != 0. You can find p using logarithms. p = ln X / ln N. Your algorithm will continue like this:

while p >= 0
1. output X / N^p
2. X = X - N^p
3. p = p - 1

To convert to base 2, just set N = 2
Need information on a function I've posted? Chances are it's at the MSDN.
MXP

Posts: 6506
Joined: Mon Sep 22, 2003 5:27 pm

I think about it in a slightly different way. The last digit of a binary representation is 0 for even numbers and 1 for odd numbers. Actually, that digit is just the remainder of the division by 2. Dropping the last digit is the same thing as dividing by two rounding down (just as in base ten dropping the last digit is dividing by ten rounding down). So just divide your number by two rounding down and start the process again to find the other digits.

For example:
35 is odd => 1
17 is odd => 1
8 is even => 0
4 is even => 0
2 is even => 0
1 is odd => 1
Collect all the binary digits to get 100011.

A recursive function is an elegant way to implement this.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

Actually, a loop can be a lot faster and better.

Code: Select all
`while(n){  if(n&1)    /* put the digit '1' */  else    /* put the digit '0' */  n>>=1;  // divide by 2}`

Actually, I know even a more better way (I created it for my programs a while ago) written in assembly language, but the method above is pretty fast.
There is something in each of us we don't know. Something with great power.

The_Grey_Beast

Posts: 196
Joined: Mon Jun 28, 2004 9:03 am
Location: Romania

Another way.

[syntax="cpp"]char buffer[33];
cout << itoa(1234, buffer, 2);[/syntax]

Safari

Posts: 1362
Joined: Sun Sep 19, 2004 11:07 am

No such thing as itoa in my compiler. That's just not standard.

The Grey Beast's code has the small problem that you have to reverse the digits. Recursion does that for you. You are also not getting the right behaviour for 0. If your function to write a number in binary is a bottleneck, then I would worry about its performance. Until then, I'll stick to my recursive function.

[syntax="cpp"]void binary(ostream &o, unsigned x){
o << x%2;
if(x>=2)
binary(o,x/2);
}
[/syntax]

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

### Who is online

Users browsing this forum: No registered users and 1 guest