3 Операция деления без восстановления остатка над целыми двоичными числами со знаком, представленными в дополнительном коде


Скачать 443.34 Kb.
Название3 Операция деления без восстановления остатка над целыми двоичными числами со знаком, представленными в дополнительном коде
страница1/3
Дата публикации19.07.2013
Размер443.34 Kb.
ТипДокументы
vb2.userdocs.ru > Военное дело > Документы
  1   2   3

Алгоритм деления 2n:n (целые числа со знаком в доп.коде)

3.2. Операция деления без восстановления остатка над целыми двоичными числами со знаком, представленными в дополнительном коде
3.2.1. Алгоритм деления 2n : n

Напомним реализацию операции деления на ассемблере i8086 для целых двоичных чисел со знаком, представленных в дополнительном коде словарной длины.

При выполнении этой операции используются две команды CWD (команда знакового расширения слова до двойной длины) и IDIV(собственно команда деления) в следующей последовательности:

cwd;

idiv word ptr [r/m]; где word ptr [r/m] определяет адрес источника

; (r – регистр / m – ячейка памяти), где хранится 16-разрядный делитель.

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

Команда CWD обеспечивает преобразование слова в двойное слово


Код

операции


Команда

Число

тактовых

циклов

Описание

98

CWD

3

DX <- расширение знаком AX

Начиная с i80386 команда cwd заменена на команду cmde:

98

CWDE

3(i486)

EAX<- расширение знаком AX

Правила выполнения команды cwd

DX < SignExtend(AX) (расширением знаком);

Описание

Команда CWD преобразовывает имеющее знак в регистре AX слово в имеющее знак двойное слово в регистрах DX:AX путем расширения старшего бита регистра AX (бита знака) на два байта регистра DX.

Команда IDIV Деление со знаком

Код

операции


Команда

Число

тактовых

циклов

Описание

F7 /7

IDIV r/m16

27/28 (i486)

Деление со знаком DX:AX на слово из [r/m]

(результат: AX=частное, DX = остаток)

Правила выполнения команды рассмотрены ниже

врем <− делимое / делитель;

IF врем не помещается в частном

THEN Прерывание 0;

ELSE

частное <− врем;

остаток <− делимое .mod. (r/m); операция взятия остатка от деления

END IF;

Замечание: Делитель задается явно в ячейке с адресом r/m (регистр/память). Делимое, частное и остаток используют неявно задаваемые регистры AX, DX, соответственно. Числа представляются в дополнительном коде со знаком.

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

Нецелые частные усекаются до 0. Остаток имеет тот же знак, что и делимое, а его абсолютное значение всегда меньше абсолютного значения делителя.

Например: при делении -5 на +6 получим в частном 0, а в остатке -5, при делении +6 на -5 получим в частном -1, а в остатке +1.

Флаги результата OF, SF, ZF, AF, PF, CF не определены.

Проанализировав приведенное выше краткое справочное описание правил выполнения команд можно сделать предположение, что для реализации команды IDIV использован классический алгоритм деления без восстановления остатка, подробно разобранный, например, в [Каган Б.М. Электронные вычислительные машины и системы. - М.: Энергоатомиздат , 1985.- 552 с. : ил.; Пьявченко О.Н. Алгоритмические основы выполнения математических операций в микрокомпьютерах: Учебное пособие. Таганрог: Изд-во ТРТУ, 1998. 190 с.].

Именно этот алгоритм работает над двумя N-разрядными целыми двоичными числами, представленными в дополнительном коде, причем первое из них (делимое) предварительно должно быть расширено по знаку до 2N-разрядного целого двоичного числа. Алгоритм регулярен по числу шагов основного цикла и имеет в процессе завершения два шага коррекции, правила выполнения которых зависит от сочетания знаков делимого, делителя и полученного в основном цикле ненулевого остатка, что будет подробно рассмотрено ниже.

Введем условные обозначения:

ДМ - n-разрядная регистровая ячейка для размещения кода делимого,

ДТ - n-разрядная регистровая ячейка для размещения кода делителя,

ЧОСТ - n-разрядная регистровая ячейка для размещения кода частичного остатка,

