大数加减乘除？

大数加减代码：（贴代码）

//Bignumber.h

#ifndef __BIGNUMBER_H
#define __BIGNUMBER_h

#include <string>
using namespace std;

string bigadd(string s1,string s2);
string bigsub(string s1,string s2);
bool compareS1S2(string s1,string s2);



#endif

//Bignumber.cc

#include "Bignumber.h"

bool compareS1S2(string s1,string s2) //比较s1 s2绝对值大小；
{
    int len1 = s1.size();
    int len2 = s2.size();

    int com1=0,com2 = 0;
    if (s1[0] == '-')
        com1 = 1;
    if (s2[0] == '-')
        com2 = 1;
    if ((len1-com1+1) != (len2-com2+1))
    {
        return (len1 - com1 + 1) > (len2 - com2 + 1);
    }
    else
    {
        while (com1<len1 && com2<len2 && s1[com1] == s2[com2])
        {
            ++com1;
            ++com2;
        }
        if (com1 < len1)
        {
            return s1[com1]>s2[com2];
        }
        else
        {
            return true;
        }
    }
}

string bigadd(string s1,string s2)
{
    //判断输入合法性,尚未检查字符串内容
    int len1 = s1.size();
    int len2 = s2.size();
    if (len1 == 0)
        return s2;
    if (len2 == 0)
        return s1;

    bool isNagative = false;
    string res = "-";
    //检测起首
    if (s1[0] == '-')
    {
        if (s2[0] == '-')
        {
            isNagative = true;
            return res + bigadd(s1.substr(1),s2.substr(1));
        }
        else
        {
            return bigsub(s2,s1.substr(1));
        }
    }
    else
    {
        if (s2[0] == '-')
        {
            return bigsub(s1,s2.substr(1));
        }
        else
        {
            if (len1 < len2) //使得len1>=len2
            {
                return bigadd(s2,s1);
            }
            int jinwei = 0;

            int add1 = len1-1,add2 = len2-1;
            string res(len1,0);
            while (add2 >= 0)
            {
                int sum = s1[add1]-'0' + s2[add2]-'0' + jinwei;
                res[add1] = sum % 10+'0';
                jinwei = sum >= 10 ? 1 : 0;
                add2--;
                add1--;
            }

            while (add1 >= 0)
            {
                int sum = s1[add1]-'0'+ jinwei;
                res[add1] = sum % 10+'0';
                jinwei = sum >= 10 ? 1 : 0;
                add1--;
            }
            if (jinwei == 1)
            {
                string jia("1");
                return jia + res;
            }
            else
            {
                return res;
            }
        }
    }

}

string bigsub(string s1,尚未检查字符串内容

    int len1 = s1.size();
    int len2 = s2.size();
    string fu("-");
    if (len1 == 0)
    {

        return fu + s2;
    }
    if (len2 == 0)
        return s1;

    //保障s1>=s2
    if (!compareS1S2(s1,s2))
    {
        string resopsi = bigsub(s2,s1);
        if (resopsi[0] == '-')
            return resopsi.substr(1);
        else
            return fu + resopsi;
    }

    if (s1[0] == '-')
    {
        if (s2[0] == '-')
        {
            string tmp1 = bigsub(s1.substr(1),s2.substr(1));
            return fu + tmp1;
        }
        else
        {
            string tmp2 = bigadd(s1.substr(1),s2);
            return fu + tmp2;
        }
    }
    else
    {
        if (s2[0] == '-')
        {
            string tmp3 = bigadd(s1,s2.substr(1));
            return tmp3;
        }
        else
        {
            string res(len1,0);
            int sub1 = len1 - 1,sub2 = len2 - 1;
            int que = 0;
            while (sub2 >= 0)
            {
                int sum = s1[sub1] - s2[sub2] - que;
                res[sub1] =(sum+10) % 10 + '0';
                que = (sum >= 0 ? 0 : 1);
                --sub1;
                --sub2;
            }

            while (sub1 >= 0)
            {
                int sum = s1[sub1]-'0'  - que;
                res[sub1] = (sum+10) % 10 + '0';
                que = (sum >= 0 ? 0 : 1);
                --sub1;
            }
            //出去开头的0
            int index = 0;
            while (res[index] == '0')index++;
            if (index == 0)
                return res;
            else
                return res.substr(index);

        }
    }


}

写代码中的心得：
1、字符串中的’0’~’9’并非int类型的0~9，实际上他们的char值并非0~9，我们需要‘9’-‘0’=9；（记得“ -‘0’”）
2、求余运算
%是求余运算符，也叫模除运算符，用于求余数。
%要求两个操作数均为整数（或可以隐式转换成整数的类型）。
标准规定：
**如果%左边的操作数为负数时，则模除的结果为负数或者0，
如果%左边的操作数为正数时，则模除的结构为正数或者0。**

一开始我以为-1%10=9，后来调试才发现为-1。。。其实还是自己太菜不熟悉。。

