时间戳

首页 > 解决方案 > 减去没有二进制补码的有符号二进制数

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

问题描述

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

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

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

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

标签： cbinaryarbitrary-precision

解决方案

这是给学校的，但我不想要代码中的解决方案，只是我可以实现的通用算法

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()可以通过检查标志并按照@user3386109BitB...()的建议调用各种来进行。

附带问题

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

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

推荐阅读