Деление целых двоичных чисел

Если умножение сводится к последовательности сложений и сдвигов, то деление — к последовательности вычитаний и сдвигов. Операция реализуется циклическими действиями. Вначале делитель Y вычитается из делимого X, а затем из остатков А;.

При делении целых чисел получают целую часть частного и остаток W, как дополнительный результат (округление не производится)

Различают два алгоритма деления:

• ? с восстановлением остатка;
• ? без восстановления остатка.

Деление с восстановлением остатка

Получение цифры частного Z; включает в себя три действия:

1) вычитание X - Y, а затем Aj - Y.

По знаку остатка А, определяется цифра частного:

• 2) восстановление отрицательного остатка, т.е. А_; + Y;
• 3) сдвиг X(Aj) влево на один разряд. В последнем цикле сдвиг не производится!

Возможны два варианта деления: со сдвигом делимого X (остатков Aj) либо со сдвигом делителя Y. На практике часто используют первый вариант (рис. 4.66, а). Форматы операндов для него приведены на рис. 4.66, б.

Остаток W от деления размещается в старших разрядах регистра делимого.

Рис. 4.66. Деление со сдвигом делимого: а — схема деления; б — форматы данных и результата

Особенности деления

• 1. Частное получается, начиная со старших разрядов. Установку цифры частного производят путем выполнения операции INC Z (Z <— Z+ 1), При формировании следующей цифры частного Zj частное Z сдвигается влево на один разряд.
• 2. Перед началом деления X и Y сравниваются на наличие переполнения, которое имеет место, если старшая половина X больше делителя Y. Допустим, X = Ц 00₂ (12₁₀), Y = 10₂ (2₁₀). Поскольку Х_ст = 11₂ > 10₂, то будет переполнение. Действительно, в соответствии с рис. 4.66, б под целую часть частного отводится 2 разряда и результат Z = 110₂ (6₁₀) не размещается в отведенной разрядной сетке. Поскольку частное Z формируется, начиная со старшего разряда, то старшая цифра его будет потеряна и результат искажен. Схема алгоритма приведена на рис. 4.67.

Рис. 4.67. Схема алгоритма

Пример. Найти Z = X/Y, если X = 25 = 00011001₂, Y = 4 = 0100₂.

Примечание. Знак остатка А, удобно определять по значению флажка С:

Деление без восстановления остатка

Алгоритм такого деления сводится к следующим этапам:

1. Остаток Aj всегда удваивается.

Анализируется знак остатка (Sg А,), по которому определяется цифра частного

и выполняется одна из двух операций:

• а) вычитание (2А, - Y), если остаток положительный;
• б) сложение (-2А, + Y), если остаток отрицательный. Примечание. В последнем цикле вместо удвоения остатка его восстанавливают.

Пример. Выполнить деление тех же чисел (X = 25, Y = 4) без восстановления остатка со сдвигом делимого.