Рассмотрим способность реализации в двоичной арифметике умножения. "Быстрый" вариант обыкновенного умножения был известен еще в Древнем Египте, его также называют "русским" или "крестьянским" методом.

Разберем пример такого умножения. Умножим 23 на 43 "русским методом".

23	×	43
46		21
92		10 (четное)
184		5
368		2 (четное)
736		1

Первый столбец состоит из результатов последовательного умножения первого сомножителя на 2, а второй - из результатов последовательного целочисленного деления второго сомножителя на 2. Далее суммируем числа первого столбца, рядом с которыми во втором столбце стоят нечетные числа.

Ответ: 23 х 43 = 23 + 46 + 184 + 736 = 989.

Такое умножение основано на следующих тождествах:

а - четное: а х b = a/2 × (b × 2) = (a/2 × b) × 2
а - нечетное: а х b = (a-1)/2 × (b × 2) + b = ((a-1)/2 × b) × 2 + b.

В результате получаем следующий рекурсивный алгоритм умножения целых двоичных чисел:

если a = 0, то Mult(a, b) = 0; конец;
a - четное: Mult(a, b) = Mult(a >> 1, b) << 1; конец;
a - нечетное: Mult(a, b) = Mult(a >> 1, b) << 1 + b; конец;

При реализации такого алгоритма в ограниченном числе разрядов к неверному результату могут привести операции сдвига влево (если старший разряд ненулевой) и сложения. В примере показаны ошибки, возникающие при работе в ограниченном числе разрядов.

Умножим в 8-разрядном беззнаковом типе 14 на 100:

14 = 1110₂ умножить на 100 = 1100100₂

Рекурсивный спуск:

Mult(1110,1100100) = Mult(111,100100) << 1;
Mult(111,1100100) = Mult(11,100100) << 1 + 1100100;
Mult(11,1100100) = Mult(1,100100) << 1 + 1100100.

Рекурсивный подъем:

Mult(1,100100) = 1100100.

Поскольку все вычисления проводятся в 8 разрядах, то получим:

Мult(11,1100100) = 11001000 + 1100100 = 00101100,

вместо 100101100, так как левая единица находится в 9-ом разряде, т.е. результат восьмиразрядной арифметики не совпал с результатом обычной арифметики

Mult(lll,1100100) = 1011000 + 1100100 = 10111100;
Mult(1110,1100100) = 10111100 << 1 = 11110002 = 120;

при сдвиге влево единица в старшем разряде исчезла.

Ответ: 14·100 = 120 (в 8-разрядной арифметике).

Заметим, что полученное число равно остатку от деления 14-100 = 1400 на 256 = 2⁸, то есть умножение произведено по модулю 256 = 2⁸.

Определим, при каких ограничениях умножение чисел в k-разрядах дает верный результат с точки зрения обычной арифметики.

Если оба множителя положительны или отрицательны, то их произведение должно быть меньше, чем 2^k - 1; (если оба числа а и b отрицательны, то с помощью дополнительного кода они записаны как 2^k - |a| и 2^k - |b| и их произведение равно:

(2^k - |a|)(2^k - |b|) = 2^2k - 2^k (|a| + |b|) + |a|·|b|,

что в k -разрядной арифметике соответствует просто |a|·|b|, так как остальные слагаемые выходят за пределы k разрядов);

Если множители имеют разный знак, например, а < 0, b > 0, то их произведение, можно представить как:

(2^k - |a|)|b| = 2^k|b| - |a|·|b|,

но в k разрядах это просто 2^k - |a|·|b|, т.е. дополнительный код числа -|a|·|b| и для получения правильного результата умножения достаточно, чтобы |a|·|b| ≤ 2^k-1.

Целочисленное деление с остатком в двоичной системе сводится к сравнению и вычитанию. Если как делимое так и делитель представимы в k-разрядном типе, то и результат деления и остаток от него будут получены правильно. Однако, если в делении участвуют отрицательные числа, то остаток компьютерного деления может не совпадать с математическим понятием остатка, и об этом следует помнить при программировании.