I have 2 strings, both contain only numbers. Those numbers are bigger than max of uint64_t.
How can I still add these 2 numbers and then convert the result to string?
4 Answers
Well, you can either use a bigger datatype (for example a library that deals with large integers), or you can quickly knock up your own.
I would suggest that if this is a one off, you do long addition exactly like you would have learned to do in your first few years of school. You can operate directly on the two strings, add the columns, do the 'carry', and build another string containing the result. You can do all this without any conversion to or from binary.
Here. Just for fun, I knocked up a solution for you:
string Add( const string& a, const string& b ) { // Reserve storage for the result. string result; result.reserve( 1 + std::max(a.size(), b.size()) ); // Column positions and carry flag. int apos = a.size(); int bpos = b.size(); int carry = 0; // Add columns while( carry > 0 || apos > 0 || bpos > 0 ) { if( apos > 0 ) carry += a[--apos] - '0'; if( bpos > 0 ) carry += b[--bpos] - '0'; result.push_back('0' + (carry%10)); carry /= 10; } // The result string is backwards. Reverse and return it. reverse( result.begin(), result.end() ); return result; } Note that, for clarity, this code doesn't even attempt to handle errors. It also doesn't do negatives, but it's not hard to fix that.
1 Comment
paxdiablo
Nice use of the carry for the sum as well, I've not seen it done that way before - it reduces code size nicely.
You need a a BigInt implementation. You can find several different ones here.
Whatever BigInt implementation you choose, needs to have conversion to and from string (they usually do).
Comments
Here is the code for your question:
#include <iostream> #include <string> using namespace std; string StrAdd(string a, string b) { string::reverse_iterator rit_a = a.rbegin(); string::reverse_iterator rit_b = b.rbegin(); string c; int val_c_adv = 0; while(rit_a != a.rend() && rit_b != b.rend() ) { int val_a_i = *rit_a - '0'; int val_b_i = *rit_b - '0'; int val_c_i = val_a_i + val_b_i + val_c_adv; if(val_c_i >= 10 ) { val_c_adv = 1; val_c_i -= 10; } else { val_c_adv = 0; } c.insert(0,1, (char)(val_c_i+'0')); ++rit_a; ++rit_b; } if(rit_a == a.rend() ) { while( rit_b != b.rend() ) { int val_b_i = *rit_b - '0'; int val_c_i = val_b_i + val_c_adv; if(val_c_i >= 10 ) { val_c_adv = 1; val_c_i -= 10; } else { val_c_adv = 0; } c.insert(0, 1, (char)(val_c_i+'0')); ++rit_b; } } else if( rit_b == b.rend() ) { while( rit_a != a.rend() ) { int val_a_i = *rit_a - '0'; int val_c_i = val_a_i + val_c_adv; if(val_c_i >= 10 ) { val_c_adv = 1; val_c_i -= 10; } else { val_c_adv = 0; } c.insert(0, 1, (char)(val_c_i+'0')); ++rit_a; } } return c; } int main() { string res, a, b; cout << "a=" << endl; cin >> a; cout << "b=" << endl; cin >> b; res = StrAdd(a, b); cout << "Result=" << res << endl; } 
Comments
If you just want to handle positive numbers without having to worry about bringing in an entire bignum library like GMP (along with its tendency to just abort on out-of-memory errors, something I find unforgivable in a general purpose library), you can roll your own, something like:
static std::string add (const std::string& num1, const std::string& num2) { // Make num1 the wider number to simplify further code. int digit, idx1 = num1.length() - 1, idx2 = num2.length() - 1; if (idx1 < idx2) return add (num2, num1); // Initialise loop variables. int carry = 0; std::string res; // reserve idx1+2 chars if you want. // Add digits from right until thinner number finished. while (idx2 >= 0) { digit = num1[idx1--] - '0' + num2[idx2--] - '0' + carry; carry = (digit > 9); res.insert (0, 1, (digit % 10) + '0'); } // Then just process rest of wider number and any leftover carry. while (idx1 >= 0) { digit = num1[idx1--] - '0' + carry; carry = (digit > 9); res.insert (0, 1, (digit % 10) + '0'); } if (carry) res.insert (0, 1, '1'); return res; } You can add efficiencies like reserving space in the target string in advance, and setting specific indexes of it rather than inserting but, unless you're handling truly massive strings or doing it many time per second, I usually prefer code that is simpler to understand and maintain .
uint64_t, add them, and carry the extra digits to the next addition.