Пожалуйста, объясните мне решение проблемы ниже

Проблема:

Рассмотрим проблему добавления двух n-битовых двоичных целых чисел, хранящихся в двух массивах n-элементов A и B. Сумма двух целых чисел должна храниться в двоичной форме в массиве (n + 1) -элементов C. Задайте проблему формально и напишите псевдокод для добавления двух целых чисел.

Решение:

  • C ← [1... n + 1] ▹ C заполняется нулем.
  • для я ← 1 до n
  • do sum ← A [i] + B [i] + C [i]
  • C [i] ← сумма% 2
  • C [i + 1] ← сумма /2 ▹ Целочисленное деление.
  • вывод C

Вопрос:

  • Я думал, что C [i] есть A [i] + B [i], почему вы добавляете сумму на ← шаг [A] + B [i] + C [i] на шаге 3?
  • почему сумма% 2 (зачем нужно использовать modulo на шаге 4?)
  • зачем sum/2 (зачем нужно использовать деление на шаге 5?)

Не могли бы вы, пожалуйста, объяснить выше решение с реальным примером? Спасибо.

Ответы

Ответ 1

C - это и решение, и перенос. Для реального примера, пусть добавить 11 + 3. Я напишу в двоичном формате с десятичной в parens)

A = 1011 (11) + B = 0011 (3) [C starts as 00000 (0)]
       ^               ^                      ^

Знак отмечен первой позицией, и мы идем влево, так как читаем слева направо, но математика идет справа налево. Кроме того, мы делим целые числа, поэтому 3/2 = 1, а не 1.5. Теперь шаги.

1. sum = 1+1+0 = 10 (2), c[1] = 2 % 2 = 0, c[2] = 2/2 = 1
2. sum = 1+1+1 = 11 (3), c[2] = 3 % 2 = 1, c[3] = 3/2 = 1
3. sum = 0+0+1 = 01 (1), c[3] = 1 % 2 = 1, c[4] = 1/2 = 0
4. sum = 1+0+0 = 01 (1), c[4] = 1 % 2 = 1, c[5] = 1/2 = 0
^        ^ ^ ^                               ^
i        A B C, all at position i            note that we store the carry for the NEXT step

Результат: C = 01110 (14)

Ответ 2

  • Вы также добавляете C[i], потому что C[i] может содержать бит переноса, когда вы добавили A[i-1] + B[i-1] + C[i-1] в предыдущую итерацию. Например, если мы делаем 1 + 1, нашу первую итерацию sum = 1 + 1 + 0 = 2, но поскольку это двоичный код, мы должны перенести 1 и положить его на C[1] и поместить остаток (2 % 2 = 0) в C[0]. Это дает нам 10
  • C[i] получает сумму% 2, потому что сумма A[i] + B[i] + C[i] может быть больше 1, но 1 больше всего подходит для этой цифры. Остальная сумма (если она есть) будет помещена в бит переноса. И это подводит нас к...
  • C[i+1] получает sum / 2, потому что sum / 2 - это величина переноса. Он будет использоваться в следующей итерации, когда мы делаем A[i] + B[i] + C[i] для i = i + 1.

Ответ 3

Вы можете думать о добавлении двоичных чисел так же, как вы добавляете базовые 10 чисел: есть шаг "добавить" и "перенос" для выполнения каждой цифры.

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

101
+
011

На первом этапе мы начинаем с крайнего правого. (В вашем примере это соответствует я = 1). Добавим (1 + 1)% 2, что дает нам 0. Что здесь происходит? 1 + 1 - 2, который в двоичном выражении представляет собой двузначное число ( "10" ). Мы можем написать только младший разряд ( "0" ), поэтому выражение суммы "mod 2" на самом деле просто говорит "не беспокойтесь о сумме переноса на данный момент". Итак, у нас есть:

101
+
011
---
  0  (carrying a 1)

Теперь мы реализуем "переносить 1", выполняя целочисленное деление ( "sum/2" ) и временно сохраняя его:

101
+
011
---
 10

Теперь мы готовы добавить две цифры: (0 + 1)% 2 - но мы должны добавить в перенос 1, который мы отслеживаем, поэтому возьмем (0 + 1 + 1 )% 2 дает:

101
+
011
---
 00

Снова нам нужно отслеживать бит переноса, давая нам (0 + 1 + 1) = 1:

101
+
011
---
100

Наконец, добавим 3-й бит: (1 + 0 + 1)% 2, чтобы дать ответ:

 101
 +
 011
 ---
1000