天天看点
返回

c++string实现的大数加减乘除

class BigInt
{
public:
	BigInt(string str) :strDigit(str){}
	friend ostream& operator<<(ostream &out, const BigInt &src);

	friend BigInt operator+(const BigInt &lhs, const BigInt &rhs);

	friend BigInt operator-(const BigInt &lhs, const BigInt &rhs);

	friend BigInt operator*(const BigInt &lhs, const BigInt &rhs);

	friend BigInt operator/(const BigInt &lhs, const BigInt &rhs);
private:
	string strDigit;   // 使用字符串存储大整数
};

1.大数加法：

思路：

1.先判断两者的长度谁长

2.两个大数先都从后向前遍历 将两者的和处理处理进位问题，将处理完的值加入到string 中

3.处理最后临界进位问题

不足：

没有写负数相加

可直接删除有些大数前多余的零，在进行运算

BigInt operator+(const BigInt &lhs, const BigInt &rhs)
{
	string greater=lhs.strDigit;
	string less=rhs.strDigit;
	string result;
	if(lhs.strDigit.length()<rhs.strDigit.length())
	{
		greater=rhs.strDigit;
		less=lhs.strDigit;
	}
	delete_zero(greater);//删除大数前的0位
	delete_zero(less);
	int Msize=greater.length()-1;
	int Lsize=less.length()-1;

	int i=Msize;
	int j=Lsize;
	bool flag=false;

	for(;j>=0;i--,j--)
	{
		int ret=greater[i]-'0'+less[j]-'0';
		
		if(flag)
		{
			ret+=1;
			flag=false;
		}

		if(ret>=10)
		{
			ret%=10;
			flag=true;
		}

		result.push_back(ret+'0');

	}
	while(i>=0)
	{
		int ret=greater[i]-'0';
		if(flag)
		{
			ret+=1;
			flag=false;
		}
		if(ret>=10)
		{
			ret%=10;
			flag=true;
		}
		result.push_back(ret+'0');
		i--;
	}
	if(flag)
	{
		result.push_back('1');
	}
	reverse(result.begin(),result.end());
	return result;
}

2.大数减法： 

BigInt operator-(const BigInt &lhs, const BigInt &rhs)
{
	string greater=lhs.strDigit;
	string less=rhs.strDigit;
	string result;
	bool Is_minus=false;

	if(lhs.strDigit.length()<rhs.strDigit.length())
	{
		greater=rhs.strDigit;
		less=lhs.strDigit;
		Is_minus=true;
	}
	else if(lhs.strDigit.length()==rhs.strDigit.length())
	{
		if(lhs.strDigit<rhs.strDigit)
		{
			greater=rhs.strDigit;
			less=lhs.strDigit;
			Is_minus=true;
		}else if(lhs.strDigit==rhs.strDigit)
		{return string("0");}
	}
	delete_zero(greater);
	delete_zero(less);
	int Msize=greater.length()-1;
	int Lsize=less.length()-1;

	int i=Msize;
	int j=Lsize;
	bool flag=false;//借位
	for(;j>=0;i--,j--)
	{
		int ret=greater[i]-less[j];
		if(flag)
		{
			ret-=1;
			flag=false;
		}
		if(ret<0)
		{
			ret+=10;
			flag=true;
		}
		result.push_back(ret+'0');
	}

	while(i>=0)
	{
		int ret=greater[i]-'0';
		if(flag)
		{
			ret-=1;
			flag=false;
		}
		if(ret<0)
		{
			ret+=10;
			flag=true;
		}
		result.push_back(ret+'0');
		i--;
	}
	
	if(Is_minus)
	{
		result.push_back('-');
	}
	reverse(result.begin(),result.end());
	return result;
}

3.大数乘法：

思路：

处理过符号的，三种情况都可以处理：两正 两负 一正一负

