大数运算

拼搏现实的明天。 2022-08-14 01:38 178阅读 0赞

文章[位操作实现加减乘除四则运算][Link 1]

当整数很大，在计算机可以表示的范围内无法通过常规的加减等运算计算时，这里介绍的大数运算是一种有效的计算方法。

这里介绍一种方式：将大数表示为一个n进制的数组（分别将大数表示成十进制和N进制），介绍大数的加减乘三种运算。这里仅考虑了非负整数

# **一、将大数表示为10进制** #

## **使用C++** ##

string AddLongInteger(string addend, string augend)
    {
    	if(addend.size() < augend.size())
     		return AddLongInteger(augend,addend);
    
    	int i,j,temp,flag = 0;
     	for(i = addend.size() - 1,j = augend.size() - 1; i >= 0;i--,j--)
    	{
    		if(j >= 0)
    			 temp = addend[i] - '0' + augend[j] - '0' + flag ;
     		else
    			 temp = addend[i] - '0' + flag;
    		if(temp > 9)
    		{
     			flag = 1;
    			temp %= 10;
     		}
     		else flag = 0;
    
    		addend[i] = temp + '0';
    	}
    
     	if(flag)
    		addend = "1" + addend; 
     	return addend;
     }
    
    int main()
    {
    	string str1,str2;
    	 cin >> str1 >> str2;
    	cout << AddLongInteger(str1,str2) << endl;
    	return 0;
    }

## 单独的实现函数    ##

**大数加法**

const int maxn = 1001;
    void BigdataAdd() {
    	char data1_str[maxn], data2_str[maxn];
    	int data1[maxn] = {0}, data2[maxn]  = {0}, data_sum[maxn]  = {0};  //这里初始化为0很重要，之后计算依赖于初始值
    	int len_data1, len_data2, i; 
    	scanf("%s", data1_str);              //由控制台读入第一个char数组形式的大数
    	len_data1 = strlen(data1_str);
    	for (i = 0; i < len_data1; ++i)      //将这个大数存入到int数组中，注意将char数组高位存入int数组地位，方便计算时对齐
    		data1[i] = data1_str[len_data1 - i - 1] - '0';
    	scanf("%s", data2_str);
    	len_data2 = strlen(data2_str);
    	for (i = 0; i < len_data2; i++)
    		data2[i] = data2_str[len_data2 - i - 1] - '0';
    	int max_len = len_data1 > len_data2 ? len_data1 : len_data2; //计算两个数中较大的长度值
    	int flag = 0;                                            // flag：需要进位的值
    	for (i = 0; i < max_len; ++i) {                          //加法运算
    		data_sum[i] = (data1[i] + data2[i] + flag) % 10; //本位的数值
    		flag = (data1[i] + data2[i] + flag) / 10;        //需要进位的数值
     	}
    	printf("Sum: ");
    	if (flag != 0) {                                         //考虑最高位是否进位
    		data_sum[max_len] = 1;                          
    		printf("%d", data_sum[max_len]);                 //输出计算结果最高位
    	}
    	for (i = max_len - 1; i >= 0; --i)                       //输出计算结果其他位
    		printf("%d", data_sum[i]);
    	printf("\n");
    }
    
    int main() {
    	BigdataAdd();
    	return 0;
    }
    
    输出结果（一）：
    1
    2
    Sum: 3
    请按任意键继续. . .

输出结果（二）：

![Center][]

# **大数减法：** #

void BigdataSubtraction() {
    	char data1_str[maxn], data2_str[maxn];
    	int data1[maxn] = {0}, data2[maxn] = {0}, data_sub[maxn] = {0};  //这里初始化为0很重要，之后计算依赖于初始值
    	int len_data1, len_data2;
    	scanf("%s", data1_str);
    	scanf("%s", data2_str);	
    	len_data1 = strlen(data1_str);
    	len_data2 = strlen(data2_str);
    	int bigdata;
    	if (len_data1 > len_data2)  //判断哪个数大，将该数作为被减数
    		bigdata = 1;
    	else if (len_data1 < len_data2)
    		bigdata = -1;
    	else
    		bigdata = strcmp(data1_str, data2_str);
    	int i;
    	if (bigdata >= 0) {
    		for (i = 0; i < len_data1; ++i)
    			data1[i] = data1_str[len_data1 - i - 1] - '0';
    		for (i = 0; i < len_data2; i++)
    			data2[i] = data2_str[len_data2 - i - 1] - '0';
    	}
    	else {
    		for (i = 0; i < len_data2; ++i)
    			data1[i] = data2_str[len_data2 - i - 1] - '0';
    		for (i = 0; i < len_data1; i++)
    			data2[i] = data1_str[len_data1 - i - 1] - '0';
    	}
    
    	int flag = 0;             //flag表示借位
    	int max_len = len_data1 >= len_data2 ? len_data1 : len_data2;
    	for (i = 0; i < max_len; ++i) {
    		int this_sub = data1[i] - flag;
    		data_sub[i] = this_sub - data2[i];
    		if (data_sub[i] >= 0) {
    			flag = 0;
    		}
    		else {
    			flag = 1;
    			data_sub[i] += 10;
    		}
    	}
    	printf("Subtraction: ");
    	if (bigdata < 0) //如果输入的第一个数小，则为结果添加负号
    		printf("-");
    	while (max_len > 1 && !data_sub[max_len - 1])
    		max_len--;
    	for (i = max_len - 1; i >= 0; --i)
    		printf("%d", data_sub[i]);
    	printf("\n");
    }

