C++ converting binary string to decimal string

Question

I have a binary string that is potentially greater than 64 bits/characters. I would like to convert it into base-10 so that I can output it to the console.

As far as I know, c++ doesn't support any integers greater than 64 bits, with exceptions to compiler specific types. Therefore, I would need to convert the binary string to a base-10 string (as opposed to a base-10 integer) if I want to output it to the console in a human-readable form.

I have the following code...

int char_to_int(const char c) {
    return ((int) c) - 48;
}

std::string string_addition(std::string s1, std::string s2) {
    std::string ret = "";
    // making sure the two strings are the same length
    while(s1.size() > s2.size())
        s2 = '0' + s2;
    while (s2.size() > s1.size())
        s1 = '0' + s1;
    
    // adding and carrying
    for (int32_t i = (int32_t) s1.size(); i >= 0; i--)
        ret[i] = (char) ((char_to_int(s1[i]) + char_to_int(s2[i])) + 48);
    for (int32_t i = (int32_t) ret.size() - 1; i >= 0; i--)
        ...
    // then finally returning
    return ret
}

std::string to_base_ten(const std::string& s) {
    std::string ret = "";
    for (size_t i = 0; i < s.size(); i++) {
        // for each digit, calculate the appropriate number to add
        int64_t temp = s[i] * (int) std::pow(2, i);
        // performing addition with strings because of potential integer overflow issues
        ret = string_addition(ret, std::to_string(temp));
    }

    return ret;
}

...which just gets tedious and hard to read/understand because of converting with strings. Are there any simpler or more efficient ways of accomplishing this task?

Answer 1

Are there any simpler or more efficient ways of accomplishing this task?

I will post this as an answer to the general query of "converting a binary string to a decimal string".

Assuming that the issue has to do with an arbitrary size decimal, then one solution is to use an arbitrary precision library. One such library is boost multiprecision, most notably the boost::multiprecision::cpp_int type.

The following example shows usage of the cpp_int type, as well as the std::accumulate function to build the decimal string, based on the current binary digit being processed:

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
#include <string>
#include <numeric>

namespace mp = boost::multiprecision;

std::string to_base_10(std::string binary_digits)
{
    using Int = mp::cpp_int;
    int curPower = 0;
    return std::accumulate(binary_digits.rbegin(), binary_digits.rend(), Int(),
                    [&](Int total, char ch) 
                    { 
                        if ( ch == '1')  // check if digit is 1
                            total += mp::pow(mp::cpp_int(2), curPower); // equivalent to total + 2^curPower                   
                        ++curPower;  // add 1 to the current power 
                        return total;                            
                    }).str(); // convert the final result to a string
}

int main() 
{
    auto s = to_base_10("10001110000011010101010101111000001101010100111000111000111110001110001111111000000011111111110");
    std::cout << s;
}

Output:

21981495524443696438500395006

The std::accumulate function will process the string from right-to-left (using the reverse iterators rbegin and rend), checking to see if the current digit is 1.

If the digit is 1, then then value of 2^current_power is added to the total. The current power is incremented, and the process is repeated. The str() function is a member of cpp_int that converts the final result to a string.

Also note that there is no string_addition function. It is not necessary when building the cpp_int, which will eventually be converted to a string at the end of the processing.

Answer 2

Are there any simpler or more efficient ways of accomplishing this task?

I've also solved a similar problem of arithmetic with strings without using libraries other than "string" for the solution. To make it more readable, instead of adding a "humand-readable string", you could instead try adding "computer-readable strings", by this I mean that the character representing '0' should just be 0 instead of the human-readable 48, doing this avoids having to convert char to int and back multiple times...

// adding and carrying
for (int32_t i = (int32_t) s1.size(); i >= 0; i--)
    ret[i] = s1[i] + s2[i];
for (int32_t i = (int32_t) ret.size() - 1; i >= 0; i--)

When having to output the string for humans to read, just make a function that iterates through the string and outputs each character corresponding to the "computer readable string" (you may not need the cast to a char)...

void output_number_string(const std::string& s) {
    for (auto l : s)
        std::cout << ((char) (l + '0'));
}

Regarding that "std::pow(2, i)", it's also prone to overflowing, to avoid that you should use you overflow-free functions for the task...

std::string to_base_ten(const std::string& s) {
    std::string ret = "";
    //initialize two_power to be a string of length one containing only the "computer readable one"
    std::string two_power = string(1, 1);
    for (size_t i = 0; i < s.size(); i++) {
        //in binary, you only need to add a power of two when the bit isn't 0
        if (s[i] == 0) continue;
        // performing addition with strings because of potential integer overflow issues
        ret = string_addition(ret, two_power);
        two_power = string_addition(two_power, two_power);
    }
return ret;
}

one extra thing I may have noticed is that the program can't handle the case when the result string is greater than the original strings, but you can just simply insert a '0' at the start of the string after making sure they're the same size:

// making sure the two strings are the same length
ret = '0' + ret;
// ...