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);
    }
}