C 语言实现大整数加减取模运算

为了解决大整数的表示与运算溢出问题，我们可以将大整数先转换成二进制，再将二进制中的每一位（0 或 1），以'0' 或 '1' 字符的形式，从低到高位依次存放到一个字符数组中，称为大数的二进制字符数组表示。

本文将使用 C 语言实现两个大整数的“+”、“-” 与 “%” 等基本运算。下面是一个简单的实现，其中假设最大的大整数位数为 1000 位。

#include <stdio.h>
#include <string.h>

#define MAX_LEN 1000

// 将大整数转换成二进制字符数组
void toBinary(char* str, char* binary) {
    int i, j = 0;
    for (i = strlen(str) - 1; i >= 0; i--) {
        int num = str[i] - '0';
        int k;
        for (k = 0; k < 3; k++) {
            binary[j++] = (num % 2 == 0) ? '0' : '1';
            num /= 2;
        }
    }
    // 处理最高位
    while (j > 1 && binary[j - 1] == '0') j--;
    binary[j] = '\0';
    // 翻转字符串
    for (i = 0; i < j / 2; i++) {
        char temp = binary[i];
        binary[i] = binary[j - 1 - i];
        binary[j - 1 - i] = temp;
    }
}

// 将二进制字符数组转换成大整数
void toDecimal(char* binary, char* str) {
    int len = strlen(binary);
    int i, j = 0;
    for (i = len - 1; i >= 0; i -= 3) {
        int num = 0;
        int k;
        for (k = 0; k < 3; k++) {
            if (i - k >= 0) {
                num *= 2;
                num += (binary[i - k] == '1') ? 1 : 0;
            }
        }
        str[j++] = num + '0';
    }
    // 处理前导0
    while (j > 1 && str[j - 1] == '0') j--;
    str[j] = '\0';
    // 翻转字符串
    for (i = 0; i < j / 2; i++) {
        char temp = str[i];
        str[i] = str[j - 1 - i];
        str[j - 1 - i] = temp;
    }
}

// 二进制字符数组加法
void add(char* a, char* b, char* result) {
    int len1 = strlen(a);
    int len2 = strlen(b);
    int len = len1 > len2 ? len1 : len2;
    int carry = 0;
    int i;
    for (i = 0; i < len; i++) {
        int num1 = (i < len1) ? (a[len1 - 1 - i] - '0') : 0;
        int num2 = (i < len2) ? (b[len2 - 1 - i] - '0') : 0;
        int sum = num1 + num2 + carry;
        result[len - 1 - i] = (sum % 2 == 0) ? '0' : '1';
        carry = sum / 2;
    }
    result[len] = '\0';
    if (carry == 1) {
        // 处理进位
        for (i = len; i >= 1; i--) {
            result[i] = result[i - 1];
        }
        result[0] = '1';
    }
}

// 二进制字符数组减法
void subtract(char* a, char* b, char* result) {
    int len1 = strlen(a);
    int len2 = strlen(b);
    int len = len1 > len2 ? len1 : len2;
    int borrow = 0;
    int i;
    for (i = 0; i < len; i++) {
        int num1 = (i < len1) ? (a[len1 - 1 - i] - '0') : 0;
        int num2 = (i < len2) ? (b[len2 - 1 - i] - '0') : 0;
        int diff = num1 - num2 - borrow;
        if (diff < 0) {
            diff += 2;
            borrow = 1;
        } else {
            borrow = 0;
        }
        result[len - 1 - i] = (diff == 0) ? '0' : '1';
    }
    result[len] = '\0';
    // 处理前导0
    while (result[0] == '0' && result[1] != '\0') {
        int i;
        for (i = 0; i < len; i++) {
            result[i] = result[i + 1];
        }
    }
}

// 二进制字符数组取模
void mod(char* a, char* b, char* result) {
    int len1 = strlen(a);
    int len2 = strlen(b);
    char temp[MAX_LEN];
    int i;
    // 处理前导0
    while (a[0] == '0' && a[1] != '\0') {
        int i;
        for (i = 0; i < len1; i++) {
            a[i] = a[i + 1];
        }
    }
    while (b[0] == '0' && b[1] != '\0') {
        int i;
        for (i = 0; i < len2; i++) {
            b[i] = b[i + 1];
        }
    }
    // 比较a和b的大小
    int cmp = strcmp(a, b);
    if (cmp < 0) {
        // 如果a<b，则a mod b=a
        strcpy(result, a);
        return;
    } else if (cmp == 0) {
        // 如果a=b，则a mod b=0
        result[0] = '0';
        result[1] = '\0';
        return;
    }
    // 一般情况
    int j = 0;
    for (i = 0; i < len2; i++) {
        temp[j++] = a[i];
    }
    temp[j] = '\0';
    for (i = 0; i < len1 - len2 + 1; i++) {
        while (strcmp(temp, b) < 0 && i < len1 - len2) {
            temp[j++] = a[len2 + i];
            temp[j] = '\0';
            i++;
        }
        if (strcmp(temp, b) < 0) break;
        subtract(temp, b, temp);
    }
    strcpy(result, temp);
}

int main() {
    char a[MAX_LEN], b[MAX_LEN];
    char binary1[MAX_LEN * 3], binary2[MAX_LEN * 3];
    char result[MAX_LEN * 3];
    printf("请输入两个大整数：\n");
    scanf("%s%s", a, b);
    toBinary(a, binary1);
    toBinary(b, binary2);
    printf("a+b=");
    add(binary1, binary2, result);
    toDecimal(result, a);
    printf("%s\n", a);
    printf("a-b=");
    subtract(binary1, binary2, result);
    toDecimal(result, a);
    printf("%s\n", a);
    printf("a%%b=");
    mod(binary1, binary2, result);
    toDecimal(result, a);
    printf("%s\n", a);
    return 0;
}

代码说明:

toBinary 函数: 将十进制大整数转换为二进制字符数组。
- 循环遍历十进制大整数的每一位，并将每一位转换为 3 位二进制数。
- 将二进制数的每一位存放到字符数组中，并从低位到高位进行存储。
- 处理最高位，确保二进制字符数组没有前导零。
- 翻转字符串，将二进制字符数组转换为从高位到低位的存储顺序。
toDecimal 函数: 将二进制字符数组转换为十进制大整数。
- 循环遍历二进制字符数组，将每 3 位二进制数转换为十进制数。
- 将十进制数存放到字符数组中，并从低位到高位进行存储。
- 处理前导零，确保十进制大整数没有前导零。
- 翻转字符串，将十进制大整数转换为从高位到低位的存储顺序。
add 函数: 实现二进制字符数组加法。
- 从低位到高位依次计算每一位的和，并处理进位。
subtract 函数: 实现二进制字符数组减法。
- 从低位到高位依次计算每一位的差，并处理借位。
mod 函数: 实现二进制字符数组取模运算。
- 处理前导零，确保二进制字符数组没有前导零。
- 比较两个二进制字符数组的大小，如果 a < b，则 a mod b = a；如果 a = b，则 a mod b = 0。
- 使用循环进行减法操作，直到 a < b。

注意:

此代码假设最大的大整数位数为 1000 位，可以根据实际情况修改 MAX_LEN 的值。
该代码使用 3 位二进制数表示一个十进制数，可以根据实际情况调整。
该代码仅演示了基本操作，可以根据需要扩展其他功能。