写一个C语言处理BigInteger数的函数
时间: 2024-05-11 20:16:33 浏览: 134
计算大整数的c语言程序
好的,下面是一个处理BigInteger数的C语言函数:
```c
#include <stdio.h>
#include <string.h>
#define SIZE 1000
// 将字符串转为大整数
void str_to_bigint(char* str, int len, int* bigint) {
for (int i = 0; i < len; i++) {
bigint[len - i - 1] = str[i] - '0';
}
}
// 将大整数转为字符串
void bigint_to_str(int* bigint, int len, char* str) {
for (int i = 0; i < len; i++) {
str[i] = bigint[len - i - 1] + '0';
}
str[len] = '\0';
}
// 大整数相加
void bigint_add(int* a, int* b, int* c, int len_a, int len_b, int* len_c) {
memset(c, 0, sizeof(int) * SIZE);
int carry = 0, i;
for (i = 0; i < len_a && i < len_b; i++) {
int tmp = a[i] + b[i] + carry;
c[i] = tmp % 10;
carry = tmp / 10;
}
while (i < len_a) {
int tmp = a[i] + carry;
c[i] = tmp % 10;
carry = tmp / 10;
i++;
}
while (i < len_b) {
int tmp = b[i] + carry;
c[i] = tmp % 10;
carry = tmp / 10;
i++;
}
if (carry) {
c[i] = carry;
i++;
}
*len_c = i;
}
// 大整数相减
void bigint_sub(int* a, int* b, int* c, int len_a, int len_b, int* len_c) {
memset(c, 0, sizeof(int) * SIZE);
int borrow = 0, i;
for (i = 0; i < len_a && i < len_b; i++) {
int tmp = a[i] - b[i] - borrow;
if (tmp < 0) {
tmp += 10;
borrow = 1;
} else {
borrow = 0;
}
c[i] = tmp;
}
while (i < len_a) {
int tmp = a[i] - borrow;
if (tmp < 0) {
tmp += 10;
borrow = 1;
} else {
borrow = 0;
}
c[i] = tmp;
i++;
}
*len_c = i;
while (*len_c > 1 && c[*len_c - 1] == 0) {
(*len_c)--;
}
}
// 大整数相乘
void bigint_mul(int* a, int* b, int* c, int len_a, int len_b, int* len_c) {
memset(c, 0, sizeof(int) * SIZE);
for (int i = 0; i < len_b; i++) {
int carry = 0;
for (int j = 0; j < len_a; j++) {
int tmp = a[j] * b[i] + c[i+j] + carry;
c[i+j] = tmp % 10;
carry = tmp / 10;
}
c[i+len_a] += carry;
}
*len_c = len_a + len_b;
while (*len_c > 1 && c[*len_c - 1] == 0) {
(*len_c)--;
}
}
// 大整数相除
void bigint_div(int* a, int* b, int* c, int len_a, int len_b, int* len_c) {
memset(c, 0, sizeof(int) * SIZE);
int tmp[SIZE], tmp_len = 0;
for (int i = 0; i < len_a; i++) {
tmp[tmp_len++] = a[len_a-i-1];
if (tmp_len == 1 && tmp[0] == 0) {
tmp_len--;
}
int j = tmp_len - 1;
while (j >= 0 && bigint_cmp(tmp, tmp_len, b, len_b) < 0) {
tmp[++j] = 0;
tmp_len++;
}
while (j >= 0) {
int r = bigint_divide(tmp, tmp_len, b, len_b);
c[i] += r;
for (int k = tmp_len - 1; k >= 0; k--) {
if (k > 0) {
tmp[k] = tmp[k-1];
} else {
tmp[k] = 0;
}
}
tmp_len--;
if (tmp_len > 0 && tmp[tmp_len - 1] == 0) {
tmp_len--;
}
j--;
}
}
*len_c = len_a;
while (*len_c > 1 && c[*len_c - 1] == 0) {
(*len_c)--;
}
}
// 比较两个大整数的大小,返回值小于0表示a<b,等于0表示a=b,大于0表示a>b
int bigint_cmp(int* a, int len_a, int* b, int len_b) {
while (len_a > 1 && a[len_a - 1] == 0) {
len_a--;
}
while (len_b > 1 && b[len_b - 1] == 0) {
len_b--;
}
if (len_a < len_b) {
return -1;
} else if (len_a > len_b) {
return 1;
} else {
for (int i = len_a - 1; i >= 0; i--) {
if (a[i] < b[i]) {
return -1;
} else if (a[i] > b[i]) {
return 1;
}
}
return 0;
}
}
// 用大整数b除以大整数a,返回余数
int bigint_divide(int* a, int len_a, int* b, int len_b) {
int l = 0, r = 10;
while (l < r) {
int mid = (l + r + 1) / 2;
int ta[SIZE], ta_len;
memset(ta, 0, sizeof(int) * SIZE);
ta[0] = mid;
bigint_mul(ta, a, ta, 1, len_a, &ta_len);
if (bigint_cmp(ta, ta_len, b, len_b) <= 0) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
int main() {
char str_a[SIZE], str_b[SIZE];
int bigint_a[SIZE], bigint_b[SIZE], bigint_c[SIZE], len_a, len_b, len_c;
// 输入两个字符串表示的大整数
printf("Please input integer a:");
scanf("%s", str_a);
len_a = strlen(str_a);
str_to_bigint(str_a, len_a, bigint_a);
printf("Please input integer b:");
scanf("%s", str_b);
len_b = strlen(str_b);
str_to_bigint(str_b, len_b, bigint_b);
// 大整数加法
bigint_add(bigint_a, bigint_b, bigint_c, len_a, len_b, &len_c);
char str_c[SIZE];
bigint_to_str(bigint_c, len_c, str_c);
printf("a + b = %s\n", str_c);
// 大整数减法
bigint_sub(bigint_a, bigint_b, bigint_c, len_a, len_b, &len_c);
bigint_to_str(bigint_c, len_c, str_c);
printf("a - b = %s\n", str_c);
// 大整数乘法
bigint_mul(bigint_a, bigint_b, bigint_c, len_a, len_b, &len_c);
bigint_to_str(bigint_c, len_c, str_c);
printf("a * b = %s\n", str_c);
// 大整数除法
bigint_div(bigint_b, bigint_a, bigint_c, len_b, len_a, &len_c);
bigint_to_str(bigint_c, len_c, str_c);
printf("b / a = %s\n", str_c);
return 0;
}
```
这个函数可以处理大于long long所能表示的整数,通过字符串转为大整数的方式进行计算,支持加、减、乘、除等操作。
阅读全文