[编程题]无线OSS－高精度整数加法

矫情吗；* 2022-09-30 12:54 100阅读 0赞

> Talk is cheap, show me the code.

### 一、问题描述 ###

在计算机中，由于处理器位宽限制，只能处理有限精度的十进制整数加减法，比如在32位宽处理器计算机中，参与运算的操作数和结果必须在-231~231-1之间。如果需要进行更大范围的十进制整数加法，需要使用特殊的方式实现，比如使用字符串保存操作数和结果，采取逐位运算的方式。如下：

9876543210 + 1234567890 = ?

让字符串 num1=”9876543210”，字符串 num2=”1234567890”，结果保存在字符串 result = “11111111100”。

\-9876543210 + (-1234567890) = ?

让字符串 num1=”-9876543210”，字符串 num2=”-1234567890”，结果保存在字符串 result = “-11111111100”。

要求编程实现上述高精度的十进制加法。要求实现方法：

public String add (String num1, String num2)

【输入】

num1：字符串形式操作数1，如果操作数为负，则num1的前缀为符号位’-‘

num2：字符串形式操作数2，如果操作数为负，则num2的前缀为符号位’-‘

【返回】

保存加法计算结果字符串，如果结果为负，则字符串的前缀为’-‘

注：(1)当输入为正数时，’+’不会出现在输入字符串中；当输入为负数时，’-‘会出现在输入字符串中，且一定在输入字符串最左边位置；

(2)输入字符串所有位均代表有效数字，即不存在由’0’开始的输入字符串，比如”0012”, “-0012”不会出现；

(3)要求输出字符串所有位均为有效数字，结果为正或0时’+’不出现在输出字符串，结果为负时输出字符串最左边位置为’-‘。

**输入描述：**

输入两个字符串

**输出描述：**

输出给求和后的结果

**输入例子：**

9876543210
    1234567890

**输出例子：**

11111111100

### 二、解题思路 ###

这道题应该考虑多种情况，正整数和正整数相加，正整数和负整数相加，负整数和负整数相加，牛客网上这道题因为给出的测试用例没有覆盖全，很多人的解法就只考虑了正整数和正整数相加，但是我认为是不完整的，应该考虑完整，以下是我实现的算法：

#include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    string addTwoPositiveNum(string s1, string s2)   //两个正整数相加
    {
        string res = "";
        int carry = 0;
        string s3 = (s1.size() >= s2.size())?s1:s2;
        string s4 = (s1.size() >= s2.size())?s2:s1;
        int i = s4.size()-1;
        int j = s3.size()-1;
        while(i >= 0)
        {
           int temp = (s4[i]-'0') + (s3[j]-'0') + carry;
           if(temp > 9)
           {
            res += to_string(temp%10);
            carry = temp/10;
           } else {
            res += to_string(temp);
            carry = 0;
           }
           i--;
           j--;
        }
        if(s3.size() > s4.size())
        {
            for(int i = s3.size()-s4.size()-1; i >= 0; i--)
            {
                int temp = (s3[i]-'0') + carry;
                if(temp > 9)
                {
                    res += to_string(temp%10);
                    carry = temp/10;
                } else {
                    res += to_string(temp);
                    carry = 0;
                }
            }
        }
        if(carry != 0)
        {
    
            res += to_string(carry);
    
        }
        reverse(res.begin(), res.end());
        return res;
    }
    string addDifferentNum(string s1, string s2)   //正整数和负整数相加
    {
        string res = "";
        int carry = 0;
        if(s2.length() <= s1.length() || (s2.length() == (s1.length()+1) && s2.substr(1) <= s1))
        {
            int j = s1.length()-1;
            for(int i = s2.length()-1; i > 0; i--, j--)
            {
                int temp = s1[j] - carry - s2[i];
                if(temp >= 0)
                    carry = 0;
                while(temp < 0)
                {
                    carry++;
                    temp = carry*10 + temp;
                }
                res += to_string(temp);
            }
            if(s1.length() >= s2.length())
            {
                for(int i = s1.length()-s2.length(); i >= 0; i--)
                {
                    int temp = s1[i] - carry;
                    if(temp >= 0)
                        carry = 0;
                    while(temp < 0)
                    {
                        carry++;
                        temp += carry*10;
                    }
                    res += to_string(temp);
                }
            }
            while(res[res.length()-1] == '0')
            {
                res = res.substr(0, res.length()-1);
            }
        } else {
            string s3 = "-" + s1;
            string s4 = s2.substr(1);
            res = addDifferentNum(s4, s3);
            res += "-";
        }
        reverse(res.begin(), res.end());
        return res;
    }
    
    string add(string s1, string s2)
    {
        int carry = 0;
        string res = "";
        if(s1[0] == '-')
        {
            if(s2[0] == '-')
            {
                res += "-";
                res = res + addTwoPositiveNum(s1.substr(1), s2.substr(1));
            }
            if(s2[0] >= '0' && s2[0] <= '9')
            {
                res = addDifferentNum(s2, s1);
            }
        }
        if(s1[0] >= '0' && s1[0] <= '9')
        {
            if(s2[0] >= '0' && s2[0] <= '9')
                res = addTwoPositiveNum(s1, s2);
            if(s2[0] == '-')
                res = addDifferentNum(s1, s2);
        }
        return res;
    }
    
    void test1()
    {
        string s1, s2;
        while(cin >> s1 >> s2)
        {
            cout << add(s1, s2) << endl;
        }
    }
    
    int main()
    {
        test1();
        return 0;
    }

除了通过题目给的测试用例，我还用到了以下的测试用例，  
测试用例：

输入：  1 2     输出： 3
    输入：  12 23   输出： 35
    输入：  1 -2    输出： -1
    输入：  12 -11  输出： 1
    输入：  2 -1    输出： 1
    输入：  23 -21  输出： 2
    输入：  -2 -3   输出： -5
    输入：  -12 -12 输出： -24