BigInt operator*(const BigInt &lhs, const BigInt &rhs)
{
	string greater=lhs.strDigit;
	string less=rhs.strDigit;
	if(lhs.strDigit.length()<rhs.strDigit.length())
	{
		greater=rhs.strDigit;
		less=lhs.strDigit;
	}
	bool Is_minus=false;
	if(greater[0]=='-'|| less[0]=='-')
	{
		if(greater[0]=='-' && less[0]=='-'){
			Is_minus=false;
			delete_minus(greater);
			delete_minus(less);
		}
		else
		{
			Is_minus=true;
			if(greater[0]=='-'){delete_minus(greater);}
			else{delete_minus(less);}
		}
	}
	
	delete_zero(greater);
	delete_zero(less);
	string str;
	vector<string> a;
	
	bool flag=false;//进位
	int count=0;//进位的数值

	int Msize=greater.length()-1;
	int Lsize=less.length()-1;

	int i=Msize;
	int j=Lsize;

	for(;j>=0;j--)
	{
		int k=Lsize-j;
		while(j!=Lsize && k>0)
		{
			str.push_back('0');
			k--;
		}
		for(i=Msize;i>=0;i--)
		{
			int ret=(greater[i]-'0')*(less[j]-'0');
			if(flag)
			{
				ret+=count;
				flag=false;
				count=0;
			}
			if(ret>=10)
			{
				count=ret/10;
				ret%=10;
				flag=true;
			}
			str.push_back(ret+'0');
		}
		if(flag)
		{
			str.push_back(count+'0');
			flag=false;
		}
		reverse(str.begin(),str.end());
		a.push_back(str);
		str.clear();
	
	}
	unsigned int z=1;
	BigInt num1(a[0]);
	while(!a.empty() && z < a.size())
	{
		
		BigInt num2(a[z]);
		num1=num1+num2;

		z++;
	}
	if(Is_minus)
	{
		num1.strDigit.insert(num1.strDigit.begin(),'-');
	}
	return num1;
}

4.大数除法：

完整代码： 

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
class BigInt
{
public:
	BigInt(string str) :strDigit(str){}
	friend ostream& operator<<(ostream &out, const BigInt &src);

	friend BigInt operator+(const BigInt &lhs, const BigInt &rhs);

	friend BigInt operator-(const BigInt &lhs, const BigInt &rhs);

	friend BigInt operator*(const BigInt &lhs, const BigInt &rhs);

	friend BigInt operator/(const BigInt &lhs, const BigInt &rhs);
private:
	string strDigit;   // 使用字符串存储大整数
};

string delete_minus(string &a)
{
		auto it=a.rfind('-');
		a=a.substr(it+1,a.size()-it-1);
		return a;
}
string delete_zero(string &a)
{
	int i=0;
	while(1)
	{
		if(a[i]=='0'){i++;}
		else{break;}
	}
	a=a.substr(i,a.size()-i);
	return a;

	
}
// 打印函数
ostream& operator<<(ostream &out, const BigInt &src)
{
	out<<src.strDigit;
	return out;
}
// 大数加法   （处理正数  可以处理string前面的0）  两个都最后一位开始相加   先判断进位  处理进位  存入到string
BigInt operator+(const BigInt &lhs, const BigInt &rhs)
{
	string greater=lhs.strDigit;
	string less=rhs.strDigit;
	string result;
	if(lhs.strDigit.length()<rhs.strDigit.length())
	{
		greater=rhs.strDigit;
		less=lhs.strDigit;
	}
	delete_zero(greater);
	delete_zero(less);
	int Msize=greater.length()-1;
	int Lsize=less.length()-1;

	int i=Msize;
	int j=Lsize;
	bool flag=false;

	for(;j>=0;i--,j--)
	{
		int ret=greater[i]-'0'+less[j]-'0';
		
		if(flag)
		{
			ret+=1;
			flag=false;
		}

		if(ret>=10)
		{
			ret%=10;
			flag=true;
		}

		result.push_back(ret+'0');

	}
	while(i>=0)
	{
		int ret=greater[i]-'0';
		if(flag)
		{
			ret+=1;
			flag=false;
		}
		if(ret>=10)
		{
			ret%=10;
			flag=true;
		}
		result.push_back(ret+'0');
		i--;
	}
	if(flag)
	{
		result.push_back('1');
	}
	reverse(result.begin(),result.end());
	return result;
}
// 大数减法   判断符号位  从后往前遍历相同位置相减  处理借位  存入string
BigInt operator-(const BigInt &lhs, const BigInt &rhs)
{
	string greater=lhs.strDigit;
	string less=rhs.strDigit;
	string result;
	bool Is_minus=false;

	if(lhs.strDigit.length()<rhs.strDigit.length())
	{
		greater=rhs.strDigit;
		less=lhs.strDigit;
		Is_minus=true;
	}
	else if(lhs.strDigit.length()==rhs.strDigit.length())
	{
		if(lhs.strDigit<rhs.strDigit)
		{
			greater=rhs.strDigit;
			less=lhs.strDigit;
			Is_minus=true;
		}else if(lhs.strDigit==rhs.strDigit)
		{return string("0");}
	}
	delete_zero(greater);
	delete_zero(less);
	int Msize=greater.length()-1;
	int Lsize=less.length()-1;

	int i=Msize;
	int j=Lsize;
	bool flag=false;//借位
	for(;j>=0;i--,j--)
	{
		int ret=greater[i]-less[j];
		if(flag)
		{
			ret-=1;
			flag=false;
		}
		if(ret<0)
		{
			ret+=10;
			flag=true;
		}
		result.push_back(ret+'0');
	}

	while(i>=0)
	{
		int ret=greater[i]-'0';
		if(flag)
		{
			ret-=1;
			flag=false;
		}
		if(ret<0)
		{
			ret+=10;
			flag=true;
		}
		result.push_back(ret+'0');
		i--;
	}
	
	if(Is_minus)
	{
		result.push_back('-');
	}
	reverse(result.begin(),result.end());
	return result;
}

