大数的加减乘除运算(C++)

自认为算法比较渣，最近经常遇到一些大数问题，虽然原理大家都懂。就是把大数转换成字符串或者数组，一位一位的进行计算。

但是实际写起代码来，还是Bug满天飞。

还是自己用代码实现一遍比较靠谱，顺便加深一下理解。

代码全扔下面了。注释应该还比较详细。

/*
这里专门就算法中的大数问题进行一个统一归纳
*/

#include<iostream>
#include<string>
#include<vector>
using namespace std;

//结果支持的最大位数
//这个可以依据具体需求调整
const static int M = 2000;


int numA[M];
int numB[M];


//使用string重置numA
void resetNumA(string numAStr)
{
	memset(numA,M*sizeof(int));

	//将字符串的每一位都转换成数字传入数组
	for (int i = 0; i < numAStr.length(); i++)
	{
		numA[i] = numAStr[numAStr.length()-i-1] - '0';
	}
}

//使用string重置numB
void resetNumB(string numBStr)
{
	memset(numB,M*sizeof(int));

	//将字符串的每一位都转换成数字传入数组
	for (int i = 0; i < numBStr.length(); i++)
	{
		numB[i] = numBStr[numBStr.length()-i-1] - '0';
	}
}


//将数组转换为字符串，用于输出
string getNumString(int* num)
{
	string numString;
	bool isBegin = false;
	for (int i = M-1; i >= 0 ; i--)
	{
		if(num[i] != 0)
		{
			isBegin = true;
		}

		if (isBegin)
		{
			numString += num[i] +'0';
		}
	}
	return numString;
}

//判断两个数字哪个大
int compare(string numAStr,string numBStr)
{
	if (numAStr.length() > numBStr.length())
	{
		return 1;
	}
	else if (numAStr.length() < numBStr.length())
	{
		return -1;
	}
	else
	{
		for (int i = 0; i < numAStr.length(); i++)
		{
			if (numAStr[i]>numBStr[i])
			{
				return 1;
			}
			
			if (numAStr[i]<numBStr[i])
			{
				return -1;
			}
		}
		return 0;
	}
}

//加法
string plus(string numAStr,string numBStr)
{
	resetNumA(numAStr);
	resetNumB(numBStr);

	for (int i = 0; i < M; i++)
	{
		//结果保存在numA中
		numA[i] += numB[i];

		//数字大于9则进位
		if(numA[i]>9)
		{
			numA[i] -= 10;
			numA[i+1]++;
		}
	}

	return getNumString(numA);
}

//减法
string minus(string numAStr,string numBStr)
{
	bool isNegative = false;

	//如果numA比numB小
	//则结果为负数
	//调换位置进行计算
	if (compare(numAStr,numBStr)==-1)
	{
		isNegative = true;
		string temp = numAStr;
		numAStr = numBStr;
		numBStr = temp;
	}
	else if (compare(numAStr,numBStr)==0)
	{
		return "0";
	}

	resetNumA(numAStr);
	resetNumB(numBStr);



	for (int i = 0; i < M; i++)
	{
		//减数小于被减数就借位
		if (numA[i]<numB[i])
		{
			numA[i] = numA[i]+10-numB[i]; 
			numA[i+1]--;
		}
		else
		{
			numA[i] -= numB[i];
		}
	}
	if (isNegative)
	{
		return "-"+  getNumString(numA);
	}
	else
	{
		return getNumString(numA);
	}
	
}

//乘法

string mul(string numAStr,string numBStr)
{
	resetNumA(numAStr);
	resetNumB(numBStr);

	vector<string> nums;
	for (int i = 0; i < numBStr.length(); i++)
	{
		//初始化一个临时数据来保存被乘数与乘数的某一位相乘的结果
		int temp[M];
		memset(temp,M*sizeof(int));


		for (int j = i; j < numAStr.length()+i; j++)
		{
			temp[j] += numA[j-i]*numB[i]%10;

			temp[j+1] = numA[j-i]*numB[i]/10;

			//如果大于9，那么就做进位处理
			if (temp[j]>9)
			{
				temp[j]-=10;
				temp[j+1]++;
			}
		}
		nums.push_back(getNumString(temp));
	}

	//每位相乘的结果再用加法加起来
	string result = nums[0];
	for (int i = 1; i < nums.size(); i++)
	{
		result = plus(result,nums[i]);
	}

	return result;
}



//除,结果精确到个位
string div(string numAStr,string numBStr)
{
	resetNumA(numAStr);
	resetNumB(numBStr);

	string result;
	string left;

	if (compare(numAStr,numBStr)==-1)
	{
		return "0";
	}

	//标记第一个不为0的位数的出现
	bool flag = false;
	for (int i = 0; i < numAStr.length(); i++)
	{
		left +=numAStr[i];

		//余数比除数大
		if (compare(left,numBStr)==1)
		{
			flag = true;

			int count = 1;
			string temp = numBStr;

			while (true)
			{
				//每循环一次加上一个余数
				temp = plus(temp,numBStr);

				//余数仍然大于除数，继续累加
				if (compare(left,temp)==1)
				{
					count++;
				}
				//余数小于除数
				//可以计算结果
				else if (compare(left,temp)==-1)
				{
					result += count + '0';
					left = minus(left,minus(temp,numBStr));
					break;
				}
				//此时余数刚好是除数的倍数
				else if (compare(left,temp) == 0)
				{
					count ++;
					result += count + '0';
					left = "";
					break;
				}
			}
		}
		//刚好除尽
		else if(compare(left,numBStr)==0)
		{
			flag = true;
			result +="1";
			left = "";
		}
		//余数比除数小，跳到下一位
		else if(flag)
		{
			result +="0";
		}


	}

	return result;
}

void printTitle()
{
	cout << endl;
	cout << "输入1：加法" << endl;
	cout << "输入2：减法" << endl;
	cout << "输入3：乘法" << endl;
	cout << "输入4：除法" << endl;
	cout << "选择 : ";
}

int main()
{

	string numAStr,numBStr;
	string operation;
	string result;

	printTitle();

	while (cin >> operation)
	{
		cout << "输入两个数字： ";
		cin >> numAStr >> numBStr;

		if(operation == "1")
		{
			result = plus(numAStr,numBStr);
		}
		else if(operation == "2")
		{
			result = minus(numAStr,numBStr);
		}
		else if(operation == "3")
		{
			result = mul(numAStr,numBStr);
		}
		else 
		{
			result = div(numAStr,numBStr);
		}

		cout << "结果为：" << result << endl;

		printTitle();
	}
}