大整数加减乘除及取模运算 C++实现

我就是我 2022-09-19 01:45 191阅读 0赞

最近事情实在是太多了，一直没有时间写博客，昨天刚刚忙完硕士开题，虽然还是有很多的事情要做，

但实在是不想弄了。想起一个月之前就已经写完的一个大整数加减乘除法的程序，今天把它贴出来和大家分享，

目前我只是做了简单的测试，可能程序中还存在不好的bug，也希望大家能一块帮着指出其中的错误！！

希望和大家一块学习共勉 .....

工程下载地址（也可以留下邮箱，我会将工程发过去）：http://download.csdn.net/detail/doufei\_ccst/6693721

首先是实现大整数的头文件：BitInt.h

#ifndef		DOUFEI_BIGINT_HEADER
    #define	DOUFEI_BIGINT_HEADER
    #include <string>
    #include <iostream>
    
    class CBigInt
    {
    public:
    	explicit CBigInt() ; 
    	CBigInt(const int i) ; 
    	CBigInt(const std :: string& strValues) ;
    	CBigInt(const CBigInt& bigInt) ; //复制构造函数
    	~CBigInt() ;
    
    public:
    	bool inline isPositive() {return flag ; };
    	int compareBitInt(const CBigInt& rhs)const ; //比较两个数的大小
    	CBigInt& operator = (const CBigInt& rhs) ; //赋值操作符重载
    	friend std :: ostream& operator << (std :: ostream& ou, const CBigInt& bigInt) ; //重载输出操作符
    	friend std :: istream& operator >> (std :: istream& in, CBigInt& bigInt) ; //输入操作符的重载
    	friend const CBigInt operator + (const CBigInt& lhs, const CBigInt& rhs ) ; //加法操作重载
    	friend const CBigInt operator - (const CBigInt& lhs, const CBigInt& rhs) ; //减法操作符重载
    	friend const CBigInt operator * (const CBigInt& lhs, const CBigInt& rhs) ; //乘法操作符重载
    	friend const CBigInt operator / (const CBigInt& lhs, const CBigInt& rhs) ; //除法操作重载
    	friend const CBigInt operator % (const CBigInt& lhs, const CBigInt& rhs) ; //取模运算操作符重载
    
    
    	void setValue(const std :: string& strValues) ; //根据字符串设置数值
    	const CBigInt absolute()const ; //绝对值
    
    
    private:
    	std :: string values ; //保存所有位上的数字
    	bool flag ; //true表示正数，false表示负数，0默认为正数
    };
    
    std :: ostream& operator << (std :: ostream& ou, const CBigInt& bigInt) ;
    std :: istream& operator >> (std :: istream& in, CBigInt& bigInt) ;
    const CBigInt operator + (const CBigInt& lhs, const CBigInt& rhs ) ; //加法操作符重载
    const CBigInt operator - (const CBigInt& lhs, const CBigInt& rhs) ; //剑法操作符重载
    const CBigInt operator * (const CBigInt& lhs, const CBigInt& rhs) ; //乘法操作符重载
    const CBigInt operator / (const CBigInt& lhs, const CBigInt& rhs) ; //除法操作重载
    const CBigInt operator % (const CBigInt& lhs, const CBigInt& rhs) ; //取模运算操作符重载
    
    #endif

BitInt.cpp

