大整数运算

比眉伴天荒 2022-12-22 04:47 151阅读 0赞

### 文章目录 ###

*   *  大整数的存储
     *  比较大小
     *  高精度加法
     *  高精度减法
     *  高精度乘法
     *  高精度除法
     *  完整代码演示（加法）

## 大整数的存储 ##

*  定义结构体

struct bign{
        
    	int d[1000];
    	int len;
    	bign(){
        
    		memset(d, 0, sizeof(d));
    		len = 0;
    	}
    };

*  将整数转换为bign

bign change(char str[]){
        
    		bign a;
    		a.len = strlen(str);
    		for(int i=0; i<a.len; i++)
    		{
        
    			a.d[i] = str[a.len-i-1] - '0';
    			
    		}
    		return a;
    }

## 比较大小 ##

/*比较a和b大小，a大 相等 小分别返回1 0 -1*/ 
    int compare(bign a, bign b){
        
    	if(a.len > b.len){
         //a大 
    		return 1;
    	}
    	else if(a.len<b.len){
         //a小 
    		return -1;
    	}
    	//a b 长度相等 
    	else{
        
    		for(int i=a.len-1; i>=0; i--){
         //从高位往地位比较 
    			if(a.d[i]>b.d[i]){
         //只要有一位a大则a大 
    				return 1;
    			}
    			else if(a.d[i]<b.d[i]){
         //只要有一位a小则a小 
    				return -1;
    			}
    		}
    		return 2; //两数相等 
    	}	
    }

## 高精度加法 ##

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] + carry; //两个对应和进位相加
    		c.d[c.len++ ] = temp % 10; //个位数为该为结果
    		carry = temp /10; //十位数为新的进位 
    	}
    	if(carry!=0){
         //如果最后进位不为0，则直接赋给结果的最高位 
    		c.d[c.len++] = carry;
    	} 
    	return c;
    }

## 高精度减法 ##

bign sub(bign a, bign b){
        
    	bign c;
    	for(int i=0; i<a.len||b.len; i++){
        
    		if(a.d[i]<b.d[i]){
         //不够减 
    			a.d[i+1]--; //向高位借位 
    			a.d[i] += 10; //当前位加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--;
    	} 
    	return c;
    }

## 高精度乘法 ##

/*高精度a*b*/
    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 
    	while(carry!=0){
        
    		c.d[c.len++] = carry % 10;
    		carry /= 10;
    	}
    	return c;
    }

## 高精度除法 ##

/*高精度a/b, r为余数*/
    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){
         //不够除 该位为0 
    			c.d[i] = 0;
    		}
    		else{
         //够除 
    			c.d[i] = r / b; //商 
    			r = r%b; //获得新的余数 
    		}
    	}
    	//去除高位的0，同时至少保留一位最低位 
    	while(c.len-1>=1 && c.d[c.len-1]==0){
        
    		c.len--;
    	}
    	return c;
    }

## 完整代码演示（加法） ##

#include <cstdio>
    #include <cstring>
    
    struct bign{
        
    	int d[1000];
    	int len;
    	bign(){
        
    		memset(d, 0, sizeof(d));
    		len = 0;
    	}
    };
    /*将整数转换为bign*/
    bign change(char str[]){
        
    		bign a;
    		a.len = strlen(str);
    		for(int i=0; i<a.len; i++)
    		{
        
    			a.d[i] = str[a.len-i-1] - '0';
    			
    		}
    		return a;
    }
    /*高精度a+b*/ 
    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] + carry; //两个对应和进位相加
    		c.d[c.len++ ] = temp % 10; //个位数为该为结果
    		carry = temp /10; //十位数为新的进位 
    	}
    	if(carry!=0){
         //如果最后进位不为0，则直接赋给结果的最高位 
    		c.d[c.len++] = carry;
    	} 
    	return c;
    }
    
    /*输出bign*/
    void print(bign a){
        
    	for(int i=a.len-1; i>=0; i--){
        
    		printf("%d", a.d[i]);
    	}
    }
    
    int main(){
        
    	char str1[1000], str2[1000];
    	scanf("%s %s", str1, str2);
    	bign a = change(str1);
    	bign b = change(str2);
    	print(add(a, b));
    
    	return 0;
    }

减法、乘法、除法照葫芦画瓢即可，需要注意减法时需先比较两个数的大小，如果被减数小于减数，需要交换两个变量，然后输出负号，再使用sub函数