2014-01-25
838
Примечание.
При умножении на младшую единицу производится вычитание множимого. При умножении на младшие нули осуществляется только сдвиг нулевой СЧП и множителя до появления первой единицы.
Пример. А =11, В = 15, n = 5.
[Aпр.] = 0.1011 [Bпр.] = 0.1111
[Aдоп.] = 1.0101 [Вдоп.] = 1.0001
а) А>0, B>0:
| № шага | Операнды и действия | СЧП (старшие разряды) | СЧП (младшие разряды) | Пояснения | ||||||||
| СЧП | Обнуление старших разрядов СЧП. | |||||||||||
| [-A]доп. | Младший разряд множителя равен 1: вычитание множимого из СЧП | |||||||||||
| СЧП | ||||||||||||
| СЧП→ | Сдвиг СЧП. | |||||||||||
| СЧП→ | Сдвиг СЧП. | |||||||||||
| СЧП→ | Сдвиг СЧП. | |||||||||||
| СЧП→ | Сдвиг СЧП. | |||||||||||
| [A]пр. | При сдвиге младший разряд множителя изменился с 1 на 0: сложение СЧП с множимым | |||||||||||
| СЧП | ||||||||||||
| СЧП→ | Сдвиг СЧП. |
Спр. = (0.010100101)2 = 165
|
|
|
а) А<0, B<0:
| № шага | Операнды и действия | СЧП (старшие разряды) | СЧП (младшие разряды) | Пояснения | ||||||||
| СЧП | Обнуление старших разрядов СЧП. | |||||||||||
| [-A]пр. | Младший разряд множителя равен 1: вычитание множимого из СЧП | |||||||||||
| СЧП | ||||||||||||
| СЧП→ | Сдвиг СЧП. | |||||||||||
| [A]доп. | При сдвиге младший разряд множителя изменился с 1 на 0: сложение СЧП с множимым | |||||||||||
| СЧП | ||||||||||||
| СЧП→ | ||||||||||||
| СЧП→ | Сдвиг СЧП. | |||||||||||
| СЧП→ | Сдвиг СЧП. | |||||||||||
| [-A]пр. | При сдвиге младший разряд множителя изменился с 0 на 1: вычитание множимого из СЧП | |||||||||||
| СЧП | ||||||||||||
| СЧП→ | Сдвиг СЧП. |
Спр. = (0.010100101)2 = 165
Особенности двоичного деления
Пример. А = 130, В = 10.
А/В = С(R),
где А – делимое,
В – делитель,
С – частное,
R – остаток.
А = (130)10 = (10000010)2
В = (10)10 = (1010)2
_ 1 0 0 0 0 0 1 0 | 1 0 1 0
1 0 1 0 | 0 1 1 0 1
1 1 1 0 (R<0)
_ 1 0 0 0 0 0 1 0
1 0 1 0
0 0 1 1 0 (R>0)
_ 1 1 0 0 1 0
1 0 1 0
0 0 1 0 (R>0)
_ 0 1 0 1 0
1 0 1 0
1 0 1 1 (R<0)
_ 0 1 0 1 0
1 0 1 0
0 0 0 0 (R≥0)
|
|
|
Из проделанного примера отчетливо проявляются следующие особенности двоичного сложения:
1) Процесс деления сводится к последовательному вычитанию делителя первоначально из делимого, а далее – из получаемых текущих остатков (под текущим остатком будем понимать промежуточный результат вычитания делителя из делимого на первом шаге или очередного остатка на последующих шагах).
2) На начальном шаге делитель совмещается со старшими разрядами делимого, а затем на каждом шаге делитель сдвигается на одну позицию (разряд) вправо относительно неподвижного текущего остатка. На последнем шаге делитель совмещается с младшими разрядами текущего остатка.
3) Цифры частного, вырабатываемые на каждом шаге, определяются знаком текущего остатка. Для остатка большего или равного 0 цифра частного равна 1, для остатка, который меньше 0, цифра частного равна 0.
4) О знаке текущего остатка можно судить по наличию или отсутствию заема в старший разряд при вычитании. Если заем есть, то результат вычитания (т.е. текущий остаток) отрицателен. Если заем отсутствует, то результат вычитания и, соответственно, текущий остаток не отрицателен.
5) При получении отрицательного остатка на очередном шаге перед переходом к следующему шагу необходимо выполнить восстановление остатка путем сложения отрицательного остатка с делителем (это действие в примере опущено).
Особенности реализации целочисленного деления в ЭВМ
• Т.к. операция деления является обратной по отношению к умножению, а результат сложения n-разрядных сомножителей представляется в 2n-разрядном формате, то делимое по сравнению с делителем так же должно представляться в удвоенном формате.
• В качестве результата деления формируется не только частное, но и остаток. Операция деления с остатком должна удовлетворять следующему соотношению:
B·C + R = A
Для большинства современных процессоров (в том числе и фирмы Intel) по окончании операции деления частное занимает младшие разряды делимого, а остаток – старшие разряды делимого.
• В целях экономии оборудования на каждом шаге операции деления осуществляется не сдвиг делителя вправо относительно неподвижного текущего остатка, а сдвиг текущего остатка влево относительно неподвижного делителя. При этом делитель должен совмещаться со старшими разрядами сначала делимого, а на последующих шагах – текущего остатка.
• При получении отрицательного остатка на каком-либо шаге для перехода к следующему шагу требуется предварительное восстановление остатка путем его сложения с делителем. Подробный подход к реализации операции деления называется «метод деления с восстановлением остатка». В целях экономии времени выполнения операции деления в современных процессорах деление реализуется с использованием метода без восстановления остатка. Идея метода сводится к тому, что после получения отрицательного остатка на очередном шаге деления осуществляется его сдвиг влево так же, как и для положительного остатка, однако на следующем шаге производится не вычитание делителя из остатка, а сложение делителя с остатком.
Обоснование метода
Допустим, что на i-ом шаге деления получен остаток Ri<0, тогда для получения очередного остатка Ri+1 на (i+1)-ом шаге над текущим остатком Ri выполняются следующие действия:
а) По методу с восстановлением остатка:
Ri+1 = (Ri + В)·2 – В = 2Ri + 2В – В = 2Ri + В
(Ri + В) – сложение с делителем;
(Ri + В)·2 – сдвиг влево на 1 разряд;
(Ri + В)·2 – В – вычитание делителя.
б) По методу без восстановления остатка:
Ri+1 = 2Ri + В
2Ri – сдвиг отрицательного остатка влево; 2Ri + В – сложение с делителем.
• При некоторых соотношениях между делимым и делителем может оказаться, что частное не помещается в формат делителя. Подобная ситуация возникает также, если делитель равен 0. Этот особый случай распознается и фиксируется на начальных шагах операции деления. Наличие подобного случая классифицируется как некорректность целочисленного деления и приводит к прерыванию выполняемой программы. Выход на это прерывание может быть зафиксирован при попытке разделить двухбайтное делимое, равное 1000, на однобайтный делитель, равный 1,2,3, при выполнении команды DIV (беззнаковое деление), а при выполнении команды IDIV также при В = 4,5.
|
|
|
Деление беззнаковых целых чисел
В основном беззнаковое деление реализуется по общим принципам, описанным ранее. Это означает, что цифра частного, вырабатываемая на каждом шаге деления, определяется знаком текущего остатка, получаемого на данном шаге. При отрицательном остатке вырабатывается цифра частного, равная 0; при положительном остатке – равная 1.
Проверка корректности беззнакового деления
Для n-разрядного делителя и, следовательно, n-разрядного частного условие корректности принимает вид:
А/B ≤ 2n – 1 => A/B < 2n
A < B · 2n
A - B · 2n < 0
Из полученного условия следует, что для проверки корректности беззнакового деления необходимо произвести вычитание делителя из старших разрядов делимого. Если полученная разность отрицательна, то деление корректно, т.е. частное помещается в формате делителя. Если же результат так называемого «пробного вычитания» положителен или равен 0, то результат деления в виде частного не может быть помещен в n-разрядный формат. При обнаружении такого случая генерируется требование прерывания выполняемой программы по причине некорректности целочисленного деления. Для процессоров Intel это прерывание является стандартным, ему присвоен номер, равный нулю.