//大数乘法   
/*
思路:
	从后往前遍历长度大的数，将小的最后一位依次相乘，存入到string，内层循环完后将本次乘积的str保存在vector<string> a中，外层循环结束后，a中已经存在了每次乘积的值，利用上面的加法重载依次相加，得到结果。

	处理了符号，其实有三种情况   都正  都负 一正一负  都可以处理
*/
BigInt operator*(const BigInt &lhs, const BigInt &rhs)
{
	string greater=lhs.strDigit;
	string less=rhs.strDigit;
	if(lhs.strDigit.length()<rhs.strDigit.length())
	{
		greater=rhs.strDigit;
		less=lhs.strDigit;
	}
	bool Is_minus=false;
	if(greater[0]=='-'|| less[0]=='-')
	{
		if(greater[0]=='-' && less[0]=='-'){
			Is_minus=false;
			delete_minus(greater);
			delete_minus(less);
		}
		else
		{
			Is_minus=true;
			if(greater[0]=='-'){delete_minus(greater);}
			else{delete_minus(less);}
		}
	}
	
	delete_zero(greater);
	delete_zero(less);
	string str;
	vector<string> a;
	
	bool flag=false;//进位
	int count=0;//进位的数值

	int Msize=greater.length()-1;
	int Lsize=less.length()-1;

	int i=Msize;
	int j=Lsize;

	for(;j>=0;j--)
	{
		int k=Lsize-j;
		while(j!=Lsize && k>0)
		{
			str.push_back('0');
			k--;
		}
		for(i=Msize;i>=0;i--)
		{
			int ret=(greater[i]-'0')*(less[j]-'0');
			if(flag)
			{
				ret+=count;
				flag=false;
				count=0;
			}
			if(ret>=10)
			{
				count=ret/10;
				ret%=10;
				flag=true;
			}
			str.push_back(ret+'0');
		}
		if(flag)
		{
			str.push_back(count+'0');
			flag=false;
		}
		reverse(str.begin(),str.end());
		a.push_back(str);
		str.clear();
	
	}
	unsigned int z=1;
	BigInt num1(a[0]);
	while(!a.empty() && z < a.size())
	{
		
		BigInt num2(a[z]);
		num1=num1+num2;

		z++;
	}
	if(Is_minus)
	{
		num1.strDigit.insert(num1.strDigit.begin(),'-');
	}
	return num1;
}

BigInt operator/(const BigInt &lhs, const BigInt &rhs);


int main()
{
	BigInt int1 = "100";
	BigInt int2 = "00000000110";
	BigInt int3="-122232";
	BigInt int4="-1222122121212";
	cout << int2 + int2 << endl;
	cout << int1 -int2 << endl;
	cout << int3 *int4 << endl;
	cout << int1 *int2 << endl;
	cout << int2 *int2 << endl;
	cout << int1 *int3 << endl;
	system("pause");
	return 0;
}
C/C++ 大数 加减乘除 string STL
上一篇: 5位无符号阵列乘法器设计_基于FPGA器件FLEX10k30A实现成形滤波器的设计用方法
下一篇: 计算加减乘除混合运算python实现_python,实现计算器程序,加减乘除混合运算加括号,完善实现...

继续阅读