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

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

为了解决大整数表示和运算过程中出现的溢出问题，可以使用二进制字符数组来存储大数。将大整数转换为二进制数，并将每个二进制位用字符'0'或'1'表示，从低位到高位存储到字符数组中。本文将使用这种方法实现大数的基本运算，包括加减乘除。

1. 数据结构定义

首先定义一个结构体来表示大数：

#define MAXLEN 1000

typedef struct {
    char digits[MAXLEN]; // 存储大数的字符数组
    int length; // 大数的位数
    int sign; // 大数的符号（1表示正数，-1表示负数）
} bignum;

2. 输入和输出函数

以下代码定义了大数的输入和输出函数：

2.1 输入函数 input(bignum *a)

void input(bignum *a) {
    char s[MAXLEN];
    scanf("%s", s);
    a->length = strlen(s);
    int i = 0, j = a->length - 1;
    if (s[0] == '-') {
        a->sign = -1;
        i++;
    } else {
        a->sign = 1;
    }
    // 翻转字符串，将低位存放在数组的低地址
    while (i < j) {
        char t = s[i];
        s[i] = s[j];
        s[j] = t;
        i++;
        j--;
    }
    // 将字符串复制到 digits 数组中
    for (i = 0; i < a->length; i++) {
        a->digits[i] = s[i];
    }
}

2.2 输出函数 output(bignum a)

void output(bignum a) {
    if (a.sign == -1) {
        printf("-");
    }
    int i;
    // 从高位到低位输出字符数组
    for (i = a.length - 1; i >= 0; i--) {
        printf("%c", a.digits[i]);
    }
    printf("\n");
}

3. 大数运算函数

以下代码定义了大数的加减乘除运算函数：

3.1 加法函数 add(bignum a, bignum b)

bignum add(bignum a, bignum b) {
    bignum c;
    int carry = 0, i, j;
    // 遍历两个大数的所有位数，直到进位为 0
    for (i = 0, j = 0; i < a.length || j < b.length || carry != 0; i++, j++) {
        int x = i < a.length ? a.digits[i] - '0' : 0;
        int y = j < b.length ? b.digits[j] - '0' : 0;
        int z = x + y + carry;
        carry = z / 10;
        c.digits[i] = z % 10 + '0';
    }
    c.length = i;
    c.sign = a.sign; // 保留加数的符号
    return c;
}

3.2 减法函数 sub(bignum a, bignum b)

bignum sub(bignum a, bignum b) {
    bignum c;
    int borrow = 0, i, j;
    // 遍历两个大数的所有位数，直到借位为 0
    for (i = 0, j = 0; i < a.length || j < b.length || borrow != 0; i++, j++) {
        int x = i < a.length ? a.digits[i] - '0' : 0;
        int y = j < b.length ? b.digits[j] - '0' : 0;
        int z = x - y - borrow;
        if (z < 0) {
            z += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        c.digits[i] = z + '0';
    }
    // 去除前导 0
    while (i > 1 && c.digits[i - 1] == '0') {
        i--;
    }
    c.length = i;
    c.sign = a.sign; // 保留被减数的符号
    return c;
}

3.3 乘法函数 mul(bignum a, bignum b)

bignum mul(bignum a, bignum b) {
    bignum c;
    int i, j;
    // 初始化结果数组，长度为两个大数长度之和
    for (i = 0; i < a.length + b.length; i++) {
        c.digits[i] = '0';
    }
    // 逐位相乘
    for (i = 0; i < a.length; i++) {
        int carry = 0;
        for (j = 0; j < b.length || carry != 0; j++) {
            int x = i + j < c.length ? c.digits[i + j] - '0' : 0;
            int y = j < b.length ? b.digits[j] - '0' : 0;
            int z = x + a.digits[i] * y + carry;
            carry = z / 10;
            c.digits[i + j] = z % 10 + '0';
        }
    }
    // 去除前导 0
    while (c.length > 1 && c.digits[c.length - 1] == '0') {
        c.length--;
    }
    c.sign = a.sign * b.sign; // 确定结果的符号
    return c;
}

3.4 除法函数 div(bignum a, bignum b)

bignum div(bignum a, bignum b) {
    bignum c;
    // 判断除数是否为 0
    if (b.length == 1 && b.digits[0] == '0') {
        printf("除数为 0！\n");
        exit(0);
    }
    c.length = a.length;
    int i;
    // 初始化结果数组
    for (i = 0; i < a.length; i++) {
        c.digits[i] = '0';
    }
    c.sign = a.sign * b.sign;
    // 将除数的符号置为 1
    b.sign = 1;
    // 逐位相除
    for (i = a.length - 1; i >= 0; i--) {
        c.digits[i] = '0';
        int j;
        // 尝试从 9 到 0 寻找商
        for (j = 9; j >= 0; j--) {
            bignum x = mul(b, int2big(j)); // 计算除数乘以当前商
            // 比较被除数和 (被除数 - 商 * 除数) 的大小
            if (compare(x, sub(a, mul(int2big(i), x))) <= 0) {
                c.digits[i] = j + '0';
                a = sub(a, mul(int2big(i), x)); // 更新被除数
                break;
            }
        }
    }
    // 去除前导 0
    while (c.length > 1 && c.digits[c.length - 1] == '0') {
        c.length--;
    }
    return c;
}

4. 辅助函数

4.1 将 int 类型整数转换为大数 int2big(int n)

bignum int2big(int n) {
    bignum c;
    if (n == 0) {
        c.digits[0] = '0';
        c.length = 1;
        c.sign = 1;
    } else {
        int i = 0;
        if (n < 0) {
            n = -n;
            c.sign = -1;
        } else {
            c.sign = 1;
        }
        while (n > 0) {
            c.digits[i++] = n % 10 + '0';
            n /= 10;
        }
        c.length = i;
    }
    return c;
}

4.2 比较两个大数的大小 compare(bignum a, bignum b)

int compare(bignum a, bignum b) {
    if (a.sign != b.sign) {
        return a.sign > b.sign ? 1 : -1;
    }
    if (a.length != b.length) {
        return a.length > b.length ? 1 : -1;
    }
    int i;
    for (i = a.length - 1; i >= 0; i--) {
        if (a.digits[i] != b.digits[i]) {
            return a.digits[i] > b.digits[i] ? 1 : -1;
        }
    }
    return 0; // 两个大数相等
}

总结

本文介绍了使用二进制字符数组表示大数的方法，并用C语言实现了大数的加减乘除等基本运算。代码包含详细注释，并提供完整的结构体定义和函数实现。通过本文，读者可以了解如何使用二进制字符数组来存储和操作大数，并为进一步的学习和应用提供参考。