Adding an interview to the beginning of a string

[Yaboi Gengarboi]

I'm a beginner to C++ and I'm trying to make a program that takes in a user-determined decimal integer number and prints its standard decimal counterpart. The mathematics behind it is quite simple and I've figured out what to do. I've already written a code in Java that does all of this and it works without error. I'm having issues in C++ however.

Given a number such as 57, it must be divided by 2 continuously. An even number will produce no remainder, which gives a 0 in binary. An odd number will give a remainder of 1, which gives a 1 in binary. This process continues until the number reaches 0. Then all of the remainders are counted from last to first to form the binary number. For 57 it would be 111001 (according to my Java program, which is correct).

Whatever number is entered will be assigned as A, be it 57 or 237, etc. R is the remainder, and that is simply found by using R = A%2. Then A is divided by 2 and the process repreats.

I just need to get all of the remainders to be put together in a string so they can be displayed. Say I have a string X that is initially "". Each time R is found, it needs to be put at the beginning of that string. Once the process of diving A by 2 is done, a nice mess of 0s and 1s should come together.

I just cant figure out how to put the remainder R into the beginning of the string. This is in a while loop so it needs to add onto string X each time. I've tried looking into insert, stringstream and a few others but the scenarios are different such that all I end up with is more errors.

(A and R are integers. String X is "".)

while (A>0) {
          R = A%2;
          //Something to add R to the beginning of string X
          A = A/2;
          if (A==0) {
              cout << "Binary: " << X << endl;
              break;
          }
      }

Can anyone help?

[JLBorges]

#include <iostream>
#include <string>

std::string binary_str( unsigned long long n )
{
    if( n == 0 ) return "0" ;
    else if( n == 1 ) return "1" ;
    else return binary_str( n/2 ) + binary_str( n%2 ) ;
}

int main()
{
    for( unsigned long long n : { -1ULL, 0ULL, 1016ULL, 0b101100111000111100001ULL } )
        std::cout << binary_str(n) << '\n';
}

http://coliru.stacked-crooked.com/a/dec49c2805931bd3

[Thomas1965]

Very strange.
It works on the shell but VS 2017 gives the following error:
Error C4146 unary minus operator applied to unsigned type, result still unsigned

[lastchance]

#include <iostream>
#include <string>
using namespace std;

string binary( unsigned int n )
{
   const string binaryDigits = "01";
   string result;

   if ( n == 0 ) return "0";
   while ( n > 0 )
   {
      result = binaryDigits[n%2] + result;
      n /= 2;
   }

   return result;
}

int main()
{
   for ( int i = 0; i <= 100; i++ ) cout << i << '\t' << binary( i ) << '\n';
}

[Yaboi Gengarboi]

I know how to do the conversion in the program, I just want to know how to put the remainder R into the beginning of the string.

[whitenite1]

@Yaboi Gengarboi

I know how to do the conversion in the program, I just want to know how to put the remainder R into the beginning of the string.

Actually, lastchance does show you how, on line 13.

#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::string;

int main()
{
	int A, R;
	string Remainder="",add="";
	cout << "Enter a whole number.." << endl;
	cin >> A;
	
	while (A>0)
	{
		R = A%2;
		add=(R+48);// Makes add = "0" or a "1"
		Remainder=add+Remainder;
		A/=2;
	}
	cout << "Binary: " << Remainder << endl;

	cin >> A;
}

[Yaboi Gengarboi]

Why the +48?

[Yaboi Gengarboi]

whitenite1, thank you. I added that stuff in and it works. At first I didn't put in the +48 and all the 1s were turned into question marks and the 0s were blank. After I added it it works. Do you know why that is?

[whitenite1]

@Yaboi Gengarboi

The R will equal a 0 or a 1 on line 18, but the ASCII 0 or 1, is a non-printable value. The ASCII value of "0" is 48, and the "1" is 49. So adding 48 to R and assigning that value to add, which is a string variable, makes add a "0" or a "1"

[dhayden]

This is more efficient than combining strings. It builds the string up backwards in a char array.

#include <iostream>
#include <string>

using std::string;

string toBinaryString(unsigned A)
{
    char buffer[sizeof(A)*8+1];		// make sure this is big enough
    char *cp = buffer+sizeof(buffer)-1; // point to the last character
    *cp = 0;				// null terminate it
    
    // Use do/while. Otherwise you'll get wrong answer when A==0
    do {
	unsigned R = A%2;
	*--cp = R + '0';
	A = A/2;
    } while (A);
    return cp;
}

int
main()
{
    std::cout << toBinaryString(57) << '\n';
    std::cout << toBinaryString(0) << '\n';
    std::cout << toBinaryString(1) << '\n';
    std::cout << toBinaryString(12345) << '\n';
    return 0;
}

[uplime]

