C++大整数运算

超、凢脫俗 2021-09-21 04:04 451阅读 0赞

### 大整数运算 ###

*   *  大整数的基本操作
     *   *  大整数的存储
         *  大整数的转化
         *  大数的比较
     *  大数的四则运算
     *   *  高精度加法
         *  高精度减法

在程序设计中，会遇到一些大整数的运算，这时候即使是 `long long`类型也无法表示大整数。这个时候就可以用结构体来实现大整数的存储，计算等操作。

## 大整数的基本操作 ##

### 大整数的存储 ###

定义一个结构体来表示

#include<cstdio>
    #include<algorithm>
    using namespace std;
    struct bign{ 
    	int d[1000];
    	int len;
    	//这里用构造函数初始化以下
    	bign(){ 
    		fill(bign,bign+1000,0);
    		len = 0;
    	}
    }

### 大整数的转化 ###

一般需要用字符串读入大整数，然后把字符串另存到bign结构体中。由于在用字符数组读入大整数的时候，整数的高位会变为数组的地位，因此这里让字符串倒着给d\[\]赋值

//将字符串转化为bign类型来存储
    bign change(char num[]){ 
    	bign a;
    	int len = strlen(num);
    	a.len = len;
    	//将低位存放在下标小的地方 
    	for(int i= 0; i < a.len; i++){ 
    		a.d[i] = num[len-1-i]-'0';
    	}
    	return a;	
    }

### 大数的比较 ###

//大数的比较
    int compare(bign a, bign b){ 
    	if(a.len > b.len) return 1; 
    	else if(a.len < b.len) return -1;
    	else{ 
    		int len = a.len;
    		//从高位开始比起
    		for(int i=len-1; i>=0; i--){ 
    			if(a.d[i] > b.d[i]) return 1;
    			else if(a.d[i] < b.d[i]) return -1;
    		}
    		return 0; //相等 
    	} 
    }

## 大数的四则运算 ##

### 高精度加法 ###

根据加法运算法则：将两个数的对应位数相加（有进位加上进位），取个位作为该为的结果，十位作为新的进位

bign add(bign a,bign b){ 
    	bign c;
    	int carry = 0;//进位
    	for(int i=0; i<a.len || i < b.len; i++) { //已较长的为界限 
    		int temp = a.d[i] + b.d[i] + temp;
    		c.d[c.len++] = temp % 10;
    		carry = temp /10;
    	}
    	if(carry != 0){ //最后进位不为0，直接赋值给最高位 
    		c.d[c.len++] = carry;
    	}
    	return c;
    }

### 高精度减法 ###

减法法则：对应位数相减，若不够减，则向上一位借位：具体实现就是上一位减一，本位加一。要注意最后可能有多余的0，要去除它们，但也要保证结果至少有一位数

bign sub(bign a, bign b){ 
    	bign c;
    	for(int i=0; i<a.len || i<b.len; i++){ 
    		if(a.d[i] < b.d[i]){ 
    			a.d[i+1]--;
    			a.d[i] += 10;
    		}
    		c.d[c.len++] = a.d[i] - b.d[i];
    	}
    	while(c.len-1 >= 1 && c.d[c.len-1]==0){ //去除高位的0，同时保证至少保留一位最低位 
    		c.len--;
    	}
    }

高精度和低精度的乘法  
低精度就是用基本数据类型存储的数据。这里的乘法规则是始终将低精度当做一个整体来看待

bign multi(bign a, int b){ 
    	bign c;
    	int carry = 0;//进位
    	for(int i=0; i<a.len; i++){ 
    		int temp = a.d[i]*b + carry;
    		c.d[c.len++] = temp % 10;
    		carry = temp /10;
    	}
    	while(carry != 0){ //和加法不一样，乘法的进位可能不止一位 
    		c.d[c.len++] = carry % 10;
    		carray /= 10; 
    	}
    	return c;
    	 
    }

高精度和低精度除法  
除法规则和平时计算规则是相同的。上一步的余数乘以十加上该位作为被除数，将其与除数比较，如果不够出，则该位的商为0，如果够除，则商为对应的商，余数即为对应的余数。

bign divide(bign a, int b, int& r){ 
    	bign c;
    	c.len = a.len;//被除数的每一位和商的每一位是对应的
    	for(int i=a.len-1; i>=0; i--){ 
    		r = r*10+a.d[i];
    		if(r<b)c.d[i]=0;//不够除
    		else{ 
    			c.d[i] = r/b;
    			r = r % b;
    		} 
    	}
    	while(c.len-1>=1&&c.d[c.len-1]==0){ 
    		c.len--;
    	}
    	return c; 
    }