Converting a base ten number to base two

[Lacrimosus]

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.

[MXP]

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

[Alvaro]

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.

[The_Grey_Beast]

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.

[Safari]

Another way.

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

[Alvaro]

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]