ОСТ - n-разрядная регистровая ячейка для размещения кода результирующего остатка,

ЧАСТН - n-разрядная регистровая ячейка для размещения кода частного результата,

ТСРЗН – одноразрядная ячейка (триггер) сравнения знаков делимого (затем ЧОСТ) и делителя: если знаки равны, то ячейка содержит 1, иначе - 0,

ТСРЗНдоп – дополнительная одноразрядная ячейка (триггер) сравнения знаков делимого и делителя: если знаки равны, то ячейка содержит 1, иначе - 0,

КОРР1 – первый шаг коррекции,

КОРР2 – второй шаг коррекции,

ЗНДМ – знак делимого,

ЗНДТ – знак делителя,

ЗНЧОСТ – знак частичного остатка,

NOT – битовая операция логического отрицания.

SIGN(ДМ) – операция размножения знака делимого до слова длиной N двоичных разрядов.

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

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

  2. Проверить делитель ДТ на равенство нулю. Если да, то завершить выполнение операции с ошибкой деления на ноль.

  3. Размножить знак ДМ в регистровую ячейку ЧОСТ, а также установить значения ячеек ЗНДМ и ЗНДТ.

  4. Сформировать значение в ТСРЗН, ТСРЗНдоп, равные NOT(ЗНДМ  ЗНДТ).

  5. (Начало основного цикла) Выполнить логический сдвиг влево на один разряд значений регистров ЧОСТ, ДМ. Причем в освободившийся младший разряд ЧОСТ[0] занести вытолкнутое значение старшего разряда ДМ[N-1], а значение младшего разряда ДМ[0] установить равным ТСРЗН.

  6. Проверить ТСРЗН: если ячейка равна 1, то перейти к п.7, иначе (при 0) перейти к п.8.

  7. Выполнить операцию вычитания из ЧОСТ значения ДТ: ЧОСТ:= ЧОСТ – ДТ и перейти к п.9.

  8. Выполнить операцию приращения ЧОСТ на значение ДТ: ЧОСТ:= ЧОСТ + ДТ и перейти к п.9.

  9. Сформировать значение в ТСРЗН, равное NOT ( ЗНЧОСТ ЗНДТ ).

  10. N-раз повторить п.п. 5-9, где N-разрядность числа, включая его знак.

  11. ((N+1) – й шаг алгоритма. Начало шага.) Выполнить логический сдвиг влево на один разряд значения регистра ДМ. Причем освободившееся значение младшего разряда ДМ[0] установить равным ТСРЗН. Вытолкнутое значение старшего разряда регистра ДМ теряется.

  12. Перегрузить регистр ДМ в регистр ЧАСТН. Проверить ЧОСТ на равенство 0: если да, то не выполнять коррекцию частичного остатка и перейти к п.22, иначе выполнить п.13.

  13. Проверить ТСРЗН: если ячейка равна 1 , то перейти к п.14, иначе (при 0) перейти к п.15.

  14. Выполнить операцию вычитания из ЧОСТ значения ДТ: ЧОСТ:= ЧОСТ – ДТ и перейти к п.16.

  15. Выполнить операцию приращения ЧОСТ на значение ДТ: ЧОСТ:= ЧОСТ + ДТ и перейти к п.16.

  16. (Конец N+1-го шага алгоритма) Сформировать значение в ТСРЗН, равное NOT(ЗНЧОСТ  ЗНДТ).

  17. Проверить ЧОСТ на равенство 0: если да, то перейти к п.22, иначе – перейти к п.18.

  18. Сравнить знак ЧОСТ со знаком делимого в исходном представлении (ЗНДМ): Если знаки равны, то перейти к п.22 (шаг КОРР1 не нужен), иначе перейти к п.19.

Структура первого шага коррекции Таблица 3.5

Знак ДМ

ЗнакЧОСТ

Знак ДТ

КОРР1

Комментарий

+

+

Любой

Нет

Коррекция не нужна





Любой

Нет

Коррекция не нужна

+



+

+ ДТ

К ЧОСТ прибавить ДТ



 ДТ

От ЧОСТ вычесть ДТ



+

+

 ДТ

