Сб. Дек 7th, 2024

Перейдем к описанию «быстрого» алгоритма сложения, который в общем случае более эффективен, чем побитовое сложение с переносом двух двоичных k-разрядных чисел, эквивалентное сложению столбиком. «Быстрый» алгоритм использует такие элементарные операции как анализ четности числа, прибавление единицы, а также умножение и деление на 2.

Первые две из этих операций уже были рассмотрены. Умножение двоичного числа на 2 = 102, соответствует сдвигу его влево на один разряд, а целочисленное деление, наоборот, сдвигу вправо. «Лишние» разряды при сдвигах (например, самый правый разряд при сдвиге вправо) оказываются потерянными. Побитовые сдвиги чисел в компьютере также реализованы аппаратно.

В зависимости от четности двух чисел a и b справедливы следующие тождества:

  • a и b — четные: a + b = (a/2 + b/2)·2;
  • a и b — нечетные: a + b = ((a-1)/2 + (b-1)/2 + 1)·2;
  • a — четное и b — нечетное: a + b = (a/2 + (b-1)/2)·2 + 1;
  • a — нечетное и b — четное: a + b = ((a-1)/2 + b/2)·2 + 1.
Заметим, что при этом операция (a-1)/2 для нечетного числа, как и a/2 — для четного, соответствует сдвигу двоичного представления числа а вправо на один разряд.

Например, пусть а = 1012. Сдвиг вправо а на один разряд даст результат 102. Сдвиг а — 1=1012 — 1=1002 на один разряд вправо также даст результат 102.

Обозначим операции (a-1)/2 и a/2 как a >> 1, а умножение a на 2 как a << 1 (что соответствует терминологии языка программирования С).

Тогда рекурсивный алгоритм сложения двух чисел Add(a,b) можно записать следующим образом:

  • если а = 0, то Add(a, b) = b; конец;
  • если b = 0, то Add(a, b) = а; конец;
  • а, b — четные: Add(a, b) = Add(a >> l, b >> l) << l; конец;
  • a, b — нечетные: Add(a, b) = Add(a >> l, b >> l + 1) << 1; конец;
  • а и b имеют различную четность: Add(a, b) = Add(a >> l, b >> l) << 1 + 1; конец.

От content