Вычитание двоичных чисел со знаком без дополнения до двух

Поэтому я пытаюсь написать код для вычитания двух двоичных чисел, но я не уверен, как элегантно решить эту проблему. Структуры, которые содержат двоичные числа, следующие.

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

Таким образом, двоичное число представлено списком битов, содержащих его абсолютное значение, от LSB до MSB, а затем короткое число, указывающее, является ли число положительным или отрицательным (это реализация арифметики произвольной точности). Как я могу вычесть одно число из другого без дополнения до двух?

И прежде чем кто-то спросит, это для школы, но я не хочу решения в коде, просто общий алгоритм, который я могу реализовать. Я искал вокруг, и кажется, что нет хорошего алгоритма, который мог бы решить общий случай. Нужно ли проверять знаки чисел, а затем вводить код для всех возможных случаев (отрицательный минус положительный, положительный минус отрицательный, положительный минус положительный, отрицательный минус положительный)? Или я должен просто преобразовать в дополнение 2?

Источник

3 ответа

Решение

Вы можете свести проблему к двум случаям: противоположные знаки и одинаковые знаки.

Вычитание чисел с противоположными знаками требует сложения двух абсолютных значений. Примеры:

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

В итоге:

Если два числа имеют противоположные знаки, то прибавьте величины.
Если два числа имеют одинаковый знак, то вычтите меньшую величину из большей.
Затем определите знак результата.

Источник

это для школы, но я не хочу решения в коде, просто общий алгоритм, который я могу реализовать

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() может быть сделано путем изучения знаков и вызова различных BitB...() как предложено @ user3386109.

Побочные вопросы

BitBAdd() представляет около 20-25% кода, необходимого для выполнения задачи ОП.

Может потребоваться отсечение наиболее значимых нулевых цифр. Также учтите, что кодирование величины знака может генерировать +0 и -0.

Источник

Вам понадобится 2 дополнения в случае A-B где |A| < |B|, например, если A = 2а также B = 5, A-B будет -3 Вы должны будете принять 2-е дополнение к результату. -(5-3), Вы должны использовать 2 дополнения в любом случае.

Я бы посоветовал вам использовать дополнение 2 для преобразования вычитания в дополнение.

т.е. если у вас есть ans = A-B принять 2-е дополнение B а затем добавить.

Вы получите ans = A + (-B),

Шаг 1. Возьмите 2 дополнения B

Шаг 2. Добавьте А с дополнением 2.

Это значительно упростит код.

Кроме того, это то, как вычитание чисел обрабатывается внутри процессора.

Источник
Другие вопросы по тегам