От ЧОСТ вычесть ДТ



+ ДТ

К ЧОСТ прибавить ДТ

  1. Выполнить шаг КОРР1 (см. таблицу 3.5): восстановить остаток. Для чего проверить значение ТСРЗН: если триггер равен 1 (знаки ЧОСТ и ДТ равны), то п.20, иначе п.21.

  2. Выполнить операцию вычитания из ЧОСТ значения ДТ: ЧОСТ:= ЧОСТ – ДТ и перейти к п.22.

  3. Выполнить операцию приращения ЧОСТ на значение ДТ: ЧОСТ:= ЧОСТ + ДТ и перейти к п.22.

  4. Выполнить здесь и далее второй шаг коррекции (КОРР2). Для чего проверить исходные знаки ДМ и ДТ (см. таблицу 3.6): если ТСРЗНдоп равняется 1 (знаки ДМ и ДТ равны), то п.23, иначе (при неравенстве знаков ДМ и ДТ) перейти к п.26.

Таблица 3.6

Структура второго шага коррекции

Знак ДМ

Знак ДТ

ЧОСТ

КОРР2

Комментарий

+

+

Любой

Нет

Коррекция не нужна

+



Любой

+1

Нарастить ЧАСТН на 1



+

≠ 0

+1

Нарастить ЧАСТН на 1

= 0

Нет

Коррекция не нужна





≠ 0

Нет

Коррекция не нужна

= 0

+1

Нарастить ЧАСТН на 1




  1. Проверить исходный знак ДМ: если ЗНДМ равняется 0 (ДМ положительно), то коррекция ЧАСТН не нужна и переход к п.28, иначе п.24.

  2. Проверить значение ЧОСТ на равенство 0, если ЧОСТ не равен 0, то коррекция ЧАСТН не нужна и перейти к п.28, иначе п. 25.

  3. Нарастить частное на 1: ЧАСТН := ЧАСТН +1, перейти к п.28.

  4. Проверить исходный знак ДМ: если ЗНДМ равняется 0 (ДМ положительно), то переход к п.25, иначе п.27.

  5. Проверить значение ЧОСТ на равенство 0, если ЧОСТ равен 0, то коррекция не нужна и перейти к п.28, иначе п. 25.

  6. Регистр ОСТ загрузить содержимым ЧОСТ и завершить алгоритм.

  7. Конец алгоритма.

3.2.2. Числовые примеры реализации операции деления

Поясним работу алгоритма на нескольких числовых примерах.

Пример 3.4

Пусть необходимо поделить два числа 7 и -5.

Представим эти десятичные числа в форме четырех разрядного дополнительного двоичного кода: ДМ - 01112 и ДТ - 10112, соответственно. Величина (–ДТ) равна 0101. Тогда имеют место следующие действия

Таблица 3.7

Nо шага

Операция

ЧОСТ

ДМ

ТСРЗН

ДТ = 1011

ТСРЗНдоп

ЧАСТН

ОСТ

Комментарии







0000

0111

0

0

0000

0000

Загрузка ЧОСТ, ДМ, ТСРЗН…

1




0000

1110













Сдвиг влево

+ДТ

1011
















ЧОСТ +=ДТ




1011

1110

1

0

0000

0000

Результат суммы

2




0111

1101













Сдвиг влево

+(-ДТ)

0101
















ЧОСТ =ДТ




1100

1101

1

0

0000

0000

Результат суммы

3




1001

1011













Сдвиг влево

+(-ДТ)

0101
















ЧОСТ =ДТ




1110

1011

1

0

0000

0000

Результат суммы

4




1101

0111













Сдвиг влево

+(-ДТ)

0101
















ЧОСТ =ДТ




0010

0111

0

0

0000

0000

Результат суммы

5




0010

1110













Сдвиг влево только над ДМ

+ДТ

1011
















ЧОСТ +=ДТ




1101

1110

1

0

0000

0000

Результат суммы

6

+(-ДТ)

0101
















КОРР1




0010

1110

0

0

1110

0010

ОСТ найден

7

+1













0001




КОРР2:

ЧАСТН +=1 , т.к. ДМ>0 и ДТ<0










