不使用二进制补码进行有符号二进制数的减法运算

Question

我试图编写代码来减去两个二进制数，但我不确定如何优雅地解决这个问题。存储二进制数的结构如下。

typedef struct _bitb {
    short bit;
    struct _bitb *nbit;
} BitB;
typedef struct _bignum {
    short sign;
    BitB *bits;
} BigNum;

因此，一个二进制数由一系列比特组成，包含其绝对值，从最低有效位（LSB）到最高有效位（MSB），然后是一个short类型的符号位，表示这个数是正还是负（它是任意精度算术的实现）。如果不使用二进制补码，如何计算两个二进制数之间的差异？

在有人问之前，我要说明这是用于学校的，但我不想要代码解决方案，只需要一般的算法，我可以自己实现。我已经搜索了很多资料，似乎没有一个好的算法可以解决一般情况。我需要检查这些数字的符号，然后为所有可能的情况编写代码吗（负减正，正减负，正减正，负减负）？或者是否应该转换为二进制补码？

- chilliefiber

---

你可以同时遍历这两个列表并逐位处理。你可以为减法制作一个真值表，输出2位（差和借位）。在每一步中，你会得到一个差异位和一个借位。差异位可以存储在第三个链表（结果）中，而借位可以在下一次迭代中使用。 - Ajay Brahmakshatriya

@AjayBrahmakshatriya 我认为这个方法只适用于从正数中减去另一个正数，我没错吧？ - chilliefiber

有符号数之间的不同操作本质上是加法或减法。加法你已经知道如何做了，就像我说的那样，减法只需要计算适当的符号并附加它。 - Ajay Brahmakshatriya

在|A| < |B|的情况下，您需要使用二进制补码来计算A-B。例如，如果A = 2且B = 5，则A-B将为-3，您需要对结果进行二进制补码运算，即-(5-3)。因此，不确定如何避免使用二进制补码。 - Rishikesh Raje

Answer 1

这是给学校作业用的，但我不想要代码解决方案，只需要一般性的算法，可以让我自己实现。

BigNum 是一个整数的符号-幅值链表编码。

为了对BigNum进行加/减运算，需要编写代码来处理每个BitB操作数的幅度的加/减。

为了进行幅度的加法，足以遍历BitB链表并随着遍历逐步形成和。

// pseudo-code
BitB *BitBAdd(const BitB *a, const BitB *b) {
  BitB temp_head = set next member to NULL
  BitB *bit_walker = pointer to the head
  bool carry = false;
  while (a is not end of list, b not end of list, or carry) {
    bool abit = get bit from a if not NULL and advance a, else 0
    bool bbit = get bit from b if not NULL and advance b, else 0
    bit_walker->nbit =  malloc(sizeof *(bit_walker->nbit));
    check allocation success
    advance bit_walker
    set bit_walker->nbit members to NULL, abit ^ bbit ^ carry
    carry = majority(abit, bbit, carry);
  }
  return temp_head.nbit;
}

减法需要先找到较大的数：int BitBCmp(const BitB *a, const BitB *b)，不显示代码。然后减法函数BitB *BitBCmp(const BitB *larger, const BitB *smaller)与BitBAdd()类似。不显示。

一旦完成了BitBAdd()、BitBCmp()和BitBSub()，则可以通过检查符号并调用 various BitB...()来制作BigNum_Add()和BigNum_Sub()，如@user3386109所建议。

---

附带问题 BitBAdd()代表实现OP任务所需代码的约20-25％。

可能需要去除最高位零位。还要考虑符号大小编码可能产生+0和-0。

- chux - Reinstate Monica

Answer 2

您可以将问题简化为两种情况：异号和同号。

减去具有相反符号的数字需要将两个绝对值相加。例如：

(-7) - (+5) = -(7+5)
(+7) - (-5) = +(7+5)

如果要减去符号相同的数字，则需要从较大的绝对值中减去较小的绝对值。例如：

(+7) - (+5) = +(7-5)
(+7) - (+9) = -(9-7)
(-7) - (-5) = -(7-5)
(-7) - (-9) = +(9-7)

正如你所看到的，实际上有六种情况可以表示结果的符号，如下所示（其中X、Y和Z是数字的大小）。

(-X) - (+Y) ==> -(Z)
(+X) - (-Y) ==> +(Z)
(+X) - (+Y) and (X >= Y) ==> +(Z)
(+X) - (+Y) and (X <  Y) ==> -(Z)
(-X) - (-Y) and (X >  Y) ==> -(Z)
(-X) - (-Y) and (X <= Y) ==> +(Z)

总结：

如果两个数的符号相反，则将它们的绝对值相加。
如果两个数的符号相同，则从较大的绝对值中减去较小的绝对值。
然后确定结果的符号。

- user3386109

Answer 3

在进行A-B运算时，如果|A| < |B|，你需要使用2的补码。例如，若A = 2且B = 5，A-B将得到-3。然后你需要对结果取2的补码，即-(5-3)。无论何种情况，都要使用2的补码。

我建议你使用2的补码将减法转换为加法。

也就是说，如果你有ans = A-B，那么你需要先对B取2的补码，然后再相加。

这样你就可以得到ans = A + (-B)。

步骤1. 取B的2的补码。

步骤2. 将A与2的补码相加。

这将大大简化代码。

此外，这就是CPU内部处理数字减法的方法。

- Rishikesh Raje