C 中的大数减法

Question

大约 20 分钟前，我刚刚完成了 C 入门课程的考试。考试的第一题让我有些措手不及，涉及找出两个大数的差异。

目标是按值获取两个结构（N1 和 N2），并将差异存储在通过引用传递的结构（N3）中。我们被允许假设 N3 是用全“0”启动的。 MAX 大小可以是任何值，因此如果数字超过 100 位，该解决方案仍然有效。

这是基本代码（原始代码可能略有不同，这是从记忆中得出的）

#include <stdio.h>
#include <stdlib.h>
/* MAX can be any length, 10, 50, 100, etc */
#define MAX 10

struct bignum
{
    char digit[MAX];
    char decimaldigit[MAX/2];
};
typedef struct bignum bigNum;
void difference(bigNum, bigNum, bigNum *);

/*
    Original values in N1 and N2

    N1.digit = { '0', '0', '0', '5', '4', '8', '2', '0', '9', '0'};
    N1.decimaldigit { '0', '0', '0', '4', '9' };

    N2.digit = { '0', '0', '0', '4', '8', '1', '3', '1', '4', '5'};
    N2.decimaldigit { '8', '0', '1', '2', '0' };
*/

/*
    Result would be:
    N3.digit = { '0', '0', '0', '0', '6', '6', '8', '9', '4', '4'}
    N3.decimaldigit { '1', '9', '9', '2', '9' }
*/

问题不在于找到该问题的解决方案，而在于仅提供了大约 20 行来提供完整的答案。我的解决方法是在转换为整数后一次减去一位数字，然后如果结果为负则进行适当的进位。这比提供的空间占用了更多的空间。

基于少量的标记和为这个问题提供的空间，我相信有一个我没有看到的相当简单的解决方案。它是什么？我现在已经完成了课程，但这个问题仍然困扰着我！

不需要完整的解决方案，只需要函数 difference 的内部工作原理即可。

为了以防万一，不要使用按位运算符。

Answer 1

大多数计算机科学课程中的 BigNumber 问题旨在让您必须精确地按照您所描述的方式“手动”进行算术：将每个字符转换为整数，进行减法，并在适当的情况下借位。

正如您所描述的那样，您的计划攻击应该只有几行。在伪代码中，像这样：（

for each character (right to left):
    difference = N1.digit[i] - N2.digit[i];
    if (difference < 0)
        N1.digit[i - 1]--;
        difference += 10;
    N3.digit[i] = difference;

加上将相同的逻辑也应用于十进制数字的一些额外麻烦。）

听起来你有正确的想法，也许只是过度考虑了实现？

Answer 2

如果N1 >= N2，这应该有效。这还假设数组的布局类似于 dn...d2d1d0.e0e1...em。

char digchr(int); // Converts a single-digit integer into a character.

void difference(bigNum N1, bigNum N2, bigNum *N3) {
    int carry = 0;

    for (int i = MAX / 2 - 1; i >= 0; i--) {
        int diff = N1.decimalDigits[i] - N2.decimalDigits[i] - carry;
        if (diff < 0) { 
            diff += 10;
            carry = 1;
        } else {
            carry = 0;
        }

        N3->decimalDigits[i] = digchr(diff);
    }

    for (int i = 0; i < MAX; i++) {
        int diff = N1.digits[i] - N2.digits[i] - carry;
        if (diff < 0) {
           diff += 10;
           carry = 1;
        } else {
            carry = 0;
        }

        N3->digits[i] = digchr(diff);
    }
}

Answer 3

亲爱的教授，减法应该用加法来定义。我已经重载了一元“-”运算符并在其他地方定义了 bignum 加法例程。我正在使用 9 的补码 来简化/加速加法（不需要讨厌的进位！）使用基于表格的答案查找（当只有 10 个答案时为什么要计算总和？）。 bigNum 减法例程（根据您的规格）如下：

void bigDifference(bigNum N1, bigNum N2, bigNum *N3) {
    bigSum(N1, -N2, N3);
}