0

0

1111

0010

Найден полный результат

Пример 3.5

Пусть необходимо поделить два числа -7 и +5.

Представим эти десятичные числа в форме четырех разрядного дополнительного двоичного кода: ДМ - 10012 и ДТ - 01012, соответственно. Величина

(–ДТ) равна 10112.

Тогда имеют место следующие действия
Таблица 3.8

Nо шага

Операция

ЧОСТ

ДМ

ТСРЗН

ДТ = 0101

ТСРЗНдоп

ЧАСТН

ОСТ

Комментарии







1111

1001

0

0

0000

0000

Загрузка ЧОСТ, ДМ, ТСРЗН…

1




1111

0010













Сдвиг влево

+ДТ

0101
















ЧОСТ +=ДТ




0100

0010

1

0

0000

0000

Результат суммы

2




1000

0101













Сдвиг влево

+(-ДТ)

1011
















ЧОСТ =ДТ




0011

0101

1

0

0000

0000

Результат суммы

3




0110

1011













Сдвиг влево

+(-ДТ)

1011
















ЧОСТ =ДТ




0001

1011

1

0

0000

0000

Результат суммы

4




0011

0111













Сдвиг влево

+(-ДТ)

1011
















ЧОСТ =ДТ




1110

0111

0

0

0000

0000

Результат суммы

5




1110

1110













Сдвиг влево только над ДМ

+ДТ

0101
















ЧОСТ +=ДТ




0011

1110

1

0

0000

0000

Результат суммы

6

+(-ДТ)

1011
















КОРР1




1110

1110

0

0

1110

1110

ОСТ найден

7

+1













0001




КОРР2:

ЧАСТН +=1, т.к. ОСТ <> 0 и ДМ<0 и ДТ>0
















1111

1110

Найден полный результат

Пример 3.6

Пусть необходимо поделить два числа -7 и -5.

Представим эти десятичные числа в форме четырех разрядного дополнительного двоичного кода: ДМ - 10012 и ДТ - 10112, соответственно. Величина (–ДТ) равна 01012.

Тогда имеют место следующие действия

Таблица 3.9

Nо шага

Операция

ЧОСТ

ДМ

ТСРЗН

ДТ = 1011

ТСРЗНдоп

ЧАСТН

ОСТ

Комментарии







1111

1001

1

1

0000

0000

Загрузка ЧОСТ, ДМ, ТСРЗН…

1




1111

0011













Сдвиг влево

+(–ДТ)

0101
















ЧОСТ =ДТ




0100

0011

0

1

0000

0000

Результат суммы

2




1000

0110













Сдвиг влево

+ ДТ

1011
















ЧОСТ +=ДТ




0011

0110

0

1

0000

0000

Результат суммы

3




0110

1100













Сдвиг влево

+ДТ

1011
















ЧОСТ +=ДТ




0001

1100

0

1

0000

0000

Результат суммы

4




0011

1000













Сдвиг влево

+ДТ

1011
















ЧОСТ +=ДТ




1110

1000

1

1

0000

0000

Результат суммы

5




1110

0001













Сдвиг влево только над ДМ

+(–ДТ)

0101
















ЧОСТ =ДТ




0011

0001

0

1

0000

0000

Результат суммы

6

+ДТ

1011
















КОРР1




1110

0001

1

1

0001

1110

ОСТ найден

7

+0













0000




Нет КОРР2, т.к. ОСТ <> 0 и ДМ<0 и ДТ<0
















0001

1110

Найден полный результат


Пример 3.7

Пусть необходимо поделить два числа -6 и +2.

Представим эти десятичные числа в форме четырех разрядного дополнительного двоичного кода: ДМ - 10102 и ДТ - 00102, соответственно. Величина (–ДТ) равна 11102.

Тогда имеют место следующие действия
Таблица 3.10

Nо шага

Операция

ЧОСТ

ДМ

ТСРЗН

ДТ = 1011

ТСРЗНдоп

ЧАСТН

ОСТ

Комментарии







1111

1010

0

0

0000

0000

Загрузка ЧОСТ, ДМ, ТСРЗН…

1




1111

0100













Сдвиг влево

+ДТ

0010
















ЧОСТ +=ДТ




0001

0100

1

0

0000

0000

Результат суммы

2




0010

1001













Сдвиг влево

+(-ДТ)

1110
















ЧОСТ =ДТ




0000

1001

1

0

0000

0000

Результат суммы

3




0001

0011













Сдвиг влево

+(-ДТ)

1110
















ЧОСТ =ДТ




1111

0011

0

0

0000

0000

Результат суммы

4




1110

0110













Сдвиг влево

+ДТ

0010
















ЧОСТ +=ДТ




0000

0110

1

0

0000

0000

Результат суммы

5




0000

1101













Сдвиг влево только над ДМ

+0

0000
















Нет суммирования, т.к. ЧОСТ = 0




0000

1101

1

0

0000

0000

Результат суммы

6

+0



















Нет КОРР1, т.к. ЧОСТ = 0




0000

1101

1

0

1101

0000

ОСТ найден

7

+0













0




Нет КОРР2, т.к. ОСТ = 0 и ДМ<0 и ДТ>0
















1101

0000

Найден полный результат
  1   2   3

Похожие:

3 Операция деления без восстановления остатка над целыми двоичными числами со знаком, представленными в дополнительном коде iconДомашнее задание по алгебре для 211 группы на вторник, 10 сентября
Найдите бесконечно много многочленов четвёртой степени (с целыми коэффициентами), неприводимых над Z, редукция по любому простому...
3 Операция деления без восстановления остатка над целыми двоичными числами со знаком, представленными в дополнительном коде iconКризис в нашей партии 97
Первый такой вопрос — вопрос о политическом значении того деления нашей пар­тии на «большинство» и «меньшинство», которое сложилось...
3 Операция деления без восстановления остатка над целыми двоичными числами со знаком, представленными в дополнительном коде iconКнига из электронной библиотеки сайта
Эпическо-философская аллегория Янна Мартела справляется с этой задачей блестяще. Приключенческая по форме, познавательная по содержанию...
3 Операция деления без восстановления остатка над целыми двоичными числами со знаком, представленными в дополнительном коде iconЖизнь 12-летнего школьника Барни Ива сложно назвать легкой. Год назад...
Гэвин Игл, а директриса мисс Хлыстер решила окончательно сжить его со свету. Как бы Барни хотелось забыть обо всем этом и пожить...
3 Операция деления без восстановления остатка над целыми двоичными числами со знаком, представленными в дополнительном коде iconСложить в последовательном и параллельном коде в дизсс

3 Операция деления без восстановления остатка над целыми двоичными числами со знаком, представленными в дополнительном коде iconДевственницы здоровьенации
Что это: курьез или тенденция? Если тенденция, то реально ли ожидать восстановления норм нравственности в Америке? И пойдут ли путем...
3 Операция деления без восстановления остатка над целыми двоичными числами со знаком, представленными в дополнительном коде iconС рочно! Нужна ваша помощь!
Со мной произошло несчастье. Я получил травму позвоночника и уже 2 года нахожусь парализован, без движения в конечностях. Но теперь...
3 Операция деления без восстановления остатка над целыми двоичными числами со знаком, представленными в дополнительном коде iconВладычество, как проявлений Образа Божия в человеке
«И сказал Бог: сотворим человека по образу Нашему по подобию Нашему, и да владычествуют они над рыбами морскими, и над птицами небесными,...
3 Операция деления без восстановления остатка над целыми двоичными числами со знаком, представленными в дополнительном коде iconПродолжение перечисления изучения проявлений Образа Божия в человеке
«И сказал Бог: сотворим человека по образу Нашему по подобию Нашему, и да владычествуют они над рыбами морскими, и над птицами небесными,...
3 Операция деления без восстановления остатка над целыми двоичными числами со знаком, представленными в дополнительном коде iconПродолжение перечисления изучения проявлений Образа Божия в человеке
«И сказал Бог: сотворим человека по образу Нашему по подобию Нашему, и да владычествуют они над рыбами морскими, и над птицами небесными,...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
vb2.userdocs.ru
Главная страница