Aren't VLA's a GNU extension in C++? I thought only C had that? Also, What makes you say it's more efficient than combining strings?

[jlb]

Aren't VLA's a GNU extension in C++?

Yes g++ has an extension to allow VLA in C++.

I thought only C had that?

Yes, C99 has VLA as part of the standard.

However, there are no VLA being used in the code posted, remember sizeof() is a compile time operation so sizeof(A) will produce a compile time constant.

[uplime]

Ah that's right. Shouldn't post before I have my coffee :)

[dhayden]

What makes you say it's more efficient than combining strings?

After computing a digit, the C-string version copies it to a char array and decrements a pointer.

The std::string version creates a 1 character string for the most significant digit. Then it creates a 1 character string for the next digit. Each of these steps may involve allocating space on the heap. Then it combines them into a 2 digit string and destroys the originals. Then it creates a string for the next digit, combines it with the 2 digit string, creating a 3 digit string. then it destroys the 1- and 2-digit strings. The process continues until it assembles all the digits.

If I modify my version to use unsigned long long for consistency and convert 57 using each method 1 million times I get these results:

int
main(int argc, char **argv)
{
    if (argc > 1) {
        std::cerr << "checking cstring\n";
        for (unsigned i=0; i<1000000; ++i) {
            toBinaryString(57);
        }
    } else {
        std::cerr << "checking string\n";
        for (unsigned i=0; i<1000000; ++i) {
            binary_str(57);
        }
    }
    return 0;
}

$ time ./foo
checking string

real    0m1.498s
user    0m1.466s
sys     0m0.015s

dhayden@DHAYDEN4WLGPF2 ~/tmp
$ time ./foo 1
checking cstring

real    0m0.229s
user    0m0.187s
sys     0m0.030s

dhayden@DHAYDEN4WLGPF2 ~/tmp

The user time is almost 8x faster.

Converting larger numbers makes the difference even more apparent. Using the largest unsigned long long I get:

$ time ./foo
checking string

real    0m11.694s
user    0m11.606s
sys     0m0.062s

dhayden@DHAYDEN4WLGPF2 ~/tmp
$ time ./foo 1
checking cstring

real    0m0.385s
user    0m0.343s
sys     0m0.030s

Here the user time is more than 33x faster.

This doesn't mean that you should abandon std::string. Fast code is only worthwhile if it works correctly. In this case, it would be easy to get the size of the buffer wrong.

[jlb]

Also the problem may not really be caused by using a std::string, but with the way the string is being manipulated. Have you considered using the same algorithm for both the C-string and std::string method. Try replacing the C-string with a std::string that has been properly sized and access the string from the back like you are the C-string. Something like:

string toBinaryString(unsigned A)
{
    
    std::string buffer(sizeof(A) * 8 + 1, '\0');
    char *cp = buffer.data() + buffer.size() - 1;// point to the last character
    *cp = 0;				// null terminate it

    // Use do/while. Otherwise you'll get wrong answer when A==0
    do {
	unsigned R = A%2;
	*--cp = R + '0';
	A = A/2;
    } while (A);
    return cp;
}

[JLBorges]

Using std::to_chars with a non-allocating, non-throwing implementation would be expected to perform the fastest possible conversion. https://en.cppreference.com/w/cpp/utility/to_chars

For example:

#include <iostream>
#include <charconv>
#include <system_error>
#include <limits>
#include <string_view>

std::string_view to_base( unsigned long long n, int base )
{
    static char buffer[ std::numeric_limits< unsigned long long >::digits ] ;
    const auto [ p, ec ] = std::to_chars( buffer, buffer + sizeof(buffer), n, base ) ;
    return { buffer, std::size_t(p-buffer) } ;
}

std::string_view binary_str( unsigned long long n ) { return to_base(n,2) ; }

int main()
{
    for( unsigned long long n : { -1ULL, 0ULL, 1016ULL, 0b101100111000111100001ULL } )
        std::cout << binary_str(n) << '\n';
        
    for( int i = 0 ; i < 1'000'000 ; ++i ) binary_str( -1ULL ) ;    
}

http://coliru.stacked-crooked.com/a/61d76ee2baffa03c

[dhayden]

jlb writes:

Also the problem may not really be caused by using a std::string, but with the way the string is being manipulated.

True.

Try replacing the C-string with a std::string that has been properly sized and access the string from the back like you are the C-string.

That's certainly possible, but why do it that way? Why contort your way into a fixed-length buffer when there's a perfectly simple way to do it? Std::string offers no benefit (that I can see) when used this way.

JLBorges writes:

Using std::to_chars with a non-allocating, non-throwing implementation would be expected to perform the fastest possible conversion

That's pretty cool. For those reading along, this is in C++17 and hasn't made it to the reference section of this website yet. See https://en.cppreference.com/w/cpp/utility/to_chars.