C++中两个大整数相乘

清疚 2022-07-24 07:23 229阅读 0赞

输入为用字符串表示的两个大的整数，输出为用字符串表示的相乘结果。

#include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    #define MAX_SIZE 1024
    
    template<typename T>
    void PrintVector(const vector<T>& vec)
    {
    	for (T x : vec) {
    		cout << x << " ";
    	}
    	cout << endl;
    }
    
    void AddToVectorPos(vector<int>& ivec, size_t pos, int num)
    {
    	ivec[pos] += num;
    
    	int carryBit = 0;
    	while (ivec[pos] > 9) {
    		carryBit = ivec[pos] / 10;
    		ivec[pos] = ivec[pos] % 10;
    
    		++pos;
    		ivec[pos] += carryBit;
    	}
    }
    
    void VectorToString(const vector<int>& vec, string& dest)
    {
    	dest.clear();
    	for (auto ix : vec) {
    		dest.push_back(static_cast<char>(ix + '0'));
    	}
    
    	while (dest.at(0) == '0') {
    		dest.erase(dest.begin());
    	}
    }
    
    void BigNumber(const char* a1, const char* b1, char* result)
    {
    	string sa1(a1);
    	string sb1(b1);
    	string::size_type totalLength = sa1.size() + sb1.size();
    	vector<int> vecA1;
    	vector<int> vecB1;
    	vector<vector<int>> vecMid;
    	vector<int> vecResult(totalLength,0);
    
    	for (auto c : sa1) {
    		vecA1.insert(vecA1.begin(), static_cast<int>(c - '0'));
    	}
    	for (auto c : sb1) {
    		vecB1.insert(vecB1.begin(), static_cast<int>(c - '0'));
    	}
    
    	int currentBit = 0;
    	int carryBit = 0;
    	vector<int> vecTmp;
    	for (auto ia : vecA1) {
    		vecTmp.clear();
    		carryBit = 0;
    		for (auto ib : vecB1) {
    			currentBit = ia * ib % 10 + carryBit;
    			carryBit = ia * ib / 10;
    			vecTmp.push_back(currentBit);
    		}
    		if (carryBit != 0) {
    			vecTmp.push_back(carryBit);
    		}
    		vecMid.push_back(vecTmp);
    	}
    
    	for (size_t i = 0; i < vecMid.size(); ++i) {
    		for (size_t j = 0; j < i; ++j) {
    			vecMid[i].insert(vecMid[i].begin(), 0);
    		}
    		while (vecMid[i].size() < totalLength) {
    			vecMid[i].push_back(0);
    		}
    	}
    
    	int currentPos = 0;
    	int currentTotal = 0;
    	for (size_t i = 0; i < totalLength; ++i) {
    		for (auto iv : vecMid) {
    			currentTotal += iv[i];
    		}
    
    		currentPos = i;
    		AddToVectorPos(vecResult, currentPos, currentTotal);
    		currentTotal = 0;
    	}
    
    	string stmp;
    	reverse(vecResult.begin(), vecResult.end());
    	VectorToString(vecResult, stmp);
    	strcpy_s(result, MAX_SIZE, stmp.c_str());
    }
    
    int main()
    {
    	char* a1 = "1234567890";
    	char* b1 = "4561234567890";
    	char result[MAX_SIZE];
    	memset(result, '\0', MAX_SIZE);
    	BigNumber(a1, b1, result);
    
    	cout << a1 << " * " << b1 << " = " << result << endl;
    
    #ifdef _MSC_VER
    	system("pause");
    #endif
    	return 0;
    }

![Image 1][]

![Center][]

[Image 1]: 
[Center]: /images/20220722/101b5761d5de46d9b1b063af61edaff5.png