大整数运算

小咪咪 2023-06-12 04:19 1阅读 0赞

> 一般数据范围：  
> int型：10^9  
> long long型：10^18  
> double型：10^308  
> 如果要存储的数据比这些还大，就需要使用大整数运算

--------------------

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

*  用数组将大整数的每一位数一次存储 **整数的高位存储在数组的高位，整数的低位存储在数组的低位** (如235813有:d\[0\] = 3, d\[1\] = 1, d\[2\] = 8, d\[3\] = 5, d\[4\] = 3, d\[5\] = 2)  
    因为加法减法乘法都是从低位遍历到高位，只有除法从高位开始  
    所以加法减法乘法即时更新长度，而除法的长度提前确定
 *  一般会定义一个d数组和记录长度的len组成的结构体来表示大整数

struct bign{ 
    	int d[1000];
    	int len;
    	bign()            //构造函数初始化结构体变量，每次定义结构体变量时都会初始化
    	{ 
    		memset(d,0,sizeof(d));
    		len = 0;
    	}
    };
    //bign即为big number

--------------------

### 大整数的四则运算 ###

*  **高精度加法**

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，则直接赋值给结果的最高位
    	{ 
    		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;     //当前位加10
    		}
    		c.d[c.len++] = a.d[i] - b.d[i];
    	}
    	while(c.len - 1 > 0 && c.d[len-1] == 0)    //去除高位的0，同时至少保留一位最低位
    	{ 
    		c.len--;
    	}
    	return c;
    }

--------------------

> tip：乘除法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(carry)            //乘法的进位可能不止一位，因此用while
    	{ 
    		c.d[len++] = carry%10;
    		carry /= 10;
    	}
    	return c;
    }

*  **高精度与低精度的除法**

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 > 0 && c.d[c.len - 1] == 0)
    	{ 
    		c.len--;
    	}
    	return c;
    }

--------------------