#include "BigInt.h"
    #include <cmath>
    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <time.h>
    #include <cassert>
    using namespace std;
    
    CBigInt :: CBigInt() : values(""), flag(true)
    {
    }
    
    CBigInt :: CBigInt(const int i)
    {
    	values.clear() ;
    	if (i >= 0) flag = true ;
    	else
    		flag = false ;
    	int v = abs(i) ;
    	while(v)
    	{
    		values.push_back(char('0' + (v % 10))) ;
    		v /= 10 ;
    	}
    	reverse(values.begin(), values.end()) ;
    	if (values.empty())
    	{
    		values.push_back('0') ;
    		flag = true ;
    	}
    }
    
    CBigInt :: CBigInt(const string& strValues)
    {
    	setValue(strValues) ; //调用成员函数完成
    }
    
    CBigInt :: CBigInt(const CBigInt& bigInt) : values(bigInt.values), flag(bigInt.flag)
    {
    }
    
    CBigInt :: ~CBigInt()
    {}
    
    const CBigInt CBigInt :: absolute() const
    {
    	CBigInt ret(*this) ;
    	ret.flag = true ;
    	return ret ;
    }
    int CBigInt :: compareBitInt(const CBigInt& rhs)const
    {
    	//异号情况
    	if (flag && !rhs.flag) return 1 ;
    	if (!flag && rhs.flag) return -1 ;
    
    	//同号情况，先比较绝对值，然后根据符号判断大小
    	int ret = 0 ;
    	if (values.length() > rhs.values.length()) ret = 1 ;
    	else
    		if (values.length() < rhs.values.length()) ret = -1 ;
    	else
    		ret = values.compare(rhs.values) ;
    
    	if (flag) return ret ;
    	return -ret ;
    }
    
    
    void CBigInt :: setValue(const string& strValues)
    {
    	values.clear() ;
    	string tmpStr(strValues.begin() + strValues.find_first_not_of(' '), strValues.end()) ; //去掉前面的空格
    	if (tmpStr.empty())
    	{
    		values.push_back('0') ;
    		flag = true ;
    		return ;
    	}
    
    	if (tmpStr.at(0) == '-' )
    		flag = false ;
    	else
    		flag = true ;
    	int i = tmpStr.find_first_of("0123456789") ;
    	int j = tmpStr.find_last_of("0123456789") ;
    
    	values = tmpStr.substr(i, j - i + 1) ;//从符号位之后开始的所有数字，直到遇到第一个非数字位
    }
    
    CBigInt& CBigInt :: operator = (const CBigInt& rhs)
    {
    	this->values = rhs.values ;
    	this->flag = rhs.flag ;
    	return *this ;
    }
    
    ostream& operator << (ostream& ou, const CBigInt& bigInt)
    {
    	if (!bigInt.flag)
    		ou << '-';
    	ou << bigInt.values ;
    	return ou ;
    }
    
    istream& operator >> (istream& in, CBigInt& bigInt)
    {
    	string str ;
    	in >> str ;
    	bigInt.setValue(str) ; //设置读入的新的数值
    	return in ;
    }
    
    const CBigInt operator + (const CBigInt& lhs, const CBigInt& rhs)
    {
    	CBigInt ret ;
    	if (lhs.flag == rhs.flag) //符号相同
    	{
    		string lvalues(lhs.values) , rvalues(rhs.values) ;
    		reverse(lvalues.begin(), lvalues.end()) ;
    		reverse(rvalues.begin(), rvalues.end()) ;
    
    		//逐位相加
    		int i = 0;
    		for ( ; i < lvalues.length() && i < rvalues.length(); ++ i)
    			ret.values.push_back(lvalues.at(i) + rvalues.at(i) - '0') ;
    
    		if (i < lvalues.length())
    			for (; i < lvalues.length(); ++ i)
    				ret.values.push_back(lvalues.at(i)) ;
    		else
    			for (; i < rvalues.length(); ++ i)
    				ret.values.push_back(rvalues.at(i)) ;
    		//处理进位
    		int carry = 0;
    		for (int i = 0; i < ret.values.length(); ++ i)
    		{
    			int newValue = ret.values.at(i) - '0' + carry ;
    			carry = newValue/ 10 ;
    			ret.values.at(i) = newValue - carry * 10 + '0' ;
    		}
    		if (carry)
    			ret.values.push_back(carry + '0') ;
    
    		//处理符号
    		ret.flag = lhs.flag ;
    	}
    	else //符号不同
    	{
    		CBigInt absL = lhs.absolute() ;
    		CBigInt absR = rhs.absolute() ;
    		int compFlag = absL.compareBitInt(absR) ;
    		if (compFlag == 0)
    		{
    			ret.setValue("0") ;
    			ret.flag = true ;
    			return ret ;
    		}
    		else
    		{
    			if (compFlag == -1) //交换位置，使得absL > absR
    			{
    				CBigInt tmp(absL) ;
    				absL = absR ;
    				absR = tmp ;
    			}
    
    			reverse(absL.values.begin(), absL.values.end()) ;
    			reverse(absR.values.begin(), absR.values.end()) ;
    
    			//处理差值
    			int i = 0;
    			for (; i < absL.values.length() && i < absR.values.length(); ++ i)
    				ret.values.push_back(absL.values.at(i) - absR.values.at(i) + '0') ;
    			
    			if (i < absL.values.length()) //不可能出现i < absR.values.length()的情况
    				for (; i < absL.values.length(); ++ i) 
    					ret.values.push_back(absL.values.at(i)) ;
    			
    			//处理借位
    			int carry = 0 ;
    			for (i = 0; i < ret.values.length(); ++ i)
    			{
    				int newValue = ret.values.at(i) - carry - '0' ;
    				if (newValue < 0) carry = 1 ; //向前借位
    				else carry = 0 ;
    				ret.values.at(i) = newValue + carry * 10 + '0' ;
    			}
    			//处理符号
    			if (compFlag == 1)
    				ret.flag = lhs.flag ;
    			else
    				ret.flag = rhs.flag;
    		}
    	}
    
    	reverse(ret.values.begin(), ret.values.end()) ;
    	int i = ret.values.find_first_not_of(" 0") ;
    	if (i == string :: npos)//空的，说明结果是0
    	{
    		ret.setValue("0") ;
    		ret.flag = true ;
    		return ret ;
    	}
    	ret.values = string(ret.values.begin() + ret.values.find_first_not_of(" 0"), ret.values.end()) ; //去掉前面的空白和0
    	return ret ;
    }
    
    const CBigInt operator - (const CBigInt& lhs, const CBigInt& rhs)
    {
    	CBigInt tmpRhs(rhs) ;
    	tmpRhs.flag = !tmpRhs.flag ; //取负号
    
    	return (lhs + tmpRhs) ;
    }
    
    //乘法操作符重载
    const CBigInt operator * (const CBigInt& lhs, const CBigInt& rhs)
    {
    	CBigInt ret ;
    	int flag1 = lhs.compareBitInt(CBigInt(0)) ;
    	int flag2 = rhs.compareBitInt(CBigInt(0)) ;
    	if (flag1 == 0 || flag2 == 0)
    	{
    		ret.setValue("0") ;
    		ret.flag = true ;
    		return ret ;
    	}
    	if (lhs.flag == rhs.flag) 
    		ret.flag = true ;//同号为正，异号为负
    	else 
    		ret.flag = false ;
    
    	string lvalues(lhs.values), rvalues(rhs.values) ;
    	reverse(lvalues.begin(), lvalues.end())  ;
    	reverse(rvalues.begin(), rvalues.end()) ;
    	ret.values.resize(lvalues.size() + rvalues.size(), '0') ;
    
    	//相乘
    	for (int i = 0; i < lvalues.size(); ++ i)
    		for (int j = 0; j < rvalues.size(); ++ j)
    		{
    			int newValue = ret.values[i + j] +  (lvalues[i] - '0') * (rvalues[j] - '0') - '0';
    			int carry = newValue / 10 ;
    			ret.values[i + j] = newValue % 10 + '0' ;
    
    			//这里之所以对每一位进行进位处理，是为了防止出现溢出情况的出现，如'0' + 9 * 9 = 48 + 81 > 127已经溢出
    			for (int k = i + j + 1; carry != 0 && k < ret.values.size(); ++ k) //处理进位
    			{
    				ret.values[ k - 1 ] = newValue % 10 + '0' ;
    				newValue = ret.values[k] + carry - '0';
    				ret.values[k] = newValue % 10 + '0' ;
    				carry = newValue / 10 ;
    			}
    		}
    
    	reverse(ret.values.begin(), ret.values.end()) ; //翻转
    	ret.values = string(ret.values.begin() + ret.values.find_first_not_of(" 0"), ret.values.end()) ; //去掉前面的空白和0
    
    	return ret ;
    }
    
    const CBigInt operator / (const CBigInt& lhs, const CBigInt& rhs)  //除法操作重载
    {
    	CBigInt ret ;
    	assert(rhs.compareBitInt(CBigInt(0)) != 0) ;
    	ret.setValue("0") ; //初始化为0
    
    	CBigInt absL(lhs.absolute()) ;
    	CBigInt absR(rhs.absolute()) ;
    
    	int comFlag = absL.compareBitInt(absR) ;
    	if (comFlag < 0)
    		return ret ;
    	if(comFlag == 0)
    	{
    		ret.setValue("1") ;
    		if (lhs.flag == rhs.flag) ret.flag = true ;
    		else
    			ret.flag = false ;
    		return ret ;
    	}
    	int movCount = absL.values.size() - absR.values.size() ;
    
    	const CBigInt tenBigInt(10) ;
    	//使用减法实现除法的操作
    	do 
    	{
    		CBigInt tmp(absR) ;
    		for (int i = 0; i < movCount; ++ i) //tmp是10的movCount次方
    			tmp = tmp * tenBigInt ;
    		int addNum = 0 ;
    		while(absL.compareBitInt(tmp) >= 0)
    		{
    			absL = absL - tmp ;
    			addNum ++ ;
    		}
    
    		ret = ret * tenBigInt + CBigInt (addNum) ;
    
    		movCount -- ;
    
    	}while (movCount >= 0);
    
    	if (lhs.flag == rhs.flag) ret.flag = true ;
    	else
    		ret.flag = false ;
    
    	return ret ;
    }
    
    const CBigInt operator % (const CBigInt& lhs, const CBigInt& rhs)  //取模运算操作符重载
    {
    	CBigInt divTmp = lhs / rhs ;
    	return (lhs - rhs * divTmp) ;
    }

