Деление чисел

Алгоритмы деления двоичных чисел

Рассмотрим алгоритмы операции деления целых положительных двоичных чисел на , где А – 2п-разрядное делимое; В – и-разрядный делитель; . Полагаем, что частное является целым от-разрядным числом , при этом

Алгоритм деления с восстановлением остатка. Значения разрядов частногоопределяются в результате анализа остатков, полученных после вычитания делителя В на первом шаге алгоритма из старших разрядов делимого Дст, а на последующих шагах – из старших разрядов текущего остатка.

При положительном и пулевом значениях остатка разряд частного ck = 1. В этом случае для получения следующего остатка текущий остаток сдвигается на один разряд влево и из него вычитается делитель В.

При отрицательном значении остатка текущий разряд частного ck = 0. Возникает тупиковая ситуация. Для выхода из нее восстанавливается предыдущий остаток путем прибавления делителя В к отрицательному остатку. Восстановленный остаток сдвигается на один разряд влево и из него вычитается делитель В. Операции восстановления и сдвига позволяют увеличить предыдущий остаток в два раза и продолжить операцию деления.

Пример 2.30. Проиллюстрируем алгоритм с восстановлением остатка для случая п = 3, когда делимое А = 100011 (35|0), делитель В = 111 (710). Для вычитания делителя В воспользуемся операцией алгебраического сложения в дополнительном коде. Отрицательное значение делителя в дополнительном коде (~В) = 1001. Для выполнения операции деления введем дополнительные знаковые разряды, которые выделим жирным шрифтом. Последовательность действий при делении представлена ниже, на рис. 2.17.

Алгоритм деления двоичных чисел с восстановлением остатка

Рис. 2.17. Алгоритм деления двоичных чисел с восстановлением остатка

Пример 2.31. При делении используются операции сложения и сдвига.

В результате деления получено частное С=0101, которое, по сути дела, представляет собой совокупность переносов, возникающих в результате операций сложения.

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

Пример 2.32. Алгоритм без восстановления остатка для тех же значений делителя и делимого аналогичен приведенному примеру 2.29 (рис. 2.18).

Алгоритм деления двоичных чисел без восстановления остатка

Рис. 2.18. Алгоритм деления двоичных чисел без восстановления остатка

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

 
< Пред   СОДЕРЖАНИЕ     След >