К. Хамахер, З. Вранешич, С. Заки - Организация ЭВМ - 5-е издание (2003) (1114649), страница 26
Текст из файла (страница 26)
Арифметический сдвиг влево ничем не отличается от логического. Циклический сдвиг В операциях сдвига те биты, которые перемещаются за пределы операнда, оказываются просто потерянными. Сохраняется только последний сдвинутый бит, который копируется во флаг переноса С. Для сохранения всех битов операнда применяются операции циклического сдвига, перемещающие «выдвинувшиеся» с одного края разряды на другой край. Обычно компьютер поддерживает две версии циклического сдвига вправо и две версии циклического сдвига влево. В первой версии разряды операнда просто циклически сдвигаются, а во второй в сдвиге участвует еще и флаг С.
Примеры всех четырех операций циклического сдвига приведены на рис. 2.32. После: Д Дс: ~(Д После: Н Рис. 2.32. Команды циклического сдвига: влево без переноса, йо(а(е(. З2,йо (а); влево с переносом, йо(а!е(.С а2,йо (б); вправо без переноса, йо(а(ей а2,ЙО (в); вправо с переносом, йо(а(ейС а2,йо [г) 110 Глава 2. Машинные команды и программы но После: До: Д1 После: Рис.
2.32 1продопжеиие) Обратите внимание, что в тех случаях, когда флаг С не участвует в операции, он, тем не менее, содержит последний бит, выдвинутый из операнда. Для определения операций циклического сдвига используются мнемонические обозначения Кога1е1., Косасе).С, КосасеК и КогасеКС. Указанные команды в основном применяются в арифметических операциях, отличных от операций сложения и вычитания (см. главу 6). 2.10.3. Команды умножения и деления Для умножения и деления двух целых чисел со знаком применяются машинные команды того же формата, что и команда Аос1. Так, команда мп!11р1у к1,кз' выполняет операцию К1 - 1К11 ° 1К)1 Произведение двух п-разрядньгх чисел может иметь размер до 2л разрядов.
Таким образом, результат операции не всегда может поместиться в регистр К). Многие компьютеры поддерживают команду Мп111р1у, которая вычисляет и младших разрядов произведения и помещает их в заданный регистр, Этого достаточно для тех ситуаций, когда заранее известно, что произведение имеет не более н разрядов. Для выполнения универсальной операции, формирующей полное произведение длиной в 2л разрядов, некоторые процессоры поддерживают другую команду, помещаюшую результат в два регистра, К) и КО+1). 2.11.
Примеры программ 111 В некоторых системах команд присутствует менее распространенная команда деления двух целых чисел со знаком Рглйе КВК) выполняющая операцию К) +- Щ / Щ При этом частное помещается в регистр К~, а остаток от деления либо помещается в регистр Щ+1), либо просто теряется. Команды Мц1Г1р1у и Ргвк(е поддерживаются не всеми компьютерами. Те компьютеры, которые их не поддерживают, выполняют эти и другие арифметические операции с помощью последовательности элементарных команд, таких как АЫ, 3пйтгасц 31пгГ и Когасе. Вы поймете, как это делается, когда будете читать главу 6, посвященную способам реализации арифметических операций.
2.11. Примеры программ В данном разделе вы познакомитесь с тремя примерами, иллюстрирующими принцип применения машинных команд. Они показывают, что собой представляют числовые (векторные) и нечисловые (выполняющие сортировку и операции со связным списком) приложения. 2.11.1. Программа вычисления скалярного произведения векторов Первый пример представляет собой числовое приложение, подобное программе, приведенной на рис. 2.16, которая выполняла сложение чисел. В программах, осуществляющих обработку векторов и матриц, часто требуется вычислить скалярное произведение двух векторов.
Предположим, у нас имеются векторы А и В длиной ж Их скалярное произведение определяется так; и-1 Скалярное произведение = ~ А® х В(1) г=в На рис. 2.33 приведена программа, вычисляющая скалярное произведение и сохраняющая результат в памяти по адресу РОТРКОР. Первые элементы векторов, А(0) и В(0), хранятся по адресам АЧЕС и ВЧЕС, а остальные — в следующих друг за другом словах. Потребность в накоплении суммы произведений возникает во многих приложениях, выполняющих обработку сигналов. В таких приложениях один из векторов состоит из последних п отсчетов, поступивших на вход устройства обработки сигналов, а второй — из и весовых коэффициентов.
Сумма их произведений составляет выходной сигнал устройства. В системах некоторых компьютеров присутствует команда Ми12(р!уАссипш1ате, объединяющая команды Мц1ар1у и А~Ы, как в программе, представленной на рис. 2.33. В частности, такая команда имеется у процессора АКМ (см. главу 3). 112 Глава 2. Машинные команды и программы К1 указывает на вектор А К2 указывает на вектор В КЗ используется в качестве счетчика В КО накапливается сумма произведений Вычисление произведения следующих компонентов Прибавление к предыдущей сумме Уменьшение значения счетчика Пикл Сохранение скалярного произведения в памяти Моче Моче Моче С!езг ЛАЧЕС,К1 ВВЧЕС,К2 Х,КЗ КО (К1)ч-,К4 (К2)ч-,К4 К4,К0 КЗ 1.00Р КО,ООТРКОР 1.00Р Моче Мп1йр1у Аоо Эесгешепт ВгапсЬ>0 Моче Рис.
2.33. Программа длл вычисления скалярного произведения двух векторов 2.11.2. Программа выполнения сортировки байтов Рассмотрим программу для сортировки списка хранящихся в памяти байтов по алфавиту. Предположим, что список состоит из п байт, которые не обязательно должны быть разными, и что каждый байт содержит А3СП-код буквы латинского алфавита (из набора от А до Х). В кодировке А3СП, полностью приведенной в приложении Д, буквы А, В, ..., 2 представлены 7-разрядными двоичными кодами. Если интерпретировать зти коды как числовые значения, будут получены последовательные целые числа.
Когда символ А3СП записывается в память в виде байта, старший разряд этого байта устанавливается в О. Таким образом, для сортировки списка букв по алфавиту достаточно отсортировать по возрастанию их числовые коды, рассматривая их как положительные числа. Пусть наш список хранится в памяти по адресу от 1Л3Т до 1ЛВТ ч- п — 1, где п — это 32-разрядное значение, находящееся по адресу )ч). Отсортированный список должен быть помещен на место исходного. Для сортировки воспользуемся алгоритмом простого перебора. Сначала найдем наибольшее число и поместим его в конец списка по адресу 1.13Т ч- и — 1. Затем в оставшемся списке из л — 1 элементов найдем наименьшее число и поместим его по адресу 1.13Т ч- л — 2. Эта процедура будет повторяться до тех пор, пока мы не отсортируем весь список.
На рис. 2.34, а приведена реализующая данный алгоритм программа на языке С, в которой список интерпретируется как одномерный массив с элементами ?ЛВТ(0)...1ЛВТ(п — 1). Для каждого подсписка?ЛВТ(1)...1ЛВТ(0) значение элемента 1Л3Т()) сравнивается с каждым из остальных элементов подсписка. Если этот элемент оказывается больше, он меняется местами с числом 1ЛВТ()). Программа на языке С обрабатывает список в направлении от конца к началу. Такой порядок облегчает завершение цикла в программе на машинном языке, поскольку цикл завершается тогда, когда текущий индекс становится равным нулю.
Программа на языке ассемблера, реализующая этот же алгоритм сортировки приведена на рис. 2.34, б. Комментарии к этой программе поясняют принцип использования различных регистров. В процессе сканирования подсписка текущее 2.11. Примвры программ 113 максимальное значение хранится в регистре КЗ. Если значение элемента списка оказывается больше КЗ, оно меняется местами со значением в регистре КЗ и за- писывается в Е1БТ(у).
!пг ша1п(1пг агяс, сЬаг" агяч[]) ( (ог (1 - п-1; ]>О; ] - ]-1) (Гог Ь - 1-1; Ь>-0; 1г - х-1) (11 (1.1БТ[[г] > Ь15Т[]]) (ТЕМР - Ь1БТ[]г]; 115Т[Ь] - 115Т[]]; 115Т[]] - ТЕМР; Загрузка списка в базовый регистр КО Инициализация индекса внешнего цикла в регистре К1 значением) - и — 1 Инициализация индекса внешнего цикла в регистре К2 значением Й -У вЂ” ! Загрузка значения Ь15Т(~) в регистр КЗ, содержащий текущее максимальное значение подсписка Если Ь15Т(а) < КЗ, не менять значения местами В противном случае поменять местами Ь1БТ(~) и Ь15Т(Й) и загрузить в КЗ новое максимальное значение Регистр К4 выполняет функции переменой ТЕМР Уменьшение значения индексных регистров К2 и К1, выполняющих функции счетчиков цикла,и, если цикл не завершен, переход назад Моче Моче БиЬтгасг Моче БцЬггасг МочеВуге №ь15Т,КО Ь),К1 №1,К1 К1,К2 №1,К1 (КО,К1),КЗ ОТТЕК !Хг)ЕК СошрагеВуте ВгапсЬяО МочеВуте МочеВуге МочеВуте Моче Вузе КЗ,(КО,К2) Ь[ЕХТ (КО,К2),К4 КЗ,(КО,К2) К4,(КО,К1) й]ЕХТ 1)есгешепг ВгапсЬ>0 1)есгешепс ВгапсЬ>0 К2 1)ьг~ЕК К1 О1)ТЕК Рис.
2.34. Программа, сортнрующая байты методом простого перебора: на языке С (а[; на языке ассемблера (б] Управление ходом выполнения двух программ осуществляется по-разному. В управляющей инструкции 11 гЬеп в программе на языке С используется трех- строчное предложение гЬеп, меняющее местами элементы массива Е1БТ([г) и 11БТ(т), если 1.1БТ(]г) < 1ЛБТ(т). В программе на языке ассемблера в случае, если 114 Глава 2. Машинные команды и программы ЫЗТ(1) < ЫЗТ(1), выполняется обход четырех команд, меняющих местами элементы списка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