输出结果（一）：

12  
45  
Subtraction: -33  
请按任意键继续. . .  
  
输出结果（二）：  
![Center 1][]

## **大数乘法：** ##

这里的乘法操作是比较完善的，考虑了数据输入非法、乘数为负数、乘数为0时的输出形式等情况。

string Mutiplication(const string data1, const string data2) {
    	if (data1 == "" || data2 == "") //非法输入
    		return "";
    
    	string result;
    	int length_data1 = data1.size();
    	int length_data2 = data2.size();
    	
    	vector<int> result_number(length_data1 +  length_data2 - 1, 0);
    
    	//处理有负数的情况，data1为负数则data1_end等于1，data2为负数则data2_end等于1
    	int data1_end = 0, data2_end = 0;
    	if (data1[0] - '-' == 0 && data2[0] - '-' == 0) {
    		data1_end = 1;
    		data2_end = 1;
    	}
    	else if (data1[0] - '-' == 0)
    		data1_end = 1;
    	else if (data2[0] - '-' == 0)
    		data2_end = 1;
    	else {}
    
    	for (int i = length_data2 - 1; i >= data2_end; --i) {
    		for (int j = length_data1 - 1; j >= data1_end; --j) {
    			if (!isdigit(data1[j]) || !isdigit(data2[i])) {
    				cerr << "invalid number";
    				return "";
    			}
    			//result_number记录乘法过程中每一位
    			result_number[i + j] += (data2[i] - '0') * (data1[j] - '0');
    		}
    	}
    
    	//处理进位并将结果存到字符串result
    	int carry = 0;
    	for (int i = result_number.size() - 1; i >= 0; --i) {
    		result_number[i] += carry;
    		carry = result_number[i] / 10;
    		result = string(1, result_number[i] % 10 + '0') + result;
    	}
    
    	if (carry > 0) //最高位的进位
    		result = string(1, carry + '0') + result;
    
    	//下面几行处理有乘数为0的情况，如果不处理，会出现：
    	//1234 * 0 = 0000的情况
    	string::iterator iter = result.begin();
    	//如果乘法结果的前n - 1位为0，则将其删除，只保留最后一位
    	while (*iter - '0' == 0 && iter < result.end() - 1) {
    		iter = result.erase(iter);
    	}
    
    	//如果结果为负数则在结果字符串中添加负号
    	if (data1_end ^ data2_end)
    		result = "-" + result;
    	return result;
    }
    
    int main() {
    	string a;
    	string b;
    	while (cin >> a >> b)
    		cout << "result: " << Mutiplication(a, b) << endl;
    }

![SouthEast][]

以上C语言的实现方式只是做了几个单独的测试，各个函数间代码的重复率很高，没有整合，这里仅是给出了大整数运算的实现方法。本文第三部分给出了这部分代码的C++类实现方式。

# **二、将大数表示为N进制数组** #

N的取值越大，数组大小越小，这样可以缩短运算时间以及空间复杂度，提高运算效率。在32位系统中，N可以取2的32次方，此时一位的大小为0~0xffffffff.

当进行加法和乘法运算会进位，则可能要判断溢出，因此，选用long long型(64位)。这里的运算思想和第一部分十进制的运算思想是一致的。

1. 加法运算：

运用”竖式计算“的思想，首先将两个操作数的低位对齐，如果本位所加的结果大于0xffffffff - 1才做进位（flag）处理，否则不进位。

计算0x12 0x2 + 0xffffffff 0xfffffff：

（1）个位：0x2 + 0xffffffff 大于0xfffffff，所以进位，本位结果为1，进位标志flag = 1；

（2）十位：0x12 + 0xffffffff + flag大于0xfffffff，所以进位，本位结果为12，flag = 1；

（3）计算第三位，两个加数均为0，进位为1，所以本位结果为1；

最终计算结果为1 12 1。

2.减法运算：

计算0x1 0x1 0x1 - 0xffffff：

（1）0x1 - 0xfffffff 小于0， 需要借位，本位为2；

（2）十位被个位借了1，因此本位结果为0；

（3）百位结果为1；

最终结果为102。

3. 乘法运算：

计算0x1 0x1 0x1 \* 0xffffff 0xfffffff：

（1）个位：0x1 0x1 0x1 \* 0xffffffff = 0xffffffff0xffffffff0xffffffff；

（2）十位：0x1 0x1 0x1 \* 0xffffffff =0xffffffff0xffffffff0xffffffff，因为这是十位，所以结果为0xffffff0xffffff 0xffffff 0x0；

