Операция сложения двух целых чисел

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

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

В зависимости от четности двух чисел 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.

Например, пусть а = 101₂. Сдвиг вправо а на один разряд даст результат 10₂. Сдвиг а — 1=101₂ — 1=100₂ на один разряд вправо также даст результат 10₂.

Обозначим операции (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; конец.