String大数加减乘除（非负整数）

leetcode上一题使用String完成大数乘法，鉴于之前华为机试也考到过大数减法，这里做一个大数运算的专题。

说到底，大数运算考察的还是对运算的理解，我们完全可以通过模拟手算来进行。

注意string与int间的转换，string[] - '0' 变成int，int + '0' 变成 string[]。

由于我们希望能用下标与数字的位数对应起来，所以需要用 reverse(s.begin(),s.end()) 对String翻转一下存储，最后翻转回来，并将得到的结果的无用高位 '0' 删除掉，如果结果为 '0'，还要特殊处理。

大数加法：

可以将两个字符串按位相加，注意进位，时间复杂度为O(N)。对于进位，我们遵循先按位相加，然后从低到高对于大于９的位进行进位处理。进位立即加到高一位，本位对10取余后再处理高一位，依次类推，后面可以看到我们对乘法虽然不是一次性加完再进位，而是从低到高一位一位加完进位，但思想是一样的。（需要小心的就是：１、注意string的范围，不能让下标越界；２、完整处理进位或借位）

string add(string num1,string num2) {
        string num(1000,'0');
        if(num1.empty() || num2.empty())
        {    
			num = "Data error!";
			return num;
        }    
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        
        int i,len;
        for(i = 0; i < num1.size(); ++i)
        	num[i] = num1[i];

	for(i = 0; i < num2.size(); ++i)
		num[i] = num[i] - '0' + num2[i];
		
	len = max(num1.size(),num2.size());         //len取最大确保处理完全部进位
	for(i = 0; i < len; ++i)
	{
		num[i + 1] = num[i + 1] + (num[i] - '0') / 10;
		num[i] = (num[i] - '0') % 10 + '0';
	}
        
        reverse(num.begin(),num.end());
	if(num.find_first_not_of('0') == string::npos)
		num = '0';
        else 
		num.erase(num.begin(),num.begin() + num.find_first_not_of('0'));　　　//删除高位无用'0'

        
	return num;
}

大数减法：

判断两个数的大小后用大数减小数，最后添加符号，注意借位，时间复杂度O(N)。

string sub(string num1,'0');
        if(num1.empty() || num2.empty())
        {    
			num = "Data error!";
			return num;
        }    
        int i,flag = 0;

	if(num1.find_first_not_of('0') == string::npos)
		num1 = '0';
        else 
		num1.erase(num1.begin(),num1.begin() + num1.find_first_not_of('0'));
	if(num2.find_first_not_of('0') == string::npos)
		num2 = '0';
        else 
		num2.erase(num2.begin(),num2.begin() + num2.find_first_not_of('0'));
		
	if(num2.size() > num1.size())　　　　　　　　　　　　　　　　　　//删除掉高位'0'后比较大小
		flag = 1;
	else if(num2.size() == num1.size())
	{
		cout << "I'm here." << endl;
		if(num1 == num2)
		{	
			num = '0';
			return num;
		}
		flag = num2 > num1;
		cout << flag << endl;
	}
        
	reverse(num1.begin(),num2.end());
		
	if(flag == 0)
	{
		for(i = 0; i < num1.size(); ++i)
			num[i] = num1[i];
		for(i = 0; i < num2.size(); ++i)
		{	
			num[i] = num[i] - num2[i] + '0';
			if(num[i] < '0')
			{
				num[i] = num[i] + 10;
				num[i + 1] = num[i + 1] - 1;
			}
		}
		while(num[i] < '0')　　　　　　　　　　　　　//处理余下的借位，因为以上循环中i只到num2.size()
		{
			num[i] = num[i] + 10;
			num[i + 1] = num[i + 1] - 1;
		}
	}
	else
	{
		for(i = 0; i < num2.size(); ++i)
			num[i] = num2[i];
		for(i = 0; i < num1.size(); ++i)
		{	
			num[i] = num[i] - num1[i] + '0';
			if(num[i] < '0')
			{
				num[i] = num[i] + 10;
				num[i + 1] = num[i + 1] - 1;
			}
		}
		while(num[i] < '0')
		{
			num[i] = num[i] + 10;
			num[i + 1] = num[i + 1] - 1;
		}
	}

	reverse(num.begin(),num.begin() + num.find_first_not_of('0'));
		
	if(flag == 1)
		num.insert(0,"-");
	return num;
}

大数乘法：

第一个字符串的第i位乘以第二个字符串的第j位一定是结果的第i+j位，如果i+j已经有值，直接加上去就OK，记得处理进位。这样的算法的复杂度是O(N^2)，利用FFT可以将算法优化到O(NlogN)，感兴趣的读者可自行google。

处理进位时只需处理当前进位，将进位直接加到前一位，注意此时的被进位位可能大于９，也即此时该位存储的字符串不是'0'~'9'，没关系，这些都只是中间过程，在下一次的运算中该位减 ‘０’ 就会得到 int 值，然后继续运算，进位也会被处理。注意 max(i) + max(j) + 1位 不可能产生进位！故最后不需要再处理额外的进位。

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!