最终结果：0xffffffff0xffffffff0xffffffff 0x0 + 0xffffffff0xffffffff0xffffffff = 1 0 0xffffffff 0xfffffffe0xffffffff。

**三、第一部分的C++实现：**

const int maxn = 1001;
    class BigData {
        int len;
        int data[maxn];
        BigData Sub(const BigData& a, const BigData& b) {
            int i;
            BigData result;
            int flag = 0;
            for (i = 0; i < a.len; ++i) {
                int this_sub = a.data[i] - flag;
                result.data[i] = this_sub - b.data[i];
                if (result.data[i] >= 0)
                    flag = 0;
                else {
                    flag = 1;
                    result.data[i] += 10;
                }
                result.len = a.len;
            }
            result.clean();
            return result;
        }
    
        void clean() {
            while (len > 1 && !data[len - 1])
                len--;
        }
    
        string str() const {
            string res = "";
            int i;
            for (i = 0; i < len; i++)
                res = (char)(data[i] + '0') + res;
            if (res.empty())
                res = "0";
            return res;
        }
    
    public:
        BigData() {
            memset(data, 0, sizeof(data));
            len = 1;
        }
    
        BigData(int num) {
            *this = num;
        }
    
        BigData(const char* num) {
            *this = num;
        } 
    
        BigData& operator=(int num) {
            char data[maxn];
            sprintf(data, "%d", num);
            *this = data;
            return *this;
        }
    
        BigData& operator=(const char *num) {
            len = strlen(num);
            int i;
            for (i = 0; i < len; ++i)
                data[i] = num[len - i - 1] - '0';
            return *this;
        }
    
        BigData operator+(const BigData& b) const {
            BigData c;
            c.len = 0;
            int i, flag = 0;
            int max_len = len > b.len ? len : b.len;
            for (i = 0; i < max_len; ++i) {
                int sum = (flag + data[i] + b.data[i]);
                c.data[c.len++] = sum % 10;
                flag = sum / 10;
            }
            if (flag != 0)
                c.data[c.len++] = 1;
            c.clean();
            return c;
        }
    
        BigData& operator+=(const BigData& b) {
            *this = *this + b;
            return *this;
        }
        
        BigData& operator-=(const BigData& b) {
            *this = *this - b;
            return *this;
        }
    
        bool operator<(const BigData& b) const {
            if (len != b.len)
                return len < b.len;
            int i;
            for (i = len - 1; i >= 0; --i) {
                if (data[i] != b.data[i])
                    return data[i] < b.data[i];
            }
            return false;
        }
    
        bool operator>(const BigData& b) const {
            return b < *this;
        }
    
        bool operator<=(const BigData& b) const {
            return !(*this > b);
        }
    
        bool operator>=(const BigData& b) const {
            return !(*this < b);
        }
    
        bool operator==(const BigData& b) const {
            return !(*this > b) && !(*this < b);
        }
    
        BigData operator-(const BigData& b) {
            BigData c;
            c.len = 0;
            if (*this == b) {
                c.data[++c.len] = 0;
                return c;
            }
            else if (*this > b) {
                c = Sub(*this, b);
            }
            else {
                c = Sub(b, *this);
                c.data[c.len++] = '-' - '0';
            }
            return c;
        }
    
        BigData operator*(const BigData& b) {
            int i, j, flag;
            BigData result;
            for (i = 0; i < len; ++i) {
                for (j = 0; j < b.len; ++j) {
                    result.data[i + j] = data[i] * b.data[j];
                }
            }
            result.len = len + b.len;
            for (i = 0; i <result.len; ++i) {
                result.data[i + 1] += result.data[i] / 10;
                result.data[i] %= 10;
            }
            result.clean();
            return result;
        }
    
        friend ostream& operator<<(ostream& out, const BigData& bd) {
            out << bd.str();
            return out;
        }
    
        friend istream& operator>>(istream& in, BigData& bd) {
            string s;
            in >> s;
            bd = s.c_str();
            return in;
        }
    };
    
    int main() {
        BigData a, b;
        cin >> a >> b;
        cout << "a: " << a << endl;
        cout << "b: " << b << endl;
        cout << "a+b: " << a + b<< endl;
        cout << "a-b: " << a - b << endl;
        cout << "a*b: " << a * b << endl;
        a += b;
        cout << "a += b: " << a << endl;
        a -= b;
        cout << "a -= b: " << a << endl;
        return 0;
    }

输出结果：

![Center 2][]

[Link 1]: http://blog.csdn.net/u013074465/article/details/42680239
[Center]: /images/20220810/e580ed8e20b34fc3a24a1d12c19d0c3d.png
[Center 1]: /images/20220810/0693c69be3304740a5e33234ac927cb6.png
[SouthEast]: /images/20220810/240a118bb555451c94665b689804662e.png
[Center 2]: /images/20220810/38c70abb1e5b474680bdf41942e2e40b.png