C 语言实现大整数运算：二进制字符数组表示法

为了解决大整数的表示与运算溢出问题，可以使用二进制字符数组表示法。将大整数先转换成二进制，再把二进制中的每一位，0 或 1，以'0' 或 '1' 字符的形式，从低到高位依次存放到一个字符数组中，称为大数的二进制字符数组表示。本文将使用这种方法实现 2 个大整数的加减乘除等基本运算。

注意： 以下代码实现中，为了方便起见，采用了将字符数组中的每个字符转换成整型数的方式进行运算。实际上，如果需要更高的效率，可以采用类似于手算加减乘除的方式进行运算，不用将字符数组中的每个字符转换成整型数。

加法运算:

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

#define MAX_LEN 1000 // 定义最大字符数组长度

void add(char a[], char b[], char sum[]) {
    int i, j, k;
    int carry = 0; // 进位
    int len_a = strlen(a);
    int len_b = strlen(b);

    for (i = len_a - 1, j = len_b - 1, k = 0; i >= 0 || j >= 0 || carry; i--, j--, k++) {
        int x = (i >= 0 ? a[i] - '0' : 0); // 取出 a 数组当前位的数值，如果已经到了最高位，则用 0 补充
        int y = (j >= 0 ? b[j] - '0' : 0); // 取出 b 数组当前位的数值，如果已经到了最高位，则用 0 补充
        int z = x + y + carry; // 计算当前位的数值
        sum[k] = z % 10 + '0'; // 将当前位的数值存储到 sum 数组对应位置
        carry = z / 10; // 计算进位
    }

    sum[k] = '\0'; // 将 sum 数组最后一位赋为 '\0'，表示字符串结束
    strrev(sum); // 反转 sum 数组，使得最高位在前，最低位在后
}

减法运算:

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

#define MAX_LEN 1000 // 定义最大字符数组长度

void subtract(char a[], char b[], char diff[]) {
    int i, j, k;
    int borrow = 0; // 借位
    int len_a = strlen(a);
    int len_b = strlen(b);

    for (i = len_a - 1, j = len_b - 1, k = 0; i >= 0 || j >= 0; i--, j--, k++) {
        int x = (i >= 0 ? a[i] - '0' : 0); // 取出 a 数组当前位的数值，如果已经到了最高位，则用 0 补充
        int y = (j >= 0 ? b[j] - '0' : 0); // 取出 b 数组当前位的数值，如果已经到了最高位，则用 0 补充
        int z = x - y - borrow; // 计算当前位的数值
        if (z < 0) {
            z += 10; // 如果需要借位，则将当前位加上 10
            borrow = 1; // 设置借位标志
        } else {
            borrow = 0; // 清除借位标志
        }
        diff[k] = z + '0'; // 将当前位的数值存储到 diff 数组对应位置
    }

    while (k > 1 && diff[k - 1] == '0') k--; // 去掉 diff 数组中的前导零
    diff[k] = '\0'; // 将 diff 数组最后一位赋为 '\0'，表示字符串结束
    strrev(diff); // 反转 diff 数组，使得最高位在前，最低位在后
}

乘法运算:

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

#define MAX_LEN 1000 // 定义最大字符数组长度

void multiply(char a[], char b[], char product[]) {
    int i, j, k;
    int len_a = strlen(a);
    int len_b = strlen(b);
    int len_product = len_a + len_b; // 计算乘积的最大长度
    int carry;

    memset(product, '0', len_product); // 将 product 数组初始化为 '0'

    for (i = len_a - 1; i >= 0; i--) {
        carry = 0; // 初始化进位
        for (j = len_b - 1; j >= 0; j--) {
            int x = a[i] - '0'; // 取出 a 数组当前位的数值
            int y = b[j] - '0'; // 取出 b 数组当前位的数值
            int z = x * y + carry + product[i + j + 1] - '0'; // 计算当前位的乘积
            carry = z / 10; // 计算进位
            product[i + j + 1] = z % 10 + '0'; // 将当前位的数值存储到 product 数组对应位置
        }
        product[i + j + 1] = carry + '0'; // 将进位存储到 product 数组对应位置
    }

    while (*product == '0' && *(product + 1) != '\0') product++; // 去掉 product 数组中的前导零
}

除法运算:

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

#define MAX_LEN 1000 // 定义最大字符数组长度

void divide(char a[], char b[], char quotient[], char remainder[]) {
    int i, j, k;
    int len_a = strlen(a);
    int len_b = strlen(b);
    int len_quotient = len_a - len_b + 1;
    int len_remainder = len_b;
    int temp[MAX_LEN];
    int q, r; // 商和余数的当前位
    int carry;

    if (len_a < len_b) { // 如果被除数小于除数，直接将被除数赋值给余数，商为 0
        strcpy(remainder, a);
        quotient[0] = '0';
        quotient[1] = '\0';
        return;
    }

    for (i = len_a - 1; i >= 0; i--) {
        memset(temp, 0, sizeof(temp)); // 将 temp 数组初始化为 0
        carry = 0; // 初始化进位
        for (j = len_b - 1, k = len_b - 1; j >= 0; j--, k--) {
            int x = a[i] - '0'; // 取出 a 数组当前位的数值
            int y = b[j] - '0'; // 取出 b 数组当前位的数值
            int z = x * y + carry; // 计算当前位的乘积
            carry = z / 10; // 计算进位
            temp[k] = z % 10; // 将当前位的数值存储到 temp 数组对应位置
        }
        temp[k] = carry; // 将进位存储到 temp 数组对应位置

        q = 0; // 初始化商的当前位
        while (q < 10 && compare(temp, b, len_b) >= 0) { // 如果 temp 大于等于 b，则进行除法运算
            subtract(temp, b, temp);
            q++;
        }

        quotient[i - len_b + 1] = q + '0'; // 将商的当前位存储到 quotient 数组对应位置

        if (i >= len_b) {
            carry = a[i - len_b] - '0'; // 取出 a 数组当前位的数值
            for (j = len_b - 1; j >= 0; j--) {
                temp[j + 1] = temp[j]; // 将 temp 数组向左移动一位
            }
            temp[0] = carry; // 将 a 数组当前位存储到 temp 数组对应位置
        }
    }

    while (*quotient == '0' && *(quotient + 1) != '\0') quotient++; // 去掉 quotient 数组中的前导零
    strcpy(remainder, temp); // 将 temp 数组赋值给余数
}

比较两个整数的大小:

#include <string.h>

#define MAX_LEN 1000 // 定义最大字符数组长度

int compare(int a[], int b[], int len) {
    int i;
    for (i = 0; i < len; i++) {
        if (a[i] != b[i]) {
            return (a[i] > b[i]) ? 1 : -1;
        }
    }
    return 0;
}