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

Question

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

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

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

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

Answer 1

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

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()，那么 BigNum_Add()和 BigNum_Sub() 可以按照 @user3386109 的建议通过检查符号并调用各种 BitB...() 来制作.

---

附带问题

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

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