Первая страница / Визуализаторы / Арифметика / Сложение двоичных чисел /

Описание алгоритма

Каскадное сложение

Неотрицательное число a записывается в двоичной системе как последовательность n битов: {a[n - 1], a[n - 2], …, a[0]}, причём n ≥ log(a + 1) и a = a[0] * 20 + a[1] * 21 + … + a[n - 1] * 2n - 1.

При сложении по двум n-значным числам a = {a[n - 1], a[n - 2], …, a[0]} и b = {b[n - 1], b[n - 2], …, b[0]} строится (n + 1)-значное число s = {s[n], s[n - 1], …, s[0]}, равное их сумме.

При сложении столбиком (справа налево) мы складываем в i-м разряде ai, bi и входной бит переноса (carry-in bit) ci. Младший разряд суммы записывается в i-й разряд ответа (si), а старший становится выходным битом переноса (carry-out bit) ci+1 и используется при сложении в следующем разряде. В младший разряд ничего не переносится, поэтому c0 = 0. Последний перенос cn становится старшим разрядом суммы sn. Поскольку si = parity(ai, bi, ci), а ci+1 = majority(ai, bi, ci), для каждого шага годится описанный выше сумматор.

Таким образом, n-разрядный каскадный сумматор состоит из последовательно соединённых простых сумматоров FA0, FA1, …, FAn - 1, так что выход ci+1 сумматора FAi является входом для FAi + 1. На входе c0 фиксировано значение 0, не зависящее от входов.

Поскольку бит переноса проходит через все сумматоры, глубина каскадного сумматора равна n (а глубина элемента FAi+1 равна i + 1). Поэтому время работы составляет O(n). Размер схемы равен O(n).

Сложение с предвычислением переносов

В каскадном сумматоре бит переноса ci вычисляется в момент времени i. Значения ai и bi, однако, известны с самого начала. В некоторых случаях они определяют бит переноса ci:

  • если ai = bi = 0, то ci = 0 (перенос "поглощается" (kill))
  • если ai = bi = 1, то ci = 1 (перенос "порождается" (generate))

Однако если один из битов ai и bi равен 1, а другой 0, то ci-1 существен; именно,

  • если ai != bi, то ci = ci-1 (перенос "распространяется" (propagate))

Каждому разряду, следовательно, соответствует один из трёх типов переноса (carry statuses): k (kill), g (generate) или p (propagate). Этот тип известен заранее, что позволяет уменьшить время работы схемы сложения.

Зная типы переноса для соседних сумматоров ((i - 1)-го и i-го), можно определить тип переноса для их соединения, считая ci-1 входным битом, а ci+1 — выходным: зная, что случается с битом переноса на каждом шаге, можно рассчитать, что произойдёт за два шага, то есть как зависит ci+1 от ci-1. Если i-й разряд имеет тип k или g, то соединение имеет тот же тип переноса. Если же i-й разряд имеет тип переноса p, то тип переноса для соединения совпадает с типом (i - 1)-го разряда.

Таким образом, вычисление битов переноса ci сводится к вычислению префиксов yi. Оставшиеся действия выполняются за время O(1): достаточно подать биты переноса на входы сумматоров.