减去没有二进制补码的有符号二进制数

Question

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

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

因此，二进制数由包含其绝对值的位列表表示，从 LSB 到 MSB，然后是表示数字是正数还是负数的短字符（它是任意精度算术的实现） .如何在没有二进制补码的情况下从一个数字中减去另一个数字？

在有人问之前，这是为学校准备的，但我不想要代码中的解决方案，只想要一个我可以实现的通用算法。我一直在四处寻找，似乎没有一个好的算法可以解决一般情况。我是否需要检查数字的符号，然后为所有可能的情况（负负正、正负负、正负正、负负正）实现代码？或者我应该只转换为 2 的补码？

Answer 1

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

符号相反的数相减需要将两个绝对值相加。示例：

(-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)

总结：

如果两个数的符号相反，则相加。
如果两个数的符号相同，则用较大的数减去较小的数。
然后判断结果的符号。

Answer 2

this is for school, but I don't want a solution in code, just a general algorithm that I can implement

BigNum是整数的符号量级链表编码。

到add/subtractBigNum，需要对每个BitB操作数的大小add/subtract进行编码。

要增加量级，只需遍历 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() 被创建，那么 BigNum_Add() 和 BigNum_Sub() 可以通过检查符号并调用各种 BitB...() 根据 .

的建议

附带问题

BitBAdd() 代表完成 OP 任务所需代码的大约 20-25%。

可能需要去掉最重要的零位。还要考虑符号幅度编码可以生成 +0 和 -0。

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)。

第一步.取B的2的补码

第 2 步。将 A 与 2 的补码相加。

这将在很大程度上简化代码。

此外，这就是 CPU.

中处理数字减法的方式

减去没有二进制补码的有符号二进制数

Subtracting signed binary numbers without two's complement

c

binary

arbitrary-precision