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

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

代码实现

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

#define MAX_DIGITS 1000 // 大数的最大位数

struct BigNum {
    char digits[MAX_DIGITS]; // 存放每一位数字的字符数组
    int sign; // 符号位，1 表示正数，-1 表示负数
};

// 将一个整数转换成大数的二进制字符数组表示
void intToBinary(int n, struct BigNum *b) {
    int i = 0;
    if (n < 0) {
        b->sign = -1;
        n = -n;
    } else {
        b->sign = 1;
    }
    while (n > 0) {
        b->digits[i++] = (n % 2) + '0';
        n /= 2;
    }
    while (i < MAX_DIGITS) {
        b->digits[i++] = '0';
    }
}

// 将一个大数的二进制字符数组表示转换成整数
int binaryToInt(struct BigNum *b) {
    int n = 0;
    for (int i = MAX_DIGITS - 1; i >= 0; i--) {
        n = n * 2 + (b->digits[i] - '0');
    }
    return b->sign * n;
}

// 将两个大数相加，结果存放在第一个大数中
void add(struct BigNum *a, struct BigNum *b) {
    if (a->sign == b->sign) {
        int carry = 0;
        for (int i = 0; i < MAX_DIGITS; i++) {
            int sum = a->digits[i] - '0' + b->digits[i] - '0' + carry;
            a->digits[i] = sum % 2 + '0';
            carry = sum / 2;
        }
    } else {
        subtract(a, b);
    }
}

// 将两个大数相减，结果存放在第一个大数中
void subtract(struct BigNum *a, struct BigNum *b) {
    if (a->sign == b->sign) {
        if (compare(a, b) < 0) {
            swap(a, b);
            a->sign = -a->sign;
        }
        int borrow = 0;
        for (int i = 0; i < MAX_DIGITS; i++) {
            int diff = a->digits[i] - '0' - (b->digits[i] - '0') - borrow;
            if (diff < 0) {
                diff += 2;
                borrow = 1;
            } else {
                borrow = 0;
            }
            a->digits[i] = diff + '0';
        }
    } else {
        add(a, b);
    }
}

// 将两个大数相乘，结果存放在第一个大数中
void multiply(struct BigNum *a, struct BigNum *b) {
    int sign = a->sign * b->sign;
    a->sign = b->sign = 1;
    struct BigNum c = { .digits = {0}, .sign = 1 };
    for (int i = 0; i < MAX_DIGITS; i++) {
        if (b->digits[i] == '1') {
            struct BigNum d = *a;
            for (int j = 0; j < i; j++) {
                leftShift(&d);
            }
            add(&c, &d);
        }
    }
    memcpy(a, &c, sizeof(struct BigNum));
    a->sign = sign;
}

// 将一个大数左移一位，相当于乘以 2
void leftShift(struct BigNum *b) {
    int carry = 0;
    for (int i = 0; i < MAX_DIGITS; i++) {
        int sum = (b->digits[i] - '0') * 2 + carry;
        b->digits[i] = sum % 10 + '0';
        carry = sum / 10;
    }
}

// 将两个大数相除，结果存放在第一个大数中，返回余数
int divide(struct BigNum *a, struct BigNum *b) {
    int sign = a->sign * b->sign;
    a->sign = b->sign = 1;
    struct BigNum c = { .digits = {0}, .sign = 1 };
    struct BigNum d = { .digits = {0}, .sign = 1 };
    for (int i = MAX_DIGITS - 1; i >= 0; i--) {
        leftShift(&c);
        c.digits[0] = a->digits[i];
        int x = 0, y = 1, z = 0;
        while (compare(&c, b) >= 0) {
            multiply(b, &d);
            while (compare(&c, &d) >= 0) {
                subtract(&c, &d);
                x += y;
                z++;
                leftShift(&d);
                y *= 2;
            }
            y /= 2;
            z--;
            rightShift(&d);
        }
        a->digits[i] = x + '0';
    }
    a->sign = sign;
    return binaryToInt(&c);
}

// 将一个大数右移一位，相当于除以 2
void rightShift(struct BigNum *b) {
    int carry = 0;
    for (int i = MAX_DIGITS - 1; i >= 0; i--) {
        int x = (b->digits[i] - '0') + carry * 10;
        b->digits[i] = x / 2 + '0';
        carry = x % 2;
    }
}

// 比较两个大数的大小，如果 a > b 返回 1，a < b 返回 -1，a = b 返回 0
int compare(struct BigNum *a, struct BigNum *b) {
    for (int i = MAX_DIGITS - 1; i >= 0; i--) {
        if (a->digits[i] > b->digits[i]) {
            return 1;
        } else if (a->digits[i] < b->digits[i]) {
            return -1;
        }
    }
    return 0;
}

// 交换两个大数
void swap(struct BigNum *a, struct BigNum *b) {
    struct BigNum temp = *a;
    *a = *b;
    *b = temp;
}

// 打印一个大数
void print(struct BigNum *b) {
    if (b->sign == -1) {
        putchar('-');
    }
    int i = MAX_DIGITS - 1;
    while (i >= 0 && b->digits[i] == '0') {
        i--;
    }
    if (i == -1) {
        putchar('0');
    } else {
        while (i >= 0) {
            putchar(b->digits[i--]);
        }
    }
    putchar('
');
}

int main() {
    struct BigNum a = { .digits = {0}, .sign = 1 };
    struct BigNum b = { .digits = {0}, .sign = 1 };
    int n = 123456789;
    int m = -987654321;
    intToBinary(n, &a);
    intToBinary(m, &b);
    print(&a);
    print(&b);
    add(&a, &b);
    print(&a);
    subtract(&a, &b);
    print(&a);
    multiply(&a, &b);
    print(&a);
    int q = divide(&a, &b);
    print(&a);
    printf("%d\n", q);
    return 0;
}

代码说明

结构体 BigNum: 用于表示大数，包含一个字符数组 digits 用于存储每一位数字的二进制表示，以及一个 sign 用于记录符号位。
函数 intToBinary: 将一个整数转换成大数的二进制字符数组表示。
函数 binaryToInt: 将一个大数的二进制字符数组表示转换成整数。
函数 add: 实现两个大数的加法运算，结果存放在第一个大数中。
函数 subtract: 实现两个大数的减法运算，结果存放在第一个大数中。
函数 multiply: 实现两个大数的乘法运算，结果存放在第一个大数中。
函数 divide: 实现两个大数的除法运算，结果存放在第一个大数中，返回余数。
函数 leftShift: 将一个大数左移一位，相当于乘以 2。
函数 rightShift: 将一个大数右移一位，相当于除以 2。
函数 compare: 比较两个大数的大小，如果 a > b 返回 1，a < b 返回 -1，a = b 返回 0。
函数 swap: 交换两个大数。
函数 print: 打印一个大数。

使用说明

在 main 函数中，我们首先定义了两个 BigNum 结构体 a 和 b，并分别将它们初始化为 123456789 和 -987654321。然后，我们使用 intToBinary 函数将这两个整数转换成二进制字符数组表示。最后，我们分别使用 add、subtract、multiply 和 divide 函数对 a 和 b 进行加减乘除运算，并将结果打印出来。

总结

本文介绍了如何使用 C 语言实现大数运算，并提供了完整的代码示例和详细的注释说明。这种方法可以有效地解决大整数的表示与运算溢出问题，并适用于各种需要处理大数的场景。