Двоичное умножение

Умножение – это быстрый способ сложения нескольких одинаковых чисел. При умножении одного числа на другое одно число называется множимым, другое - множителем. Умножение выполняется поразрядно. Часто возникает необходимость переноса в следующий по старшинству разряд. По завершению умножения множимого на значение младшего разряда множителя получается первое частичное произведение. В результате умножения множимого на значение следующего по старшинству разряда множителя формируется второе частичное произведение.

Подобная процедура повторяется необходимое число раз. Для получения результирующего произведения, смещенные относительно друг друга частичные произведения складываются с учетом переноса.

Рассмотрим пример:

17	множитель
*
12	множимое
34	первое частичное произведение
17	второе частичное произведение
100	перенос
204	результирующее произведение

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

В двоичной форме:

0001 0001	множимое 1710
*
0000 1100	множитель 1210
0000 0000	первое частичное произведение
0000 0000	второе
0001 0001
0001 0001
0000 0000
0000 0000
0000 0000
0000 0000	восьмое частичное произведение
000 0000 0000 0000	перенос
0000 0000 1100 1100	результат 20410

Перенос всегда будет равен 0, т.к. при умножении двоичных цифр его не возникает. Итак, получено восемь частичных произведений, поскольку множитель состоит из 8 разрядов. Третье частичное произведение - копия множимого, только оно сдвинуто относительно множимого на два двоичных разряда, поскольку для получения этого частичного произведения в качестве множителя используется значение третьего разряда, равного 1. Аналогично четвертое частичное произведение. Остальные равны нулям, как и соответствующие им разряды множителя. Сложение всех частичных произведений и дает конечный результат.

Создан способ выполнения двоичного умножения, получивший название умножения путем сдвига и сложения. Перечислим основные правила этого способа:

1. Формирование первого частичного произведения. Если значение младшего разряда множителя равно 0, то и результат равен 0, если значение этого разряда равно 1, то результат является копией множимого.

2. Правило сдвига. При использовании очередного разряда множителя для формирования частичного произведения производится сдвиг множимого на один разряд влево.

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

4. Определение результирующего произведения. Искомое произведение есть результат выполнения всех операций сдвига и сложения.

Попробуем применить правило к нашему примеру:

00010001

*

00001100

00010001

+

00010001

000110011

Подобный метод возможен лишь благодаря тому, что при умножении двоичного числа на 0 получается 0, а результат умножения двоичного числа на 1 есть само это число.