正常的加减乘除运算都在long范围内，最大的long long型变量只能存储-263 ~ 263-1范围（-9223372036854775808～9223372036854775807）内，所以如果给一个1000位的整数运算就无法完成了。所以此时我们需要专门解决大整数运算的问题。
- 首先是存储，改用字符串存储数组。数据是倒着存储，然后第一位存储数字的长度。比如：
数字13579，存储： “13579” =》" 5 9 7 5 3 1 "，倒着存是为了更方便的统计进位。 - 对数据做运算。
- 完成进位 *** 作，数字的长度可能是变长的。
- 先分别字符串存储好两个大数，第一位数字长度，后面倒序存储。
- 然后从最低位开始相加，每一位直接得出加法结果。
- 对每一位判断是否大于9，大于9需要进位，前一位取模，后一位取十位。
- 最后判断最后一位是否要进位。如果需要进位，则第一位长度也需要加1。
比如1 3 5 7 9 + 8 3 2的运算示意图如上。最终得到结果是1 4 4 1 1，但是存储时仍是5 1 1 4 4 1。
代码如下：
#include#include #include void print_arr(int *arr, char *s) { // 输出数组的值 printf("%s：", s); for(int i = arr[0]; i > 0; i--) { printf("%d", arr[i]); } printf("n"); return ; } int big_add(int *a, int *b, int *ans_ab) { ans_ab[0] = a[0] > b[0] ? a[0] : b[0]; // 和的长度 for (int i = 1; i <= ans_ab[0]; i++) { ans_ab[i] = a[i] + b[i]; // 加法运算 } for(int i = 1; i <= ans_ab[0]; i++) { // 处理进位 if (ans_ab[i] > 9) { ans_ab[i + 1] += ans_ab[i] / 10; ans_ab[i] %= 10; if (i == ans_ab[0]) ans_ab[0]++; // 最高位大于9，长度+1 } } return 1; } int main() { char s1[1005] = {0}, s2[1005] = {0}; while (~scanf("%s%s", s1, s2)) { int n1[1005] = {0}, n2[1005] = {0}, ans[1005] = {0}; printf("n%s + %s = n", s1, s2); //1、 格式转换 int n1_len = strlen(s1); int n2_len = strlen(s2); n1[0] = n1_len; n2[0] = n2_len; for (int i = 1, j = n1[0] - 1; i <= n1[0]; i++, j--) { n1[i] = s1[j] - '0'; // 每一位转换成数字，倒着存 } for (int i = 1, j = n2[0] - 1; i <= n2[0]; i++, j--) { n2[i] = s2[j] - '0'; } //2、 算法计算------------------- big_add(n1, n2, ans); print_arr(ans, "sum"); printf("n"); } return 0; }
测试结果：
99999 2 99999 + 2 = sum：100001 132165461988781916 2315616156 132165461988781916 + 2315616156 = sum：132165464304398072二、大整数的减法
-
存储好两个大数，第一位数字长度，后面倒序存储。
-
然后从最低位开始相减。
-
对每一位判断大小关系，若小于往前借1位，然后本位加10，前一位减1。
-
提前判断大小关系，若小于，则交换两个数再相减，然后提前输出负号。
比如3 1 2 - 6 5的运算示意图如上。最终得到结果是2 5 6，存储时是3 6 5 2。
代码如下：
#include
#include char s1[1005], s2[1005]; int n1[1005], n2[1005], ans[1005]; // 交换两个数组 void swap_arr(int *n1, int *n2) { int max_len = n1[0] > n2[0] ? n1[0] : n2[0]; int temp; for (int i = 0; i <= max_len; i++) { temp = n2[i]; n2[i] = n1[i]; n1[i] = temp; } return ; } // 计算大整数减法 n1 - n2 int main() { scanf("%s%s", s1, s2); int flag = 1; // 如果 n1 > n2 即 flag = 1 int n1_len = strlen(s1); int n2_len = strlen(s2); n1[0] = n1_len; n2[0] = n2_len; for (int i = 1, j = n1[0] - 1; i <= n1[0]; i++, j--) { n1[i] = s1[j] - '0'; } for (int i = 1, j = n2[0] - 1; i <= n2[0]; i++, j--) { n2[i] = s2[j] - '0'; } if (n1[0] < n2[0]) flag = 0; if (n1[0] == n2[0]) { int i = n1[0]; while (i > 0) { if (n1[i] == n2[i]) i--; if (n1[i] < n2[i]) { flag = 0; break; } } if (i == 0) { printf("%dn", 0); // 位数相等，每一位也相等，差值为0 return 0; } } if (flag == 0) swap_arr(n1, n2); // n1 < n2 交换相减 for (int i = 1; i <= n1[0]; i++) { if (n1[i] < n2[i]) { n1[i] += 10; n1[i + 1] -= 1; } ans[i] = n1[i] - n2[i]; } if (flag == 0) printf("-"); int flag_0 = 0; // 判断当前的0是否要输出，如果之前输出过正整数，则当前的0需要输出 for(int i = n1[0]; i > 0; i--) { if (ans[i]) printf("%d", ans[i]), flag_0 = 1; if (ans[i] == 0 && flag_0 == 1) printf("%d", 0); } printf("n"); return 0; } 测试结果：
32156 213 31943 121651561654132154 9841516163 121651551812615991 985616 1218967419743515 -1218967418757899
- 倒序存储好两个大数。
- 计算可能的结果的长度，假设乘数1的长度为x，乘数2的长度为y，根据10 * 10 = 100， 99 * 99 = 9801，所以结果长度最多为x+y，最小为x+y-1，因此初设长度为x+y-1位，然后看实际进位情况。
- 乘数的个位依次乘积得到的结果依次从个位往前排，十位乘积得到的结果依次从十位开始往前排，依次类推，乘积并累加的位置在x+y-1处。
- 逐位累加，然后进行进位判断。
代码如下：
#include#include char s1[1005], s2[1005]; int n1[1005], n2[1005], ans[2005]; // 计算大整数乘法 n1 * n2 int main() { scanf("%s%s", s1, s2); int n1_len = strlen(s1); int n2_len = strlen(s2); n1[0] = n1_len; n2[0] = n2_len; for (int i = 1, j = n1[0] - 1; i <= n1[0]; i++, j--) { n1[i] = s1[j] - '0'; } for (int i = 1, j = n2[0] - 1; i <= n2[0]; i++, j--) { n2[i] = s2[j] - '0'; } ans[0] = n1[0] + n2[0] - 1; for (int i = 1; i <= n1[0]; i++) { for (int j = 1; j <= n2[0]; j++) { ans[i + j - 1] += n1[i] * n2[j]; // 乘法运算 } } for(int i = 1; i <= ans[0]; i++) { // 处理进位 if (ans[i] > 9) { ans[i + 1] += ans[i] / 10; ans[i] %= 10; if (i == ans[0]) ans[0]++; } } for(int i = ans[0]; i > 0 ; i--) { printf("%d", ans[i]); } printf("n"); return 0; }
测试结果：
666 3 1998 1566196874949 2156449863165 3377425036673221666353585四、大整数的除法
大整数的除法相对就比较复杂了，又分为大整数 / 小整数，大整数 / 大整数。正常除法有四个元素，被除数，除数，商，余数。例如：53 / 8 = 6 余 5 ，其中53 为被除数，8为除数，6为商，5为余数。来回顾一下除法的过程，53首位是5，小于8，商为0，然后往后组成被除数53，除以8的结果只会在1-9之间，依次从1开始乘，1 * 8 = 8，53-8 = 45，仍然大于8，所以改为2相乘，依次计算到6，8 * 6 = 48，53 - 48 = 5，5小于8了即得到了该位的除法结果，此时余数有5，如果后面有位数，依次跟5结合，重复计算。
实际上就是在模拟小学时学习除法的过程，待除数记录当前数字，一直在变化，然后商不断循环从1到9，计算乘积和差值，直到计算完整个数，最后待除数的值就是余数，商即为计算的结果。
4.1 大整数 / 小整数大整数/小整数的情况，可以将大整数拆开为待除数，转化为long型范围内的整数，然后计算结果直接用/ 和%运算符，代码如下：
int get_len(int n) {
if (n == 0) return 1;
int len = 0;
while(n) {
n /= 10;
len++;
}
return len;
}
// 大整数除法: 大整数 a / 小整数 b
int big_div_int(int *a, int *b, int *res, int *res_mod) {
// 1- 将数组转换成整数
int x = 0; // 小整数x
for (int i = b[0]; i > 0; i--) {
x = x * 10 + b[i];
}
// 2- 求解
int dividend = 0; //被除数(待除数), 除数为b
int _res, _res_mod; // 商，余数
int res_len = 0; // 商的长度
for (int i = a[0]; i > 0; i--) {
dividend = dividend * 10 + a[i];
if (dividend < x) {
res[i] = 0;
if (res_len) res_len++; // 若已经得出商的值，中间的0需要加上位数
continue;
}
_res = dividend / x;
_res_mod = dividend % x;
res[i] = (int) _res;
dividend = _res_mod;
res_len++; // 商的长度+1
}
// 3- 传结果出去
res_mod[0] = get_len(dividend); // 余数的长度
for (int i = 1; i <= res_mod[0]; i++) {
res_mod[i] = dividend % 10;
dividend /= 10;
}
res[0] = res_len; // 商的长度
return 1;
}
4.2 大整数 / 大整数
大整数/大整数的情况，因为最终结果的商和余数都可能是大整数，所以必须转换为乘法和减法运算，最后不断循环得到结果。代码如下：
#include#include #include char s1[1005], s2[1005]; int n1[1005], n2[1005], ans[1005]; // 打印大整数格式的数组 void print_arr(int *arr, char *s) { printf("当前数组 %s：", s); for(int i = arr[0]; i > 0; i--) { printf("%d", arr[i]); } printf("n"); return ; } // 获得整数的长度 int get_len(int n) { if (n == 0) return 1; int len = 0; while(n) { n /= 10; len++; } return len; } // 交换两个数组 void swap_arr(int *n1, int *n2) { int max_len = n1[0] > n2[0] ? n1[0] : n2[0]; int temp; for (int i = 0; i <= max_len; i++) { temp = n2[i]; n2[i] = n1[i]; n1[i] = temp; } return ; } // 判断大整数a和b的大小 int get_big(int *a, int *b) { if (a[0] < b[0]) return 0; // a < b if (a[0] == b[0]) { for (int i = a[0]; i > 0; i--) { if (a[i] == b[i]) continue; if (a[i] > b[i]) return 1; if (a[i] < b[i]) return 0; } return 2; } return 1; // a > b } // 大整数减法运算 int big_sub(int *a, int *b, int *ans_ab) { //if (get_big(a, b) == 0) return -1; // 或者swap_arr(a, b); if (get_big(a, b) == 2) return 0; ans_ab[0] = a[0]; // 假设差值的长度就是较大数的长度 for (int i = 1; i <= a[0]; i++) { if (a[i] < b[i]) { a[i] += 10; a[i + 1] -= 1; } ans_ab[i] = a[i] - b[i]; // 减法运算 } int ans_len = ans_ab[0]; // 重新计算差值的长度 for (int i = ans_ab[0]; i > 0; i--) { if (ans_ab[i] == 0) ans_len--; if (ans_ab[i] != 0) break; } ans_ab[0] = ans_len; return 1; } // 大整数的乘法运算 int big_mul(int *a, int *b, int *ans_ab) { ans_ab[0] = a[0] + b[0] - 1; for (int i = 1; i <= a[0]; i++) { for (int j = 1; j <= b[0]; j++) { ans_ab[i + j - 1] += a[i] * b[j]; // 乘法运算 } } for(int i = 1; i <= ans_ab[0]; i++) { // 处理进位 if (ans_ab[i] > 9) { ans_ab[i + 1] += ans_ab[i] / 10; ans_ab[i] %= 10; if (i == ans_ab[0]) ans_ab[0]++; } } return 1; } // 每次计算得到差值之后，右移得到新的大整数，将要去除以除数 void big_move_right(int *a, int num) { if (a[0] == 0) { // 还没有数字的情况 a[0] = 1; a[1] = num; return ; } for(int i = a[0] + 1; i > 1; i--) { a[i] = a[i - 1]; } a[1] = num; a[0]++; // 第一位的长度加1 return ; } // 大整数除法: 大整数 a / 大整数 b，求val和mod值 int big_div_big(int *a, int *b, int *res, int *res_mod) { int _div[1005] = {0}; //被除数的中间结果(待除数), 除数为b int _res[1005] = {0}; // 商的中间结果 int _res_mul[1005] = {0}; // 商*除数的中间乘积结果 int _res_sub[1005] = {0}; // 被除数 - 乘积 的中间结果 int flag = 0; for (int i = a[0], j = 1; i > 0; i--, j++) { big_move_right(_div, a[i]); // 不断右移记录被除数 _div if (get_big(_div, b) == 0) { // 被除数 a < 除数b if (flag) res[0]++; continue; } for (int k = 9; k >= 1; k--) { _res[0] = 1; _res[1] = k; big_mul(_res, b, _res_mul); if (get_big(_res_mul, _div) == 1) { // 乘积值 大于 被除数 memset(_res_mul, 0, sizeof(_res_mul)); continue; } if (get_big(_res_mul, _div) == 2) { // 乘积值 等于 被除数 res[i] = k; flag = 1; res[0]++; memset(_div, 0, sizeof(_div)); memset(_res_mul, 0, sizeof(_res_mul)); break; } big_sub(_div, _res_mul, _res_sub); // 乘积值 小于 被除数 res[i] = k; flag = 1; res[0]++; memcpy(_div, _res_sub, sizeof(_res_sub)); // 把 差值 传给 被除数 memset(_res_mul, 0, sizeof(_res_mul)); // 对中间变量清零 memset(_res_sub, 0, sizeof(_res_sub)); break; } } memcpy(res_mod, _div, sizeof(_div)); return 1; } int main() { int res[1005] = {0}, res_mod[1005] = {0}; while (~scanf("%s%s", s1, s2)) { printf("nn1 = %s, n2 = %sn", s1, s2); // 格式转换 int n1_len = strlen(s1); int n2_len = strlen(s2); n1[0] = n1_len; n2[0] = n2_len; for (int i = 1, j = n1[0] - 1; i <= n1[0]; i++, j--) { n1[i] = s1[j] - '0'; } for (int i = 1, j = n2[0] - 1; i <= n2[0]; i++, j--) { n2[i] = s2[j] - '0'; } //1、 直接计算------------------ int x = 0, y = 0; for (int i = n1[0]; i > 0; i--) { x = x * 10 + n1[i]; } for (int i = n2[0]; i > 0; i--) { y = y * 10 + n2[i]; } printf("n直接除法：res = %d, mod = %dn", x/y, x%y); printf("-------------------------"); //2、 算法计算------------------- // 判断大小，两种特殊情况 int n1_n2_flag = get_big(n1, n2); // 判断大小，= 1, a>b; =2, a=b; =0, a 测试如下：
12345 22 n1 = 12345, n2 = 22 直接除法：res = 561, mod = 3 ------------------------- 算法求解：res = 561, mod = 3 1231561948156316163178 984698875613216 n1 = 1231561948156316163178, n2 = 984698875613216 直接除法：res = -2, mod = -22594390 ------------------------- 算法求解：res = 1250699, mod = 49125742525194 6578846156132313189784654894156164891651894832131 98651321871231894549465187455613218 n1 = 6578846156132313189784654894156164891651894832131, n2 = 98651321871231894549465187455613218 直接除法：res = 0, mod = -212964349 ------------------------- 算法求解：res = 66687866227677, mod = 94341467326046112764177507456197545可以看到，在常规数字的情况，算法都没问题，但是超出整型范围，long型便无法计算，而算法是可以的。
【参考】
(1条消息) 大数除法——超详细讲解_杨松赞的博客-CSDN博客_大数除法欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）