Основы программирования микропроцессоров



Download 1,87 Mb.
bet84/119
Sana23.02.2022
Hajmi1,87 Mb.
#139915
TuriКонтрольные вопросы
1   ...   80   81   82   83   84   85   86   87   ...   119
Bog'liq
Системное программирование

Пример 2. На языке ассемблера разработать подпрограмму бинарного поиска заданного элемента в упорядоченном массиве. Элементами массива должны быть беззнаковые целые числа размером слово. Искомый элемент должен быть помещен в регистр AX. Начальный адрес массива по-прежнему должен храниться в регистре DI, а количество элементов – в первом элементе.
Результат поиска должен быть возвращен через регистр SI и флаг CF: если значение не найдено флаг CF должен быть установлен в 1, а регистр SI содержать адрес последнего проверенного элемента; если поиск завершился успешно, флаг CF должен быть сброшен, а SI содержать адрес найденного элемента.


Решение. Процедура бинарного поиска BINSRCH приведена ниже (описание метода приведено в примере 4 главы 1). Она также использует вспомогательную переменную ARR, содержащую начальный адрес массива. Первым действием алгоритма является проверка искомого элемента на выход за границы диапазона. Для этого значение регистра AX сравнивается с первым и последним элементами массива. Если условие выхода за диапазон выполняется, устанавливается флаг CF с помощью команды STC и процедуры завершает работу. В противном случае происходит переход по метке SRCH к началу поиска элемента.
Поскольку слова отстоят друг от друга на расстояние двух байт, при делении отрезка пополам полученный индекс приводится к четному значению. Поиск считается неудачно завершенным, если индекс уменьшился до 2. В начале поиска из первого элемента извлекается количество слов массива и дополняется до ближайшего четного значения.
Затем полученный индекс SI добавляется к адресу начала массива DI. В результате происходит перемещение указателя на середину массива. Средний элемент сравнивается с искомым. Если элемент не равен искомому, поиск продолжится в левой или в правой половине массива.
В обоих случаях проверяется индекс на равенство 2 (признак окончания поиска), выполнение деления индекса SI пополам и дополнение его до ближайшего четного значения. Однако при поиске в левой половине текущий индекс SI вычитается из текущего адреса DI, а при поиске в правой половине – складывается с ним.

ARR DW ? ; начальный адрес списка в памяти


BINSRCH PROC


CMP AX, [DI+2] ; сравнение искомого элемента с первым
JA LAST ; искомое значение превосходит первый элемент
LEA SI, [DI+2] ; иначе извлекаем адрес первого элемента
JE EXITF ; искомый элемент равен первому
STC ; устанавливаем флаг CF (элемент не найден)
EXITF: RET ; выход из подпрограммы
LAST:MOV SI, ES:[DI] ; определяем количество элементов
SHL SI, 1 ; умножаем на 2
ADD SI, DI ; перемещаем указатель на последний элемент
CMP AX, ES:[SI] ; сравнение искомого элемента с последним
JB SRCH ; искомый элемент меньше последнего
JE EXITL ; искомый элемент равен последнему
STC ; устанавливаем флаг CF (элемент не найден)
EXITL: RET ; выход из подпрограммы

SRCH:MOV ARR, DI ; сохранение в памяти адреса начала массива


MOV SI, [DI] ; определяем количество элементов
EVEN:TEST SI, 1 ; проверка на четность индекса
JZ ADDL ; да, индекс четный
INC SI ; приводим индекс к четному значению
ADDL:ADD DI, SI ; определяем индекс середины массива
CMPL:CMP AX, [DI] ; сравниваем искомый элемент со средним
JE EXIT ; если средний элемент равен искомому, выход
JA HIGH ; искомый элемент больше
CMP SI, 2 ; сравниваем индекс с 2
JNE SHRL ; индекс больше 2
NO:STC ; устанавливаем флаг CF (элемент не найден)
JE EXIT ; выход из подпрограммы
SHRL:SHR SI, 1 ; делим индекс пополам
TEST SI, 1 ; проверка на четность
JZ SUBL ; индекс четный
INC SI ; делаем индекс четным
SUBL:SUB DI, SI ; перемещаем указатель назад
JMP CMPL ; переход на очередную проверку
HIGH: CMP SI, 2 ; сравниваем индекс с 2
JE NO ; искомый элемент не найден
SHR SI, 1 ; делим индекс пополам
JMP EVEN
EXIT:MOV SI, DI ; сохраняем адрес последнего сравнения в SI
MOV DI, ARR ; восстанавливаем адрес начала списка
RET ; выход из подпрограммы
BINSRCH ENDP

Download 1,87 Mb.

Do'stlaringiz bilan baham:
1   ...   80   81   82   83   84   85   86   87   ...   119




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish