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

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

0 голосов
/ 24 октября 2018

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

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

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

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

Ответы [ 3 ]

0 голосов
/ 24 октября 2018

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

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% кода, необходимого для выполнения задачи OP.

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

0 голосов
/ 24 октября 2018

Вам понадобится 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. Добавьте A с дополнением к 2.

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

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

0 голосов
/ 24 октября 2018

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

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

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

В итоге:

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

...