长整数乘法

给两个字符串整数，返回其乘积（直接类型转换会overflow）

string multiply(string str1, string str2)
{
	if (str1.empty() || str2.empty())
		return "";

	vector<int> vec1(str1.length(), 0);
	vector<int> vec2(str2.length(), 0);
	
	//将两个长整数翻转保存在数组中
	for (size_t i = 0; i < str1.length(); ++i)
		vec1[str1.length() - 1 - i] = str1[i] - '0';
	for (size_t i = 0; i < str2.length(); ++i)
		vec2[str2.length() - 1 - i] = str2[i] - '0';
		
	//构造一个(n+1) + (m+1）的数组用来保存其相乘结果。
	int n = vec1.size() + 1 + vec2.size() + 1;
	vector<int> res(n, 0);
	
	//将两个长整数单个位进行相乘并加上对应位置数然后存储
	for (size_t i = 0; i < vec1.size(); ++i) {
		for (size_t j = 0; j < vec2.size(); ++j) {
			res[i + j] = res[i + j] + vec1[i] * vec2[j];
		}
	}
	
	//遍历整个res数组进行进位操作。
	int carry = 0; //进位
	for (size_t i = 0; i < n; ++i)
	{
		int temp = res[i] + carry;
		res[i] = temp % 10;
		carry = temp / 10;
	}

	//去掉多余的0然后转为字符串存储
	string ret;
	while (n-- > 0) {
		if (res[n] != 0)
			break;
	}

	while (n >= 0) {
		char ch = res[n--] + '0';
		ret.push_back(ch);
	}

	if (ret.empty())
		ret = "0";

	return ret;
}
————————————————
版权声明：本文为CSDN博主「Wkingbai」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_36291615/article/details/126732285