前言
这种类型，在做题过程中多为观察所给数据可能造成的大小来选择是否使用。
属于模板类型，学习者理解其格式并记住大致框架即可熟练应用。
一、什么是大整数（高精度）
想知道什么是大整数，不如换一个解释的方法：什么时候需要用到大整数？
众所周知，int类型的范围是-2147483648~2147483647。long long类型的范围是 -2^63 ~ (2^63)-1。那当题目需要用到或需要输出比long long类型的范围还要大的数字时，我们是不是就不能用常规办法去接收这些数字了。这个时候使用大整数就可以解决上述问题。即解决接收超出long long范围数字的问题。
二、大整数的存储
原理很简单，使用数组。
例如定义Int类型数组d[1000]，那么这个数组中的每一位就代表存放整数的每一位。比如将数字123456存储，则有d[0] = 6,d[1] = 5,d[2] = 4,d[3] = 3,d[4] = 2,d[5] = 1。整数的高位存在数组的高位，整数的低位存储在数组的低位。（为了契合加减乘除的思维）
这时候会产生一个需要注意的问题：把整数通过%s或者itoa的方式变成字符串的时候，一开始是逆位存储的，即d[0] = 1...，因此读入的之后需要在另存为至d[i]数组的时候反转一下。
为了方便随时获取大整数的长度，一般定义len来记录长度，并与d数组组合成结构体。
1. struct bign{ 2. int d[1000]; 3. int len; 4. };
一般输入大整数时，都是先用字符串读入，然后再把字符串另存为至bign结构体。由于使用char数组进行读入时，整数高位会变成数组地位，整数的地位会变成数组的高位。因此为了让整数在bign中是顺位存储，需要让字符串倒着赋值给d[]数组。
1. bign change(char str[])//将整数转换为bign 2. { 3. bign a; 4. a.len = strlen(str);//bign的长度就是字符串的长度 5. for(int i = 0; i < a.len; i++) 6. { 7. a.d[i] = str[a.len-i-1] - '0'; 8. } 9. return a; 10. }
如果要比较两个bign变量的大小，也很简单：先判断len大小，若不相等，长的为大，若相等，则从高位至低位逐个比较，直到某一位不等，则可以判断两者大小。
1. int compare(bign a,bign b) 2. { 3. if(a.len > b.len) return 1;//a大 4. else if(a.len < b.len) return -1;//a小 5. else 6. { 7. for(int i = a.len - 1; i >= 0; i--)//从高位到低位开始比较 8. { 9. if(a.d[i] > b.d[i]) return 1;//只要有一位a大，则a大 10. else if(a.d[i] < b.d[i]) return -1;//只要有一位a小，则a小 11. } 12. return 0;//两位相等 13. } 14. }
最后如果需要输出bign变量的值，遍历一遍就可以实现了。
1. void print(bign a) 2. { 3. for(int i = a.len - 1; i >= 0; i--) 4. { 5. printf("%d",a.d[i]); 6. } 7. printf("\n"); 8. }
三、大整数的四则运算
1、高精度加法
加法实现方式与我们以前学到的加法一样。对于某一位的运算：我们将该位上的两个数字与进位相加，得到的结果取个位数作为该结果，十位数作为新的进位。
1. bign add(bign a,bign b) 2. { 3. bign c; 4. int carry = 0; //carry是进位 5. for(int i = 0; i < a.len || i < b.len; i++) //以较长的为界限 6. { 7. int temp = a.d[i] + b.d[i] + carry; //两个对应位与进位相加 8. c.d[c.len++] = temp%10; //个位数为该位的结果 9. carry = temp/10; //十位数为新的进位 10. } 11. if(carry != 0) //如果最后进位不为0，则直接赋给结果的最高位 12. { 13. c.d[c.len++] = carry; 14. } 15. return c; 16. }
这里有一点需要注意，这样写法的条件是两个对象都是非负整数。如果有一方是负的，可以在转换到数组这一步时去掉符号，再使用高精度减法；如果两个都是负的，都去掉负号后采用高精度加法，最后负号加回去即可。
2、 高精度减法
通过对减法步骤的拆分可以得到一个简练的步骤：对某一位，比较被减位和减位，如果不够减，则令被减位的高位减1，被减位加10再进行减法；如果够减，直接减。最后需要注意减法后高位可能有多余的0，要去除他们，但也要保证结果至少有一位数。
1. bign sub(bign a,bign b) //a - b 2. { 3. bign c; 4. for(int i = 0; i < a.len || i < b.len; i++) //以较长的为界限 5. { 6. if(a.d[i] < b.d[i]) //不够减 7. { 8. a.d[i + 1]--; //向高位借位 9. a.d[i] += 10; //向前位借10 10. } 11. c.d[c.len++] = a.d[i] - b.d[i]; //减法结果为当前位 12. } 13. while(c.len - 1 >= 1 && c.d[c.len - 1] == 0) 14. { 15. c.len--; //去除高位的0，同时至少保留一位最低位 16. } 17. return c; 18. }
最后需要指出，使用sub函数前要比较两个数的大小，如果被减数小于减数，需要交换两个变量，然后输出负号，再用sub函数。
3、高精度与低精度的乘法
这里所谓的低精度就是基本数据类型存储的数据，如int。这里就是bign与int的乘法。
对某一位来说是这样的步骤：取bign的某位与int型整体相乘，再与进位相加，所得结果的个位数作为该结果，高位部分作为新的进位。
1. bign multi(bign a,int b) 2. { 3. bign c; 4. int carry = 0; //进位 5. for(int i = 0; i < a.len; i++) 6. { 7. int temp = a.d[i] * b + carry; 8. c.d[c.len++] = temp % 10; //个位作为该结果 9. carry = temp / 10; //高位部分作为新的进位 10. } 11. 12. while(carry != 0) //和加法不一样，乘法的进位可能不止一位，因此用while 13. { 14. c.d[c.len++] = carry % 10; 15. carry /= 10; 16. } 17. return c; 18. }
另外，如果a和b中存在负数，需要先记录下负号，然后取他们的绝对值带入函数。
4、高精度与低精度的除法
归纳其中一位的步骤：上一步的余数乘以10加上该步的位，得到该步临时的被除数，将其与除数比较；如果不够除，则该位的商为0；如果够除，则商即为对应的商，余数即为对应的余数。最后一步要注意减法后高位可能有多余的0，要去除他们，但也要保证结果至少有一位数。
1. bign divide(bign a,int b,int& r) //r为余数 2. { 3. bign c; 4. c.len = a.len;//被除数的每一位和商的每一位是一一对应的，因此先令长度相等 5. for(int i = a.len - 1; i >= 0; i--) //从高位开始 6. { 7. r = r * 10 + a.d[i]; //和上一位遗留的余数组合 8. if(r < b) c.d[i] = 0; //不够除，该位为0 9. else //够除 10. { 11. c.d[i] = r / b; //商 12. r = r % b; //获得新的余数 13. } 14. } 15. while(c.len - 1 >= 1 && c.d[c.len - 1] == 0) 16. { 17. c.len--; //去除高位的0，同时至少保留一位最低位 18. } 19. return c; 20. }
考虑到很多题目会要求得到余数，因此把余数写成引用的形式直接作为参数传入，或者也可以把余数设成全局变量。
