大整数的加减乘除

背景

415. 字符串相加 - 力扣（LeetCode） (leetcode-cn.com)

43. 字符串相乘 - 力扣（LeetCode） (leetcode-cn.com)

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

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

示例 1:

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

输入: num1 = “123”, num2 = “456” 输出: “56088”

说明：
1. num1 和 num2 的长度小于110。
2. num1 和 num2 只包含数字 0-9。
3. num1 和 num2 均不以零开头，除非是数字 0 本身。
4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

大整数的字符串加法

模拟思路与算法

本题我们只需要对两个大整数模拟「竖式加法」的过程。竖式加法就是我们平常学习生活中常用的对两个整数相加的方法，回想一下我们在纸上对两个整数相加的操作，是不是将相同数位对齐，从低到高逐位相加，如果当前位和超过 10，则向高位进一位？因此我们只要将这个过程用代码写出来即可。

具体实现也不复杂，我们定义两个指针 i 和 j 分别指向 num1和 num2的末尾，即最低位，同时定义一个变量cur 维护当前是否有进位，然后从末尾到开头逐位相加即可。

string BigIntCalculate::add(string num1, string num2)
{
    string str;
    int cur = 0, i = num1.size() - 1, j = num2.size() - 1;
    while (i >= 0 || j >= 0 || cur != 0) {
        if (i >= 0) {
            cur += num1[i] - '0';
            i--;
        }
        if (j >= 0) {
            cur += num2[j] - '0';
            j--;
        }
        str += to_string(cur % 10);
        cur /= 10;
    }
    reverse(str.begin(), str.end());
    return str;
}

大整数的字符串减法

减法同加法一样，可以用模拟「竖式减法」的过程。只不过要先通过比较两个数的位数和大小确定正负，同时定义一个变量cur 维护当前是否有借位。

string BigIntCalculate::subtract(string num1, string num2)
{
	if (num1.size() < num2.size())
	{
		return "-" + subtract(num2, num1);
	}
	if (num1.size() == num2.size())
	{
		for (int i = 0; i < num1.size(); i++) {
			int a = num1[i] + '0';
			int b = num2[i] + '0';
			if (a < b) {
				return "-" + subtract(num2, num1);//添加负号
			}
			else if (a > b) {
				break;
			}
		}
	}
    
	string str;
	int i = num1.size() - 1, j = num2.size() - 1;
	int cur = 0;
	while (i >= 0 )
	{
		if (j >= 0) {
			cur += (num1[i] - '0') - (num2[j] - '0');
		}
		else {
			cur += num1[i] - '0';
		}
		i--;
		j--;

		if (cur < 0)
		{
			str += to_string(cur+10);
			cur = -1;
		}
		else {
			str += to_string(cur);
			cur = 0;
		}
	}
	reverse(str.begin(), str.end());
	for (int i = 0; i < str.size(); i++)
		if (str[i] != '0') return str.substr(i); //多了一步去除前导0
	return "0";
}

大整数的字符串乘法

方法一：模拟乘法的竖式运算。
方法二：大整数乘法的快速算法还可以用（快速傅立叶变换FFT）

快速傅里叶变换（FFT）求解多项式乘法 - 知乎 (zhihu.com)

string BigIntCalculate::multiply(string num1, string num2)
{
    int m = num1.size(), n = num2.size();
    string s(m + n, '0');       //初始化大小m+n
    for (int i = m - 1; i >= 0; --i)     //从后向前
        for (int j = n - 1; j >= 0; --j)
        {
            int cur = (num1[i] - '0') * (num2[j] - '0') + (s[i + j + 1] - '0'); //注意累加之前的结果
            s[i + j + 1] = cur % 10 + '0';  //这里是=字符
            s[i + j] += cur / 10;     //注意这里是+=数字
        }
    for (int i = 0; i < m + n; i++)
        if (s[i] != '0') return s.substr(i); //去除前导0
    return "0";
}

大整数的字符串除法

先实现一个减法，然后通过累次相减确定商。循环做减法，计数，直到被除数小于或等于0。

简单优化方法可以根据位数之差，将除数扩大10^t^倍进行相减，来确定商在t位次的值，能够减少减法运算的次数。

string BigIntCalculate::divide(string num1, string num2)
{
	int m = num1.size(), n = num2.size();

	if (m < n) {
		return "0";
	}
    if (num2 == "0") {
		return "error";
	}
	int t = m - n;//位数之差
	string div_result(t+1, '0');
	string tmp_num2(n + t, '0');
	for (int i = 0; i < n; i++) {//将除数扩大10^t倍
		tmp_num2[i] = num2[i];
	}
	string mod_result = num1;
	for (int i = 0; i < t + 1; i++) {
		int count = 0;
		string sub_result = mod_result;
		while(true){
			string tmp = tmp_num2.substr(0, n + t - i);
			//cout << "i = " << i << " tmp = " << tmp << " sub_result = " << sub_result << endl;
			sub_result = subtract(sub_result, tmp);
			if ( sub_result[0] != '-') {
				count++;
				mod_result = sub_result;
			}
			else  {
				break;
			}
		}
		div_result[i] = '0' + count;
	}
	if (div_result[0] == '0') {
		return div_result.substr(1); //去除前导0
	}
	else {
		return div_result;
	}
}

其它警告信息

[C26451

Microsoft Docs](https://docs.microsoft.com/zh-cn/cpp/code-quality/c26451?f1url=%3FappId%3DDev16IDEF1%26l%3DZH-CN%26k%3Dk(C26451)%26rd%3Dtrue&view=msvc-160)

warning_C26451

~~99+warnings关我什么事，能跑就行。~~

受到C语言以及各种C/C++入门书的熏陶，不少人一想到整型，一律使用 int。可能已经注意到，通篇使用int常常会有大片的此类警告：

警告 C26451 算术溢出: 使用 4 字节值上的运算符 + ，然后将结果转换到 8 字节值。在调用运算符 + 之前将值强制转换为宽类型可避免溢出(io.2)。

这是64位和32位整型宽度不对齐的警告。这些警告也许不碍事，只碍眼。有强迫症的，可能按照警告的提示加一个强制类型转换，没有强迫症的人直接就忽略了。但是没有任何一个警告是无缘无故的。这些警告不仅意味着程序中的潜在的溢出问题，还意味着无意义的强制类型转换浪费的效率。

32 位 VS 64 位

32位平台和64位平台最重要的区别是地址和指令的长度不同。在32位平台上，指针是32位的（即sizeof(void)==4），并且，为了契合32位，stl的容器的大小、索引也都是32位的整型。在64位平台上，指针是64位的（即sizeof(void)==8），并且stl的容器的大小和索引也都是64位的。特别指出，64位已经非常普及了，64位编译是必须考虑的问题。

	有符号	无符号
32位	int	unsigned int
64位	long long; __int64	unsigned long long; unsigned __int64

为了同时兼容32位和64位，还要避免不必要的类型转换，要使用哪种类型？std中已经用宏和typedef为你写好了：

int => ptrdiff_t

usigned int => size_t

ptrdiff_t的意思是“指针之差”，即两个地址运算之差，对应有符号整型；size_t对应无符号整型，他们的宽度是依赖于编译平台的，在32位平台上是32位的，在64位平台是64位的，他们存在于std库中，用宏检查平台，并typedef自对应平台的整型。

std::ptrdiff_t - cppreference.com

size_t - cppreference.com

Zeng Penghui

大整数的加减乘除

大整数的加减乘除

背景

大整数的字符串加法

大整数的字符串减法

大整数的字符串乘法

大整数的字符串除法

其它警告信息

32 位 VS 64 位

留下评论