[算法系列之八]大数问题（高精度运算）

/*********************************
*   日期：2015-01-28
*   作者：SJF0115
*   题目: 大数加法(高精度加法)
*   博客：
**********************************/
#include <iostream>
using namespace std;

string AddString(string num1,string num2){
    int len1 = num1.length();
    int len2 = num2.length();
    // 容错处理
    if(len1 <= 0){
        return num2;
    }//if
    if(len2 <= 0){
        return num1;
    }
    string result;
    int i = len1-1,j = len2-1;
    int a,b,sum,carry = 0;
    // 倒序相加
    while(i >= 0 || j >= 0 || carry > 0){
        a = i >= 0 ? num1[i] - '0' : 0;
        b = j >= 0 ? num2[j] - '0' : 0;
        // 按位相加并加上进位
        sum = a + b + carry;
        // 进位
        carry = sum / 10;
        result.insert(result.begin(),sum % 10 + '0');
        --i;
        --j;
    }//while
    return result;
}


int main(){
    string num1("72");
    string num2("874");
    string result = AddString(num1,num2);
    // 输出
    cout<<result<<endl;
    return 0;
}

/*********************************
*   日期：2015-01-28
*   作者：SJF0115
*   题目: 大数加法(高精度加法)
*   博客：
**********************************/
#include <iostream>
using namespace std;

string AddString(string num1,string num2){
    int len1 = num1.length();
    int len2 = num2.length();
    int max = len1 > len2 ? (len1 + 2) : (len2 + 2);
    char* result = new char[max];
    int index = 0;
    int i = len1 - 1,j = len2 - 1;
    int numA,numB,carry = 0,sum = 0;
    //加法
    while(i >= 0 || j >= 0 || carry > 0){
        numA = i >= 0 ? (num1[i] - '0') : 0;
        numB = j >= 0 ? (num2[j] - '0') : 0;
        sum = numA + numB + carry;
        carry = sum / 10;
        result[index++] = sum % 10 + '0';
        --i;
        --j;
    }//while
    result[index] = '\0';
    //反转
    for(i = 0,j = index - 1;i < j;++i,--j){
        char temp = result[i];
        result[i] = result[j];
        result[j] = temp;
    }//for
    return string(result);
}


int main(){
    string num1("872");
    string num2("874");
    string result = AddString(num1,num2);
    // 输出
    cout<<result<<endl;
    return 0;
}

string MinusString(string num1, string num2) {
    int len1 = num1.length();
    int len2 = num2.length();
    // 相等
    if(num1 == num2){
        return "0";
    }//if
    // 正负
    bool positive = true;
    if(len1 < len2 || (len1 == len2 && num1 < num2)){
        positive = false;
        // 交换使之num1 > num2
        string tmp = num1;
        num1 = num2;
        num2 = tmp;
        int temp = len1;
        len1 = len2;
        len2 = temp;
    }//if
    string result;
    int i = len1 - 1,j = len2 - 1;
    int a,b,sum,carray = 0;
    // 从低位到高位对位做减法
    while(i >= 0 || j >= 0){
        a = i >= 0 ? num1[i] - '0' : 0;
        b = j >= 0 ? num2[j] - '0' : 0;
        sum = a - b + carray;
        carray = 0;
        // 不够减
        if(sum < 0){
            sum += 10;
            carray = -1;
        }//if
        result.insert(result.begin(),sum + '0');
        --i;
        --j;
    }//while
    // 删除前导0
    string::iterator it = result.begin();
    while(it != result.end() && *it == '0'){
        ++it;
    }//while
    result.erase(result.begin(),it);
    return positive ? result : "-"+result;
}

/*********************************
*   日期：2015-01-28
*   作者：SJF0115
*   题目: 高精度乘法(大数乘法)
*   博客：
**********************************/
#include <iostream>
#include <cstring>
using namespace std;

string MultiplyString(string num1, string num2) {
    int len1 = num1.length();
    int len2 = num2.length();
    // 容错处理
    if(len1 <= 0 || len2 <= 0){
        return "";
    }//if
    int sum = 0;
    int len3 = len1 + len2;
    char result[len3];
    memset(result,'0',sizeof(result[0])*(len3+1));
    for(int i = len1 - 1,m = 0;i >= 0;--i,++m){
        for(int j = len2 - 1,n = 0;j >= 0;--j,++n){
            sum = (num1[i] - '0') * (num2[j] - '0') + result[m+n] - '0';
            result[m+n] = sum % 10 + '0';
            // 进位
            result[m+n+1] += sum / 10;
        }//for
    }//for
    //去掉前导0 确定乘积的位数
    while(result[len3] == '0' && len3 > 0){
        --len3;
    }//while
    //注意：加'\0'
    result[len3+1] = '\0';
    //翻转
    int temp;
    for(int i = 0,j = len3;i < j;++i,--j){
        temp = result[i];
        result[i] = result[j];
        result[j] = temp;
    }//for
    return string(result);
}

int main(){
    string num1("2");
    string num2("123");
    string result = MultiplyString(num1,num2);
    // 输出
    cout<<result<<endl;
    return 0;
}<span style="color:#ff0000;">
</span>