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

Большинство компьютерных систем не могут напрямую адресовать биты, которые содержатся группами по 8, 16, 32 или 64 битов в словах. Для обеспечения работы с битами существует множество машинных инструкций, включающие различные типы сдвигов.

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

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

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

Существует несколько вариантов сдвига:

1. Логический сдвиг. Сдвиг, который выполняется над всеми разрядами операнда, включая знаковый. В младший или старший биты записывается (0).

2. Арифметический сдвиг. Не влияет на положение знака операнда.

Арифметический сдвиг двоичного операнда, влево или вправо на ( ) разрядов, эквивалентно соответственно умножению и делению исходного операнда на ( ). При сдвиге вправо разряды исходного операнда, которые выходят за пределы разрядной сетки регистра, теряются, внося при этом ошибку, которая по абсолютной величине не превышает полученного после сдвига числа.

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

3. Модифицированный сдвиг. Арифметический сдвиг операндов, представленных обратным или дополнительным кодом:

- обратный код - при правом и левом сдвигах в освобождающиеся разряды регистра записываются цифры знакового разряда;

- дополнительный код - при сдвиге вправо в разряды, которые освобождаются, записываются цифры знакового разряда, а при сдвиге влево - в освобождающиеся разряды записываются нули.

4. Циклический сдвиг. Операнд перемещается в регистре как в замкнутом контуре, поступая с выхода последнего разряда на вход первого.

Схемы выполнения операций сдвига приведены на рис. 3.1.

Рисунок 3.1 - Схемы выполнения операций сдвига в компьютерной системе

В отличие от ручного умножения, операционное устройство компьютерной системы не может просуммировать сразу ( ) частичных произведений, как это делает человек. Обычный сумматор, как правило, рассчитан на одновременное сложение только двух операндов. Если нужно получить сумму нескольких слагаемых, то происходит накопление суммы: сначала в сумматор записывается первое слагаемое, к нему прибавляется второе, затем к полученной сумме прибавляется третье слагаемое и так до получения полной суммы. Длина произведения -битных сомножителей равна бит:

.

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

.

Умножение реализуется циклическим процессом, на каждом шаге которого:

- анализируется очередной бит ( ) множителя;

- в зависимости от его значения происходит ( ) или нет ( ) прибавление множимого к предыдущей сумме частичных произведений;

- производится изменение взаимного положения множимого ( ) и суммы частичных произведений с учетом веса ( ).

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

В соответствии со способом формирования суммы частичных произведений (ЧП), возможны четыре варианта умножения.

Они различаются тем, с каких разрядов множителя ( ) (младших или старших) начинается умножение, и что сдвигается - множимое или сумма ЧП.

Варианты умножения, начиная с младших или старших разрядов множителя, называются еще умножением младшими и старшими разрядами вперед соответственно.

Схемы выполнения операции умножения двоичных беззнаковых чисел представлены на рис 3.2.

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

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

Соответственно, при умножении старшими разрядами вперед должен анализироваться старший разряд множителя.

Схема №1.

.

.

Время выполнения операции умножения:

где ( ) - время, затрачиваемое на выполнение операции сдвига на один разряд;

( ) - время, затрачиваемое на выполнение операции сложения.

Рисунок 3.2 - Схемы выполнения операции умножения двоичных беззнаковых чисел в компьютерной системе

Схема №2.

.

.

Время выполнения операции умножения:

где ( ) - время, затрачиваемое на выполнение операции сдвига на один разряд;

( ) - время, затрачиваемое на выполнение операции сложения.

Схема №3.

.

.

Время выполнения операции умножения:

где ( ) - время, затрачиваемое на выполнение операции сдвига на один разряд;

( ) - время, затрачиваемое на выполнение операции сложения.

Схема №4.

.

.

Время выполнения операции умножения:

где ( ) - время, затрачиваемое на выполнение операции сдвига на один разряд;

( ) - время, затрачиваемое на выполнение операции сложения.

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

Алгоритм №1. Алгоритм умножения младшими разрядами вперед, со сдвигом суммы ( ) вправо.

1. Исходное значение суммы ( ) принимается равным ( ), счетчику тактов - ( ) присваивается значение, равное числу разрядов множителя.

2. Анализируется младшая разрядная цифра множителя. Если она равна ( ), то к сумме ( ) прибавляется множимое, совмещенное по старшим разрядам; если ( ) - прибавление не производится.

3. Производится сдвиг множителя и суммы ( ) вправо на ( ) разряд. Содержимое ( ) уменьшается на ( ).

4. Анализируется содержимое ( ). Если оно не равно ( ), то переход к (п.2), иначе - (п.5).

5. Умножение закончено, младшая часть произведения находится на месте множителя, а старшая - на месте суммы ( ).

Алгоритм №2. Алгоритм умножения старшими разрядами вперед, со сдвигом суммы ( ) влево.

1. Исходное значение суммы ( ) принимается равным ( ), ( ) присваивается значение, равное числу разрядов множителя.

2. Производится сдвиг суммы ( ) влево на ( ) разряд.

3.Анализируется старшая разрядная цифра множителя. Если она равна ( ), то к сумме ( ) прибавляется множимое, совмещенное по младшим разрядам; если ( ) - прибавление не производится.

4.Производится сдвиг множителя влево на ( ) разряд. Содержимое ( ) уменьшается на ( ).

5.Анализируется содержимое ( ). Если оно не равно ( ), то переход к (п.2), иначе - (п.6).

6.Умножение закончено, произведения находится на месте суммы ( ), которая имеет удвоенную разрядность

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

- первый тип это когда делимое, делитель и частное имеют одну и ту же длину ( );

- второй тип это когда делимое имеет длину ( ) - удвоенную по сравнению с делителем и частным. Тогда можно записать:

.

.

.

.

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

.

или

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

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

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

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

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

- алгоритм №1 с восстановлением остатка;

- алгоритм №2 без восстановления остатка.

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

Рисунок 3.3 - Схемы деления двоичных беззнаковых чисел в компьютерной системе

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

Алгоритм №1. Деление целых двоичных беззнаковых чисел методом с восстановлением остатка.

1. Исходное значение частного ( ) полагается равным ( ). ( ) присваивается значение ( ). Исходное значение частичного остатка ( ) полагается равным ( ) старшим разрядам делимого.

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

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

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

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

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

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

8. п.п. последовательно выполняются до получения всех цифр частного, пока ( ) не станет равным ( ).

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

Недостатки:

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

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

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

.

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

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

.

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

.

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

.

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

.

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

.

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

.

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

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

1. Исходное значение частного ( ) полагается равным ( ). ( ) присваивается значение ( ). Исходное значение частичного остатка ( ) полагается равным ( ) старшим разрядам делимого.

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

3. ( ) удваивается путем сдвига на один разряд влево.

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

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

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

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

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

Контрольные вопросы

1. Объясните прицип работы логического сдвига.

2. Объясните принцип работы арифметического сдвига.

3. Объясните принцип работы модифицированного сдвига.

4. Объясните принцип работы циклического сдвига.

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

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

7. Сформулируйте алгоритм деления целых двоичных беззнаковых чисел методом с восстановлением остатка.

8. Сформулируйте алгоритм деления целых двоичных беззнаковых чисел методом без восстановлением остатка