Деление двоичных знаковых чисел в компьютерных системах - Компьютерная арифметика

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

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

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

Таким образом, при делении чисел в ДК трудности, связанные с коррекцией результата (как при умножении в дополнительном коде), практически отсутствуют.

Пусть:

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

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

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

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

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

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

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

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

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

Алгоритм деления целых двоичных знаковых чисел заключается в следующем:

    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

X > 0; Y > 0; Z > 0.

Необходимо разделить два знаковых числа:

Х = +21 - делимое;

Y = +7 - делитель;

Z = +3 - частное.

((+21) : (+7) = (+3)).

Для удобства возьмем длину разрядной сетки равную четырем битам, а именно: если (Z) и (Y) равняется четырем битам, то как было отмечено выше (X) должно быть восьмиразрядным значением, т. е длина разрядной сетки делимого в два раза больше делителя и частного. На первом шаге разрядная сетка делителя увеличивается на один разряд путем арифметического сдвига вправо. Далее, когда знаки делимого и делителя совпадают, то на втором шаге производится вычитание, когда знаки делимого и делителя не совпадают, то на втором шаге производится сложение. Затем анализируются знаковые биты частичного остатка и делителя, если они разные, то в частное записывается (0), если одинаковые, то в частное записывается (1). Далее анализируются знаки частичного остатка и делителя, если они разные, то после сдвига влево производится сложение частичного остатка с делителем, если одинаковые, то производится вычитание из частичного остатка делителя (или сложение с дополнительным кодом делителя).

Алгоритм деления приведен в табл. 4.10.

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

Регистр (В)

Делимое

X

Регистр (С)

Делитель

Y

Регистр (А)

Частное

Z

Счетчик тактов

(Сч. Т)

0

0

0

1

0

1

0

1

0

1

1

1

0

0

1

1

4

(-)

1

1

0

0

1

0

0

1

1

1

1

1

0

1

1

3

0

1

1

1

0

1

(+)

0

1

1

1

1

1

1

0

2

1

1

0

0

1

(+)

0

1

1

1

1

0

0

1

1

1

0

1

1

1

(-)

1

0

0

1

1

0

0

0

0

0

СТОП

Случай №2 X > 0; Y < 0; Z < 0.

Необходимо разделить два знаковых числа:

Х = +21 - делимое;

Y = -7 - делитель;

Z = -3 - частное.

((+21) : (-7) = (-3)).

В этом случае знаки делимого и делителя не совпадают, поэтому на втором шаге производится сложение делимого и отрицательного делителя, а также необходима коррекция частного, т. е. после получения частного к последнему биту частного необходимо прибавить (1).

Алгоритм деления приведен в табл. 4.11.

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

Регистр (В)

Делимое

X

Регистр (С)

Делитель

Y

Регистр (А)

Частное

Z

Счетчик тактов

(Сч. Т)

0

0

0

1

0

1

0

1

1

0

0

1

1

1

0

0

4

(+)

1

1

0

0

1

1

1

0

0

1

1

1

0

1

1

3

0

1

1

1

0

1

(-)

0

1

1

1

1

1

1

0

2

1

1

0

0

1

(-)

0

1

1

1

1

0

0

1

1

1

0

1

1

1

(+)

1

0

0

1

1

0

0

0

0

0

СТОП

Счетчик тактов равняется (0), деление окончено, но как было сказано выше, в частном мы получили псевдо частное (Z' = 1100). Для получения истинного частного (Z), необходимо выполнить коррекцию, т. е. к (Z' +1) и тогда получаем истинное значение частного: Z = 1101.

Случай №3 X < 0; Y > 0; Z < 0.

Необходимо разделить два знаковых числа:

Х = -21 - делимое;

Y = +7 - делитель;

Z = -3 - частное.

((-21) : (+7) = (-3)).

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

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

Алгоритм деления приведен в табл. 4.12.

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

Регистр (В)

Делимое

X

Регистр (С)

Делитель

Y

Регистр (А)

Частное

Z

Счетчик тактов

(Сч. Т)

1

1

1

0

1

0

1

1

0

1

1

1

1

1

0

1

4

(+)

0

1

1

1

1

0

0

1

1

1

1

0

1

1

0

0

3

1

0

0

0

1

1

(-)

1

0

0

1

1

0

0

0

1

2

0

0

1

1

1

(-)

1

0

0

1

1

1

0

0

1

1

0

0

1

(+)

0

1

1

1

1

0

0

0

0

0

СТОП

Счетчик тактов равняется (0), деление окончено и как было сказано выше, т. к. последний частичный остаток равен нулю, то мы сразу получили истинное значение частного Z = 1101 и корректировка не потребовалась.

Случай №4 X < 0; Y < 0; Z > 0.

Необходимо разделить два знаковых числа:

Х = -21 - делимое;

Y = -7 - делитель;

Z = +3 - частное.

((-21) : (-7) = (+3)).

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

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

Алгоритм деления приведен в табл. 4.13.

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

Регистр (В)

Делимое

X

Регистр (С)

Делитель

Y

Регистр (А)

Частное

Z

Счетчик тактов

(Сч. Т)

1

1

1

0

1

0

1

1

1

0

0

1

0

0

1

0

4

(-)

0

0

1

1

1

1

1

0

0

1

1

0

0

1

0

0

3

1

0

0

0

1

1

(+)

1

0

0

1

1

0

0

0

1

2

0

0

1

1

1

(+)

1

0

0

1

1

1

0

0

1

1

0

0

1

(-)

0

1

1

1

1

0

0

0

0

0

СТОП

Счетчик тактов равняется (0), деление окончено в частном мы получили псевдо частное (Z' = 0010) и как было сказано выше, если последний частичный остаток равен (0), то необходима коррекция частного, т. е. после получения частного к последнему биту частного необходимо прибавить (1) для получения истинного частного (Z), необходимо выполнить коррекцию, т. е. к (Z' +1) и тогда получаем истинное значение частного: Z = 0011.

Похожие статьи




Деление двоичных знаковых чисел в компьютерных системах - Компьютерная арифметика

Предыдущая | Следующая