大数乘法

乘积是逐位相乘，也就是aibj，结果加入到积C的第i+j位，最后处理进位即可，例如：A =17 = 1*10 + 7 = （7,1）最后是十进制的幂表示法，幂次是从低位到高位，以下同。B=25 = 2*10 + 5 = (5,2);C = A * B = (7 * 5,1 * 5 + 2 * 7,1 * 2) = (35,19,2) = (5,22,2. 4)=425。
代码：
//仍然在Bignumber.h

#ifndef __BIGNUMBER_H
#define __BIGNUMBER_h

#include <string>
#include <vector>
using namespace std;


bool compareS1S2(string s1,string s2);

string bigmul(string s1,string s2);

#endif

//仍然在Bignumber.cc

bool compareS1S2(string s1,string s2) //比较s1 s2绝对值大小；
{
    int len1 = s1.size();
    int len2 = s2.size();

    int com1=0,com2 = 0;
    if (s1[0] == '-')
        com1 = 1;
    if (s2[0] == '-')
        com2 = 1;
    if ((len1-com1+1) != (len2-com2+1))
    {
        return (len1 - com1 + 1) > (len2 - com2 + 1);
    }
    else
    {
        while (com1<len1 && com2<len2 && s1[com1] == s2[com2])
        {
            ++com1;
            ++com2;
        }
        if (com1 < len1)
        {
            return s1[com1]>s2[com2];
        }
        else
        {
            return true;
        }
    }
}

void invertToVector(string s,vector<int>& vec)
{
    int siz = s.size(); 
    if (siz == 0)
        return;
    vec.resize(siz,0);
    int i = 0,k=siz-1;
    while (i < siz)
    {
        vec[i] = s[k]-'0';
        --k;
        ++i;
    }
}
string invertToString(vector<int>& vec)
{
    int siz = vec.size();
    if (siz == 0)
    {
        string s("");
        return s;
    }

    string s(siz,k = siz - 1;
    while (i < siz)
    {
        s[k] = vec[i]+'0';
        --k;
        ++i;
    }
    //去0
    int index = 0;
    while (s[index] == '0')++index;
    if (index == 0)
        return s;
    else
        return s.substr(index);

}
string bigmul(string s1,string s2)
{
    vector<int> v1,v2;
    invertToVector(s1,v1);
    invertToVector(s2,v2);

    int len1 = s1.size(),len2 = s2.size();
    vector<int> res(len1 + len2,0);
    for (int k = 0; k < len1 + len2; ++k)
    {
        res[k] = 0;
        for (int i = 0; i < len1 && (k - i >= 0); ++i)
        {
            if (k - i < len2)
            {
                res[k] += v1[i] * v2[k - i];
            }
        }
    }
    int jinwei = 0;
    for (int i = 0; i < len1 + len2; ++i)
    {
        jinwei = res[i] + jinwei;
        res[i] = jinwei % 10;
        jinwei = jinwei / 10;
    }
    string ress = invertToString(res);
    return ress;

}

大数除法

大数除法，应该算是四则运算里面最难的一种了。不同于一般的模拟，除法操作步数模仿手工除法，而是利用减法操作实现的。
其基本思想是反复做除法，看从被除数里面最多能减去多少个除数，商就是多少。
逐个减显然太慢，要判断一次最多能减少多少个整的10的n次方。
以7546除23为例。
先减去23的100倍，就是2300，可以减3次，余下646。 此时商就是300；
然后646减去23的10倍，就是230，可以减2次，余下186。此时商就是320；
然后186减去23，可以减8次，此时商就是328.

根据这个思想，不难写出下面的代码。
//Bignumber.h

#ifndef __BIGNUMBER_H
#define __BIGNUMBER_h

#include <string>
#include <vector>
using namespace std;

string bigadd(string s1,string s2);
string bigdiv(string s1,string s2); //s1/s2
#endif

//Bignumber.cc

//会用到 bigsub 函数

string bigdiv(string s1,string s2)
{
    int len1 = s1.size();
    int len2 = s2.size();
    if (len1 < len2)
    {
        string res("0");
        return res;
    }
    string res(len1 - len2 + 1,0);

    string subed(len1 - len2,0+'0');
    int index = 0;
    int ind = 0;
    string tmp(s1);
    while (ind<len1-len2+1)
    {
        string s2s2;
        if (index < len1 - len2)
        {
            s2s2 = s2 + subed.substr(index);
        }
        else
        {
            s2s2 = s2;
        }
        int val = 0;
        while (compareS1S2(tmp,s2s2))
        {
            tmp = bigsub(tmp,s2s2);
            ++val;
        }
        res[ind] = val + '0';
        ++index;
        //subed = subed.substr(1);
        ++ind;
    }
    //去0
    int k = 0;
    while (res[k] == '0') ++k;
    if (k == 0)
        return res;
    else
        return res.substr(k);
}