为什么会有大数呢？因为long long通常为64位范围约为 -9,223,372,036,854,775,808 到 9,223,372,036,854,775,807，最多也就19位，那么超过19位的如何计算呢？这就引申出来大数了。
本博客适合思考过这道题，但是没做出来或感觉代码不够简洁的朋友来看。
简述
通过这道题，我加深了对数据处理的重要性以及模块化编程的重要性，虽然没有用到高级的算法，但是给我带来了好多新的想法。
加减乘除运算为人类发明的，那么这道题自然要用人类的思路来解这道题，我们小学便以及学过，故我们只需要将小学的做题思维转化为我们的高级语言就行了。简单点来说就是模拟我们运算加减乘除的过程。
总代码不超过一百行，但如果我们的数据处理不好，和不以一个小学生的思维去做这道题，那二百行都不一定写得完。我之前的写法便是没有以一个正常人的思维去思考，昨天问了老师这道题，才理清问题。
- 加法运算：两个数从低位到高位依次相加，大于10进位。
- 减法运算：两个数从低位到高位依次相加，大于10补位。
- 乘法运算：乘数的从低位到高位每一位都乘以被乘数，大于10进位。
- 除法运算：从被除数的最高位开始，减去商的一位乘以除数，将余数补位。
首先要考虑的便是数据存储的问题。输入30位整数：
100000000000000000000000000030
从左到右依次减小，超过19为位肯定要用数组存了，那么用什么类型呢，这里每一个地址存储一个个位数，那么就不超过4个bit，其实用半个bits就行了，我们这里就用1个bist的char类型来存储。这里我们假设所有输入的数字不超过50位（范围很重要，范围一旦确定，这道题就会简单很多了）。
我们定义大数类型:
#define N 50
typedef char BIG_NUM[N];//存储大数输入/输出模块
运算无非就是进位和补位，那么怎么才能进位和补位方便呢？我们的输入输出方式要使得进位和补位方便，现在我展示两种方法：
- 靠右存储：高位补零 ，去除补零外，从左到右依次减小。
- 靠左存储：低位补零，去除补零外，从左到右依次减小。
我们既要保证进位补位方便还要保证输入输出方便。假设我们用靠左存储存储，如果计算998+2=1000的话，那么得到的结果就需要手动进位，并且我们还要计算位数。
如果用靠右存储的话，左边高位补0，因为0+0=0，0*0=0，0/0=0，0-0=0，故我们不需要考虑进位问题，因为只要位数不超过50，那么高位的0再需要进位时更改就行了，至于位数问题，那就只需再输出时去掉高位的零就行了。
故我们就已经确定了输入输出模块的内容了。
输入的时候因为是从高到低输入，不知道具体多少位，所以我们需要先靠左存储，然后移位到右边。
输出时从左到右（高位到低位）依次输出，可以选择是否输出高位0。
输入
void input(BIG_NUM x)
{
int i, j;
for(i=0; i<N && isdigit(x[i]=getchar()); ++i) x[i] -= '0';//i（从0开始）为大数加上'\n'的个数
for(--i, j=N-1;i>=0;--i,--j) x[j] = x[i];//移位至靠右存储先执行一个i--,是因为现在的x[i]是'\n'
for(;j>=0;--j) x[j] = 0;//前面补0
}输出
void output(BIG_NUM x)
{
int i;
for(i=0; i<N-1 && x[i]==0; ++i);//i<N-1因为要保证结果为0的情况
for(; i<N; ++i) putchar('0'+x[i]);
}加法
int add(BIG_NUM x, BIG_NUM y, BIG_NUM z) /* z = x + y */
{
int i, carry;
for(i=N-1, carry=0; i>=0; --i)
{
int s = x[i] + y[i] + carry;
z[i] = s % 10;
carry = s / 10;
}
return carry;
}这里如果返回的carry不为0就代表得到的结果大于五十位，可以在根据实际情况进行改进。
减法
int sub(BIG_NUM x, BIG_NUM y, BIG_NUM z) /* z = x - y */
{
int i, carry;
for(i=N-1, carry=0; i>=0; --i)
{
int s = x[i] - y[i] - carry;
if( s < 0) {carry = 1; s = 10 + s;} else carry = 0;
z[i] = s;
}
return carry;
}carry返回为1就代表相减的两个数，第一个小于第二个。
乘法
int mul(BIG_NUM x, BIG_NUM y, BIG_NUM z) /* z = x * y */
{
int i, j, carry;
char t[N+N];
memset(t, 0, N+N);
for(j=N-1; j>=0; --j)
for(i=N-1, carry=0; i>=0; --i)
{
int s = t[i+j+1] + x[i] * y[j] + carry;
t[i+j+1] = s % 10;
carry = s / 10;
}
t[0] = carry;
for(i=0; i<N; ++i) z[i] = t[i+N];
for(i=0, carry=0; i<N; ++i) carry |= t[i];//判断是否超过50
return carry;
}这里如果返回的carry不为0就代表得到的结果大于五十位，可以在根据实际情况进行改进。其中t是100位，可以适当调整。
除法
除法部分稍微复杂，但还是模拟小学做题，每一位商的值就是1-9，和我们算除法一样，这一点用到逆向思维，这九种情况我们需要一个一个来试试。比如108/9=n，换成n*9=108,n的值为1-9一个一个试，如果n为9还是不够，那么剩下的就是余数，下一位就需要减少余数*10。
我们这里做一个例子模仿一下代码的运算。如1080/9，先判断1-n*9，当n为0时，余数1，当n为1时，余数为负，故这一位的商为0，余数为1；
再判断 1*10+0-n*9,这里的n为1，依次类推便能得到结果为120.
代码如下：
void seti(BIG_NUM x, unsigned int u){ /* y = u */
int i, s;
for(i=N-1, s=u; i>=0; --i){ x[i] = s % 10; s /= 10; }
}
void set(BIG_NUM y, BIG_NUM x){ /* y = x */
memcpy(y, x, N);
}
void div(BIG_NUM x, BIG_NUM y, BIG_NUM z, BIG_NUM r) /* z = x / y */
{
int i, q;
BIG_NUM ten, s, t;
seti(r, 0);//初始化赋零
seti(ten, 10);//用于补位的余数*10
seti(s, 0);//初始化赋零
for(i=0; i<N; ++i)
{
mul(r, ten, r);//余数高位到低位需乘10
seti(s, x[i]);/* s = x[i] x[i]为被除数的某一位*/
add(r, s, r);/* r = r+s*/
for(q=0; q<10 && !sub(r, y, t); ++q)
/* r=r-y */ set(r, t);//每次循环t减小，最后一次循环得到的t为余数
z[i] = q;
}
}总结
大数运算可以扩展的有很多，比如这几个模块没有考虑负数情况,还有结果大于五十位的扩展等等，但核心部分已经解决，这些根据情况而定，我把这些叫做程序预处理，如下：
正负判断（程序预处理）
四种情况：++；+-；-+；--
+ +：不影响计算
- +：乘除先剔除符号在运算，加法剔除A的负号，A+B变成B-A，减法剔除A的负号，A-B变成-（A+B）
+ -: 乘除先剔除符号在运算, 加法剔除B的负号，A+B变成A-B，减法剔除B的负号，A-B变成A+B
- -：乘除先剔除符号在运算，加法剔除负号,A+B变成-(A+B),减法剔除负号,A-B变成B-A；
模块化的好处就是代码清晰明了，省略了好多冗杂的部分，而且不同函数之间的引用和扩展性能变高。
总的来说，这道题也是数据思维的一种体现，正确的数据理解和思维，大大降低了程序设计的难度，带来的效果有时候比算法的优化效果更棒！
