Почему сдвиг битов помогает умножать
В двоичной записи каждый разряд означает степень двойки: справа налево стоят 1, 2, 4, 8 и так далее. Поэтому сдвиг числа на один разряд влево добавляет справа ноль и удваивает его; сдвиг на два разряда умножает на четыре. Например, 1011₂ — это 11, а 10110₂ — 22.
Умножение можно разложить на сложение таких сдвинутых чисел. Возьмём 1011₂ и умножим на 101₂. Последнее число означает «одна единица плюс четыре», поэтому результат складывается из 1011 и 1011, сдвинутого влево на два разряда: 1011 + 101100 = 110111₂. Это 55 — произведение 11 и 5.
Что происходит внутри процессора
Каждый бит множителя подсказывает, добавлять ли очередную сдвинутую копию первого числа: при бите 1 — добавлять, при 0 — пропускать. Затем аппаратные схемы выполняют сложение и переносят разряд, если сумма в столбце превышает единицу. Так привычные десятичные таблицы умножения заменяются комбинацией простых операций с битами.
Это не значит, что любой процессор буквально делает один сдвиг и одно сложение за другим. В современных чипах специальные схемы могут формировать и складывать промежуточные результаты параллельно. Но принцип остаётся тем же: сдвиг задаёт вес каждого разряда, а сложение объединяет выбранные части произведения.
Сдвиг вправо обычно убирает младшие разряды и соответствует делению на степень двойки с округлением вниз для неотрицательных целых чисел. Поэтому он полезен не только в умножении: те же простые перемещения битов позволяют быстро делить целые числа на 2, 4 или 8.
