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

Answer 4

这是我在 C 中对 LARGE_INTEGER 进行加减的方法。C++ 中没有函数可以执行此操作。

#define LP LowPart
#define HP HighPart
#define DW DWORD
#define DWV  4294967296.0

double Add(LARGE_INTEGER a, LARGE_INTEGER b) // Add b to a
{  int n = 0;
    double sum;
   LARGE_INTEGER ans;

   double low = a.LP + b.LP;
   double hi  = a.LP + b.LP;
   if (low > DWV)
   {  low -= DWV;
      hi++;
   }
   if (hi > DWV)
   {  hi -= DWV;
      n++;
   }
   sum = low + DWV * hi + n * DWV * DWV;
   ans.LP = (DW)low;
   ans.HP = (DW)hi;
   // Not sure how to handle overflow for LARGE_INTEGER
   return sum;
}
//------------------------------------------------------------------------
double Subtract(LARGE_INTEGER a, LARGE_INTEGER b) // Subtract b from a
{  double n, dif;
   LARGE_INTEGER ans;

   n = (double)a.HP - (double)b.HP;
   dif = (double)a.LP - (double)b.LP;  // Difference (could be -)
   if (n > 0.0)
   {  if (dif < 0.0)
      {  dif += DWV;
         n--;
      }
   }
   else if (n < 0.0)
   {  if (dif > 0.0)
      {  dif -= DWV;
         n++;
      }
   }
   if (n >= 0.0)
   {  ans.HP = (DW)n;
      ans.LP = (DW)dif;
   }
   // Not sure how t represent negative number in LARGE_INTEGER
   if (n != 0.0)
      dif += n * DWV;
   return dif;
}