大数相加和大数相乘

1、大数相加

int或者long类型的数据往往满足不了数据容量的要求，这时需要用到数组或者字符串进行操作。考虑到数据的位数并不是一个确定的值，运用string来处理可以简化思维。在进行运算之前，需要明确下面几点要求：

1.将两组数据中位数大的放在前面，方便后面处理；

2.字符转数字，减去‘0’；数字转字符加上‘0’；

3.进位考虑

4.最高位时进位判断

string BigPlus(string num1,string num2){
    //默认使得num1位数大于num2，方便后续运算。
    if(num1.size()<num2.size()){
        string temp=num2;
        num2=num1;
        num1=temp;
    }
    int lenth1=num1.size(),lenth2=num2.size(),flag=0,a,b,sum;//初始化位数、进位标志、定义转换数字a、b和sum
    while(lenth1>0){//lenth1总是大于等于lenth2
        a=num1[lenth1-1]-'0';//转换为数字
        if(lenth2>0){
            b=num2[lenth2-1]-'0';//转换为数字
        }
        else{
            b=0;//num2位数加完了
        }
        sum=a+b+flag;//当前位加进位
        if(sum>=10){//进位判断
            flag=1;//进位标记
            num1[lenth1-1]='0'+sum%10;//取个位
        }
        else{
            flag=0;//进位标记清除
            num1[lenth1-1]='0'+sum;
        }
        //每次向前进位
        lenth1--;
        lenth2--;
    }
    if(flag){
        num1="1"+num1;//当最高位进位，在前面加1
    }
    return num1;//返回得到的和
}

2、大数相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1: 输入: num1 = “2”, num2 = “3”. 输出: “6”

class Solution {
public:
	string multiply(string num1, string num2) {
		if (num1 == "0" || num2 == "0") return "0";
		int n1 = num1.length() - 1;
		int n2 = num2.length() - 1;
		vector<int> mul(n1 + n2 + 2);
//编译器默认初始化为0  n位数和m位数相乘最多为m+n位数。
//乘数 num1 位数为 MM，被乘数 num2 位数为 NN， num1 x num2 结果 res 最大总位数为 M+N
//num1[i] x num2[j] 的结果为 tmp(位数为两位，"0x","xy"的形式)，其第一位位于 res[i+j]，第二位位于 res[i+j+1]。
//11*12 =132  1和2相乘的结果为2的下标加1的下标，假设1的下标代表2乘了几个10（0下标开始的话）
		for (int i = n1; i >= 0; i--)
			for (int j = n2; j >= 0; j--) { //11 12
				int bitmul = (num1[i] - '0')*(num2[j] - '0');//两个位上的数的乘积
				bitmul += mul[i + j + 1];//先加低位，判断是否有新的进位

				mul[i + j] += bitmul / 10;//高位
				mul[i + j + 1] = bitmul % 10;//低位
			}

		//去掉前导0
		int i = 0;
		while (i < n1 + n2 + 1 && mul[i] == 0)
			i++;
		int index = i;
		string multi=string(n1+n2+2-i,'0');
		for (; i < n1 + n2 + 2; i++)
			multi[i-index]=(mul[i]+'0');//string类型的append函数
		return multi;
	}
};