Adding strings of integers

Question

I'm trying to write an algorithm for a larger project that will take two strings which are both large integers (only using 10 digit numbers for the sake of this demo) and add them together to produce a final string that accurately represents the sum of the two original strings. I realize there are potentially better ways to have gone about this from the beginning but I am supposed to specifically use strings of large integers as opposed to a long integer.

My thinking was to take the two original strings, reverse them so their ones position, tens position, and so on all line up properly for adding. Then one position at a time, convert the characters from the strings to single integers and add them together and then use that sum as the ones position or otherwise for the final string, which once completed will also be reversed back to the correct order of characters.

Where I'm running into trouble I think is in preparing for the event in which the two integers from the corresponding positions in their strings add to a sum greater than 9, and I would then have carry over some remainder to the next position. For example, if I had 7 and 5 in my ones positions that would add to 12, so I would keep the 2 and add 1 to the tens position once it looped back around for the tens position operation.

I'm not getting results that are in any way accurate and after spending a large amount of time stumbling over myself trying to rectify my algorithm, I am not sure what I need to do to fix this.

Hopefully my intended process is clear and someone will be able to point me in the right direction or correct some mistake I may have in my program.

Thanks in advance.

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

int main()
{
    string str1 = "1234567890", str2 = "2345678901"; //Two original strings of large integers
    string rev_str1, rev_str2;
    int int1 = 0, int2 = 0;
    string final; //Final product string, sum of two original strings
    int temp_int = 0, buffer_int, remainder = 0;
    string temp_str = "", buffer_str;
    char buffer[100] = {0};

    cout << "str1 = " << str1 << endl;
    cout << endl;
    cout << "str2 = " << str2 << endl;
    cout << endl;

    rev_str1 = string(str1.rbegin(), str1.rend());
    rev_str2 = string(str2.rbegin(), str2.rend());

    for (int i = 0; i < 10; i++)
    {
        buffer_str = rev_str1.at(i);
        int1 = atoi(buffer_str.c_str());
        buffer_str = rev_str2.at(i);
        int2 = atoi(buffer_str.c_str());
        buffer_int += (int1 + int2 + remainder);
        remainder = 0;

        while (buffer_int > 9)
        {
            buffer_int -= 10;
            remainder += 10;
        }

        temp_str = itoa(buffer_int, buffer, 10);
        final += temp_str;
    }

    final = string(final.rbegin(), final.rend());

    cout << "final = " << final << endl;
    cout << endl;
}

Isn't what you're asking for basically a BigInteger implementation using a char array? — Rapptz
– Rapptz, Commented Jan 29, 2013 at 5:49
A few implementation comments, not related to the correctness of the program: Why don't you use the reverse iterators directly to iterate through the strings? Also, std::string::at(size_t) returns a char which you can directly add up if you subtract the value of '0', no need for an intermediate std::string and atoi(). Lastly, there's certainly no need for itoa(), just add the value of '0' and append. Lastly, you could pre-allocate the result string and also iterate over it, at most it is one digit longer than the longer of the input strings. — Michael Wild
– Michael Wild, Commented Jan 29, 2013 at 7:28
First make it work for strings with zero length, then length 1, then length 2, then differing lengths, etc. — Open AI - Opting Out
– Open AI - Opting Out, Commented Jan 29, 2013 at 7:51

Michael Wild · Accepted Answer · 2013-01-29 08:44:39Z

Here's what I came up with. It is just for two summands; if you have more, you'll have to adapt things a bit, in particular with the carry, which can then be larger than 19, and the way the result string is allocated:

#include <iostream>
#include <string>

using namespace std;

int main()
{
    // Two original strings of large integers
    string str1 = "1234567890",
           str2 = "2345678901234";

    // Zero-padd str1 and str2 to the same length
    size_t n = max(str1.size(), str2.size());
    if (n > str1.size())
        str1 = string(n-str1.size(), '0') + str1;
    if (n > str2.size())
        str2 = string(n-str2.size(), '0') + str2;

    // Final product string, sum of two original strings.
    // The sum of two integers has at most one digit more, for more inputs make
    // below reverse_iterator a back_insert_iterator, then reverse the result
    // and skip the removal of the padding.
    string final(n+1, '0');

    // The carry
    char carry = 0;

    // Iterators
    string::const_reverse_iterator s1 = str1.rbegin(), e = str1.rend(),
                                   s2 = str2.rbegin();
    string::reverse_iterator f = final.rbegin();

    // Conversion
    for (; s1 != e; ++s1, ++s2, ++f)
    {
        // Bracketing to avoid overflow
        char tmp = (*s1-'0')+(*s2-'0') + carry;
        if (tmp > 9)
        {
            carry = 1;
            tmp -= 10;
        }
        else
        {
            carry = 0;
        }
        *f = tmp + '0';
    }
    final[0] = carry + '0';

    // Remove leading zeros from result
    n = final.find_first_not_of("0");
    if (n != string::npos)
    {
        final = final.substr(n);
    }

    cout << "str1 = " << str1 << endl
         << "str2 = " << str2 << endl
         << "final = " << final << endl;
}

Thanks, I changed a couple of things but your algorithm helped me out a lot. I appreciate it. Also, that was definitely a cleaner way of going about it than I had originally.

Gabe · Accepted Answer · 2013-01-30 13:15:10Z

4

Your problem is that you are carrying 10s instead of 1s. When you add 19 + 5, you get 4 in the units position and add an extra 1 in the 10s position. You wouldn't add an extra 10 in the 10s position.

You simply need to change this line: remainder += 10; to remainder += 1;.

Also, that while loop isn't necessary if you have more than two addends. As it is, when you are adding only two digits at a time, the largest addends you can have are 9 + 9, which carries only 1.

edited Jan 30, 2013 at 13:15

answered Jan 29, 2013 at 7:18

Gabe

87.1k13 gold badges144 silver badges238 bronze badges

3 Comments

Agentlien Over a year ago

Nice solution. :) Tiny clarification, though. Even with more addends, you could avoid the while loop by simply taking the digit sum modulo ten, which immediately gives you the rest. This is clearer code and will only cost as much as one division.

Gabe Over a year ago

@Agentlien: If you think that one division costs less than several iterations of that while loop, remember that some architectures don't even have an integer division instruction, and it's pretty slow on those that do. I welcome speed comparisons, though.

Agentlien Over a year ago

You have a good point, and that's why I said that it would "only cost as much as one division", rather than making a claim about which is faster in practice. On architectures which do support a division instruction, I would expect it to be faster, even if division is an expensive operation. On those that don't, well.. I find the modulo version to be cleaner, more readable code. If at a later point you realize this is too slow in practice. Well, that's when you should look at for which hardware this should be optimized and which version is faster for that particular architecture...

Ali Khan · Accepted Answer · 2017-03-08 20:35:28Z

-2

#include<iostream>

using namespace std; main(){

int sum =0;
int a;
int reminder;
cout<<"Enter the Number :"<<endl;
cin>>a;
while(a>0){
    reminder=a%10;
    sum=r+sum;
    a=a/10;`enter code here`

}
cout<<"Additon is :"<<sum<<endl;

}

answered Mar 8, 2017 at 20:35

Ali Khan

11 bronze badge

Collectives™ on Stack Overflow

Adding strings of integers

3 Answers 3

1 Comment

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related