测试主函数：main.cpp

#include <iostream>
    #include <fstream>
    #include "BigInt.h"
    #include <string>
    using namespace std ;
    
    
    int main(int argc, char** argv)
    {
    	ifstream in("data.txt") ;
    #define  cin in 
    	string num1, num2 ;
    	cin >> num1 >> num2 ;
    	CBigInt bi1(num1);
    	CBigInt bi2(num2) ;
    	cout << "第一个操作数是：" << bi1 << endl ;
    	cout << "第二个操作数是：" << bi2 << endl;
    	cout << "乘法结果:" << bi1 * bi2 << endl;
    	cout <<"加法结果：" << (bi1 + bi2) << endl;
    	cout << "减法结果：" <<(bi1 - bi2) << endl;
    	cout << "除法的结果是：" << bi1/bi2 << endl;
    	cout << "取模的结果是：" << bi1 % bi2 << endl;
    	return 0 ;
    }

测试数据放在一个data.txt文件中，内容是两个操作数，如下：

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
    -999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998999899989998

程序的运行结果是：

![SouthEast][]![SouthEast 1][]

工程下载地址（也可以留下邮箱，我会将工程发过去）：http://download.csdn.net/detail/doufei\_ccst/6693721

希望能够指正程序中的错误和不足，共同学习进步 ....

[SouthEast]: https://img-blog.csdn.net/20131210211903000?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZG91ZmVpX2Njc3Q=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: /images/20220828/8030d53990914a788ade154e065b8f33.png