C++高精度乘法

我信你个鬼！ / 2024-09-05 / 原文

#include <iostream>
#include <string>
#include <cstring>

using namespace std;
 
int main()
{
    string str1, str2;
    cin >> str1 >> str2;
 	
 	// 确定字符串长度
 	int len1 = str1.length();
 	int len2 = str2.length();
 	
 	// 确认积数组的长度
 	// 积的长度上限推断：999*99的大小不会超过999*100(999补两个0即加两位),也即len3<=len1+len2
 	int len3 = len1 + len2;
 	
 	// 创建存储数据的int数组
 	// num1:乘数1数组，num2:乘数2数组，num3:积数组
 	int num1[len1], num2[len2], num3[len3];
 	
 	// 数组数据全部置为0
 	memset(num1, 0, sizeof(num1));
 	memset(num2, 0, sizeof(num2));
 	memset(num3, 0, sizeof(num3));
 	
 	// 乘数数据的逆序填充
 	for(int i=0;i<len1;i++) num1[i] = str1[len1-i-1] - 48;
 	for(int i=0;i<len2;i++) num2[i] = str2[len2-i-1] - 48;
 	
 	// 计算乘法，分别遍历两个乘数，边乘边将结果存入到积相对应的位置处理
	// 进行遍历相乘时，根据竖式推导可知num1[i]*num2[j]的值会被放到num3的i+j位置上
 	// x为进位值，存入到num3中后需取余并设定进位
 	int x = 0;
 	for(int i=0;i<len1;i++)
 	{
 		for(int j=0;j<len2;j++)
 		{
 			// 计算乘数，注意用+=，因为i+j位置在两层循环中有可能被重复赋值
 			num3[i+j] += num1[i] * num2[j] + x;
 			// 向上进位
 			num3[i+j+1] += num3[i+j] / 10;
 			// 取余
 			num3[i+j] %= 10;
		}
	}
	
	// 判断最后num3最后一位是否为0，为0则len3--以去除多余的高位
	if(num3[len3-1]==0) len3--;
	
	// 逆序打印结果
	for(int i=len3-1;i>=0;i) cout << num3[i];
	cout << endl;
 	
    return 0;
}