Convert an array of more than 64 bits to a base-10 string

Question

I am trying to roll my own arbitrary size unsigned integer class, but I am having trouble finding a way to convert the std::vector<bool> I am using to store the bits into a base 10 string. Currently, my algorithm is

unsigned long long sum = 0LL;
for(unsigned long long i=0; i<64LL && i<bit_list.size(); i++){
    if(bit_list[i]){
        sum |= 1LL << i;
    }
}
return std::to_string(sum);

However, this only works for numbers below 2^64, because of the limitations of std::to_string and the built in unsigned long long. How would I go about converting, a many bit unsigned int to a string representation of the base 10 conversion? Preferably, I would like the algorithm to be extendable to any number of bits.

Just use a direct representation of the decimal digits. Go through the binary digits and add and double (operations on decimal digits) as appropriate. — Cheers and hth. - Alf, Sep 27 '17 at 18:26
Doesn't std::bitset require a predetermined number of bits at compile time? My class will have a varying number of bits, to conserve memory. — quietsamurai98, Sep 27 '17 at 18:27
Yeah, noticed I was looking at the problem wrong. Would [this](https://stackoverflow.com/questions/29210120/binary-string-to-hex-c) work for you? — NathanOliver, Sep 27 '17 at 18:29
@NathanOliver I think that question is about binary to hex, not binary to decimal. — quietsamurai98, Sep 27 '17 at 18:31
@quietsamurai98 Dang it. Sorry again. Not sure why I searched for hex — NathanOliver, Sep 27 '17 at 18:37
Sadly I'm not finding an old code I had made that does this exact thing. I wrote this basic "bigint" class in JavaScript that would handle virtually any integer number, and perform any arithmetic operation with it. It was so long ago I don't even remember how I did it. — Havenard, Sep 27 '17 at 18:44

score 1 · Accepted Answer · answered Sep 27 '17 at 18:36

1

Pseudo code:

string s;
your_bitlist_class i;
if ( i > 0 )
{
    while ( i > 0 )
    {
        s.insert( 0, std::to_string( i % 10 ) );
        i /= 10;   
    }
}
else
{
    s = "0";
}

Optimization is left as an exercise for the reader.

answered Sep 27 '17 at 18:36

Rob K

8,757
2
32
36

There are two general ways to convert from base A to base B. You can use base B to calculate the value of the base A spec. That's simple and efficient. Or you can use base A to calculate the base B digits, which involves inefficient division, and complexity. You've chosen the inefficient and complex way. – Cheers and hth. - Alf Sep 27 '17 at 18:37
It's general and will work for arbitrary numbers of bits. As I wrote, optimization is left as an exercise... – Rob K Sep 27 '17 at 18:41
Also, appending data to the beginning of the string like that is very expensive. It would be cheaper to just append to the end, and then invert the whole string. You can also use `stringstream` instead of `string` so you don't have to create a temporary `string` object with `to_string` just to be able to insert it in the result. And instead of dividing by 10 you can divide by the highest power of 10 that fits in a regular int (I guess that would be 1000000000), and pad with leading zeros if `i /= 1000000000 > 0`. – Havenard Sep 27 '17 at 18:55

quietsamurai98 · Answer 2 · 2017-09-29T23:25:01.673

EDIT: Please, do NOT use this code! It sucks! I ended up using binary division by 10 with remainder.

Here's the algorithm I found that works well. It's not super efficient, but it gets the job done.

BigInt num_copy(this);
std::vector<unsigned short> digits;
digits.push_back(0);
while(num_copy!=0){
    num_copy--;
    digits[0]++;
    unsigned long long i = 0LL;
    while(digits[i]==10){
        if(digits.size()==(i+1LL)){
            digits.push_back(0);
        }
        digits[i]=0;
        i++;
        digits[i]++;
    }
}
std::string outstr = "";
for(unsigned long long i=0LL; i < digits.size(); i++){
    outstr = std::to_string(digits[i]) + outstr;
}
return outstr;

Convert an array of more than 64 bits to a base-10 string

2 Answers2