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

Размещено на http://www.allbest.ru/

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

Введение

Деление мантисс чисел в форме с фиксированной запятой выполняется над абсолютными величинами операндов, представленными, чаще всего, прямым кодом.

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

Как правило, формальным признаком окончания операции деления принимается количество сдвигов: при достижении числа сдвигов, равного количеству разрядов в частном, операция деления завершается.

1. Деление бззнаковых чисел

Обозначим X делимое, а Y -- делитель. Тогда частное

.

Пусть X, Y и Z являются беззнаковыми числами.

Операция деления характеризуется также дополнительным результатом R -- остатком.

В практической реализации выделяют два типа операции деления:

1) делимое, делитель и частное имеют одну и ту же длину s;

2) делимое имеет длину 2s -- удвоенную по сравнению с делителем и частным.

Рассмотрим случай 1.

,

,

,

, .

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

Или

.

В противном случае будет иметь место переполнение разрядной сетки.

Переполнение исключено, если делимое и делитель имеют одинаковую длину. Как особый случай переполнения рассматривают попытку деления на нуль.

По существу, деление сводится к последовательности вычитаний делителя вначале из делимого, а затем из остатков.

Цифра частного определяется следующим образом: если текущий остаток больше или равен делителю, цифра частного равна 1, если меньше, то цифра частного равна 0. При этом операция сравнения реализуется посредством операции вычитания.

Так как частное можно определить только со старших разрядов, существует два варианта деления (рисунок 1):

1) с неподвижным делимым (частичным остатком) и сдвигаемым вправо делителем;

2) с неподвижным делителем и сдвигаемым влево делимым (частичным остатком).

Рисунок 1 -- Схемы деления двоичных чисел

В зависимости от способа обработки отрицательного частичного остатка, различают два алгоритма деления -- с восстановлением и без восстановления остатка.

деление двоичное беззнаковое число остаток

2. Метод деления с восстановлением остатка

Если на очередном шаге получен положительный остаток, то в очередную цифру частного записывается 1, а остаток становится «предыдущим» для следующего шага. Данный шаг на этом заканчивается.

Если текущий остаток отрицателен, то в очередную цифру частного записывается 0, а к остатку прибавляется делитель для восстановления предыдущего, сдвинутого влево остатка, который становится «предыдущим» для следующего шага. Таким образом, отрицательный остаток аннулируется, поскольку он выполнил свою функцию сигнализатора о соотношении модулей остатка и делителя и больше не нужен.

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

1. Исходное значение частного Z полагается равным 0. СчТ присваивается значение s. Исходное значение частичного остатка R0 полагается равным s старшим разрядам делимого.

2. Выполняется пробное вычитание делителя Y из исходного значения ЧО. Положительная разность указывает на то, что частное превысит s-разрядную сетку, и будет выполнено прерывание. Если же результат вычитания отрицательный, то деление можно выполнять.

3. Восстанавливается исходное значение ЧО прибавлением делителя к полученному отрицательному остатку.

4. ЧО удваивается путем сдвига на один разряд влево.

5. Из ЧО вычитается делитель и анализируется знак результата вычитания: если остаток положительный, то очередная цифра частного равна 1, иначе -- 0.

6. Частное сдвигается влево с занесением очередной полученной цифры частного в освободившийся младший разряд. СчТ уменьшается на 1.

7. Если полученный остаток отрицателен, то восстанавливается предыдущий положительный остаток прибавлением делителя к отрицательному остатку.

8. Пп. 4-7 последовательно выполняются до получения всех цифр частного, пока СчТ не станет равным 0.

9. Если последний остаток от деления отрицателен, то восстанавливается предыдущий положительный остаток, который будет окончательным остатком от деления.

Недостатки:

1. Нерегулярность выполнения операций, что усложняет устройство управления (для получения одной цифры частного необходимо выполнять либо одно вычитание и сдвиг, либо одно вычитание, одно сложение и сдвиг);

2. Относительно малая скорость деления, т.к. в среднем половина шагов будет содержать операцию восстановления остатка: T=(s+l)(l,5t++tc)-tc.

2.2 Метод деления без восстановления остатка

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

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

Пусть

.

При этом, в соответствии с правилом деления, должны выполняться три действия:

1)восстановление предыдущего (сдвинутого влево) остатка:

;

2)сдвиг восстановленного остатка влево на один разряд:

;

3)вычитание модуля делителя из полученной кодовой комбинации:

.(1)

Таким образом, требуется перейти от текущего остатка

к последующему вида (1), избавившись от операции восстановления.

Если первым действием является сдвиг отрицательного остатка влево, то

.(2)

Правая часть (1) отличается от требуемого вида величиной |Y|. Поэтому вторым действием будет корректировка (2):

Сформулируем общее правило.

Чтобы определить цифру частного в некотором разряде, необходимо сдвинуть логически влево на один разряд, а затем прибавить к нему код делителя, которому приписывается знак, противоположный знаку предыдущего остатка; если полученный положительный, то в частном проставляется 1, если же отрицательный, -- то 0.

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

1-2.Аналогично п.п. 1, 2 предыдущего.

3.Аналогично п. 4.

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

5.Частное сдвигается; в младший разряд заносится очередная цифра частного (1 -- при положительном остатке, 0 -- при отрицательном);

6.П.п. 3-5 последовательно выполняются для получения всех цифр частного, пока СчТ не станет равен 0.

7.Аналогично последнему пункту предыдущего алгоритма.

