Decimal to binary not working for large numbers

[Nebur]

Hey! I am trying to make a program that given a decimal number returns its binary representation. The program must be done using recursivity.

  #include <iostream>
using namespace std;

long long int to_binary (long long int n, long long int d) {
	if (n != 0) return (n%2)*d + to_binary(n/2, 10*d);
	return n; 
}
	

int main () {
	long long int n;
	cin >> n;
	cout << to_binary(n, 1);
}

not very complicated code. It works fine but for large numbers like 1000000000 it doesen't work. How can this be solved?

[Chervil]

Well, it looks like your code is trying to use a sort of pseudo-binary representation where a series of decimal 1 or 0 digits are used to visually represent a binary value.

The problem is, a number such as 1000000000 (decimal) converts to 111011100110101100101000000000 (binary).

But if we treat this as a decimal number : 111011100110101100101000000000
then it is too big to fit in a long long int (it requires 97 bits, but a long long int has only 64).

I think it would be better to have the function return a std::string result, which can have unlimited length.

#include <iostream>
#include <string>

using namespace std;

std::string to_binary(unsigned long long int n, bool flag=false) 
{
    static const std::string digits [2] = {"0", "1"};
    if (n != 0) 
        return to_binary(n/2, true) + digits[n&1];
    
    return (flag) ? "" : "0";
}
    
int main() 
{
    for (int i=0; i<20; i++)
        cout << to_binary(i) << endl;
    
    cout << to_binary(1000000000) << endl;	    
}

The purpose of the bool flag is to suppress the leading zero, except in the case where the input really is zero.
Output:

0
1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111
10000
10001
10010
10011
111011100110101100101000000000

[MarketAnarchist]

I think it would be better to have the function return a std::string result, which can have unlimited length.

a boolean array makes more sense to me. dont you think?

[Nebur]

I haven't learnt yet how to use this "std::" thing and i don't know what it means at all. Besides that, what your code does is to put the 1 and 0 in a string¿

[Chervil]

Yes, you have learned to use this std:: thing already.
Your original code has std::cin and std::cout
By putting using namespace std; you've saved yourself the trouble of typing the std:: each time - which is ok for some simple programs, but is actually bad practice.

Yes, my code puts "1" or "0" in a string. However, it was only by way of an example, Feel free to use the idea and write your own function in a way which you can understand, if you like.

[Nebur]

Ok, thanks a lot for answering.

But i have one doubt: I tried to place the 0 and the 1 in a string before asking for help but i found with some trouble:

First is that I declared the string in the recursive function, and because of that every time that the function executed itself, the string was redeclared and lost (I think thats what happens, but I am not sure).

Also that the function had to be "string to_binary ...." therefore a string had to be returned every time but i didnt know how to do that either :p

[Chervil]

Well, returning a string from a function is just as easy as returning an integer.

If you have some of your own code which doesn't work, then you could post it here for a someone else to look at it, and see where the problems are.

[Nebur]

Is it possible that you make the code a bit simpler?

With the format I used to write mine if possible because i need to do the same for octal and hexadecimal so it would be very nice.

Thanks a lot :)

[Nebur]

what does this line do?

   static const std::string digits [2] = {"0", "1"};

And what's the difference between your code and this:

#include <iostream>
using namespace std;

string to_binary (int n) {
	if (n != 0) {
		if (n%2 != 0) return to_binary(n/2) + "1";
		return "0";		
	}
	return "0";
	
}

int main () {
	int n;
	cin >> n;
	cout << to_binary(n);
}

[Chervil]

What does this do:

    static const std::string digits [2] = {"0", "1"};

It is creating a lookup-table. That is, an array with just two elements. It allows the number 0 to be translated to the string "0" and similar for 1 and "1".

The keyword static means that it doesn't need to be re-created each time the function is called, it retains the same value from one call to the next. const is used because we definitely do not want to change the contents of the table.

And what's the difference between your code and this

Well, partly a matter of style, that is personal preference. Though there is an error in the code you posted. It should be like this:

string to_binary (int n) 
{
    if (n != 0) 
    {
        if (n%2 != 0) 
            return to_binary(n/2) + "1";
        else
            return to_binary(n/2) + "0";
    }
    return "0";
}

[Chervil]

This is the equivalent of my code for hex rather than binary:

std::string to_hex(unsigned long long int n, bool flag=false) 
{
    static const char digits [17] = "0123456789ABCDEF";
    
    if (n != 0) 
        return to_hex(n/16, true) + digits[n & 0x0F];
    
    return (flag) ? "" : "0";
}

Don't let the std:: put you off, I just copy+pasted the same code, which is why it looks similar. I used the binary & operator to get each digit, but you could get an equivalent result using the % operator. The first method is more efficient, but nothing to lose sleep over.

You could do this without using a lookup table, there are hundreds of possible ways to solve the problem.

Quote: Is it possible that you make the code a bit simpler? Well, it depends where you are sitting. What is simple may depend on (a) what you are already familiar with and (b) what you are permitted to use. C++ already has several built-in functions to do these tasks, and that's what I'd normally use. But doing the job using your own code is probably meant to aid learning, where the main benefit is in the process, rather than the result.