Реализация данного алгоритма не требует никаких дополнительных аппаратурных затрат.

.

3. Деление целых двоичных знаковых чисел

Так как данные в памяти компьютера хранятся в ДК, операцию деления целесообразно выполнять в ДК.

За основу можно принять базовый алгоритм деления БВО, т.к. он предполагает использование отрицательного делителя, дополнительного кода для вычитания и учет знаков остатка и делителя на каждом шаге деления. Делимое участвует в операции только на первом шаге, а далее используются остатки, которые могут быть как положительными, так и отрицательными. Поэтому не имеет смысла рассматривать алгоритмы деления в ДК, где знаки операндов обрабатываются отдельно от их числовых частей. Таким образом, при делении чисел в ДК трудности, связанные с коррекцией результата (как при умножении в дополнительном коде), практически отсутствуют.

Пусть:

-- разрядность 2s,

-- разрядность s,

-- разрядность s,

-- разрядность s, .

Для проверки на корректность операции деления используется условие

.

Таким образом, при пробном вычитании делитель д.б. сдвинут на (s-1) разряд влево. Однако чтобы обеспечить регулярность процесса деления, делитель сдвигается влево на s разрядов, а перед пробным вычитанием делимое сдвигается на один разряд влево.

Деление целых двоичных чисел выполняется только методом БВО. В каждом цикле сдвинутый остаток складывается с делителем, которому приписывается знак, противоположный знаку частичного остатка.

Алгоритм деления знаковых чисел отличается от алгоритма деления беззнаковых чисел способом формирования разрядных цифр частного. Очередная цифра определяется на основе анализа знаков частичного остатка и делителя. Если знак полученного остатка совпадает со знаком делителя, то цифра частного равна 1, если нет -- 0. При этом частное формируется в прямом или обратном коде (в зависимости от соотношения знаков делимого и делителя).

На этапе пробного вычитания автоматически формируется старшая цифра частного, которая представляет его знак. Если знак полученного частичного остатка совпадает со знаком делителя, участвующего в операции пробного вычитания, деление является корректным. В противном случае имеет место переполнение РС.

3.1 Алгоритм деления целых двоичных знаковых чисел, представленных в дополнительном коде

1.Частному присваивается значение 0; СчТ -- s. Исходное значение частичного остатка равно s старшим разрядам делимого.

2.Частичный остаток удваивается сдвигом влево на 1 разряд, с занесением в младший разряд очередной цифры делимого.

3.Если частичный остаток и делитель разного знака, то они складываются, если же одного знака, то из частичного остатка вычитается делитель.

4.Частное сдвигается влево на 1 разряд. В освобождающийся младший разряд заносится очередная цифра частного: 1 -- если знак делителя и остатка совпадают, 0 -- в противном случае. СчТ уменьшается на 1.

5.Пункты 2-4 повторяются до тех пор, пока СчТ не станет равным 0.

6.Частное и остаток сформированы в обратном коде. Если знак окончательного остатка не совпадает со знаком делимого, то выполняется его восстановление. Для получения ДК результата выполняется его коррекция в зависимости от соотношения знаков делимого и делителя.

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

1)X > 0; Y > 0. Деление в этом случае ничем не отличается от деления положительных операндов в прямом коде. Коррекция не требуется;

2)X > 0; Y < 0. Этот случай легко сводится к обычному делению в прямом коде, если считать, что в наличии имеется -Y и +Y. Однако для формирования правильного знака частного и обратного кода отрицательного результата необходимо псевдознаковую цифру и цифры частного получать равными цифрам знаковых разрядов соответствующих остатков. Переполнение разрядной сетки здесь фиксируется по . В конце деления для образования дополнительного кода и округления частного следует прибавить единицу к младшему разряду: (Z=Z'+1);

3)X < 0; Y > 0. Из отрицательного делимого должен вычитаться положительный делитель, в отличие от деления без восстановления остатка в прямом коде, когда на первом шаге Х>0, Y<0. Поэтому псевдознаковая цифра частного , полученная по знаку нулевого остатка в соответствии с алгоритмом деления без восстановления остатка, здесь указывает на переполнение разрядной сетки. Если же переполнения разрядной сетки нет, эта цифра является правильной знаковой цифрой частного (то есть, ). Знаки всех других остатков в этом случае определяют инверсные значения цифр частного. В результате будет записан обратный код отрицательного частного. Для округления и получения дополнительного кода результата необходимо добавить единицу в младший разряд, если полученный остаток не равен нулю: (Z=Z'+1);

4)X < 0; Y < 0. На первом шаге алгоритма для формирования правильного знака частного () необходимо из отрицательного делимого вычитать отрицательный делитель ( соответствует переполнению разрядной сетки). Далее же этот случай сводится к третьему. Здесь все цифры частного, включая псевдознаковую, равны знакам остатков. В случае, когда полученный остаток равен нулю, к частному следует прибавить единицу (Z=Z'+1).

Свойства

1. При использовании методов с восстановлением остатка и без восстановления остатка сдвиг влево может вызвать передачу значащей цифры из старшего разряда остатка в знаковый, и остаток будет искажен. Поэтому надо оперировать двумя знаковыми разрядами. Правильный знак при этом находится в дополнительном ЗР, а единица в основном относится к разряду переполнения (в случае правильных дробей -- к разряду целых).

2. Знак остатка от деления должен совпадать со знаком делимого.

Размещено на Allbest.ru