Операции и флаги (1110644)

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

Текст из файла

А. А. ВылитокОперации над битовыми наборами.Установка флагов и проверка условий1. Определение операций сложения и вычитания битовых наборовБитовые наборы используются для представления данных в ЭВМ, в частностидля представления чисел. Сами наборы можно считать словами в алфавите {0, 1}.Сначала мы формально определим операции сложения и вычитания на множествебитовых наборов длины k. Затем исследуем связь этих операций с операциямисложения и вычитания чисел.Пусть x и y — битовые наборы. Перенумеруем биты наборов справа налево от 0до k − 1.

Через zi будем обозначать i-й бит набора z, zi ∈ {0, 1}. Для определениярезультатов (суммы и разности) воспользуемся некоторыми логическими операциями(дизъюнкция, конъюнкция, отрицание, сложение по модулю два), интерпретируя 0 какложь, 1 — как истину.Суммой (соответственно, разностью) битовых наборов x и y назовем набор z,разряды которого определяются ниже. Попутно определим набор величин ci, i = 0, …, k,ci ∈ {0, 1}, где ci означает наличие (при ci = 1) или отсутствие (при ci = 0) переносаединицы в i-й разряд, а в случае вычитания — заёма из i-го разряда. Операциювычисления суммы (соответственно, разности) битовых наборов назовем сложением(соответственно, вычитанием):сложениеz = x+ y⎧с0 = 0,⎪для i = 0, K , k − 1⎪⎨⎪ z i = xi ⊕ y i ⊕ c i ,⎪⎩ci +1 = xi y i ∨ xi ci ∨ y i ciвычитаниеz = x− y⎧с0 = 0,⎪для i = 0, K , k − 1⎪⎨⎪ z i = xi ⊕ y i ⊕ c i ,⎪⎩ci +1 = y i ci ∨ z i ci ∨ y i z iЗдесь ⊕ означает «сложение по модулю два», ∨ — дизъюнкцию, знакконъюнкции (логического умножения) опущен.Если рассматривать битовые наборы как представление беззнаковых целыхчисел или знаковых в дополнительном коде, то определенные выше операции надбитовыми наборами реализуют сложение и вычитание целых чисел по модулю 2k.

Вомногих ЭВМ схемы сложения и вычитания чисел устроены именно так. Поскольку приподобных операциях результат может быть искажен (из-за переполнения разряднойсетки или мантиссы), для отслеживания этой ситуации одновременно с результатомустанавливаются специальные флаги.2. Установка флагов при сложении и вычитанииФлаг — это бит, принимающий значение 1 («флаг установлен»), если выполненонекоторое условие, и значение 0 («флаг сброшен») в противном случае.

Наиболееупотребительны флаги:ƒCF — carry flag (флаг переноса) фиксирует искажение результатаоперации для чисел без знака (он устанавливается, например, когда1полученная сумма k-разрядных чисел «не умещается» в k-разряднуюячейку);ƒOF — overflow flag (флаг переполнения мантиссы) фиксирует искажениерезультата для знаковых чисел;ƒZF — zero flag (флаг нуля) фиксирует нулевой результат;ƒSF — sign flag (флаг знака) устанавливается в 1, если результат операциинад знаковыми числами отрицательный.Заметим, что сложение и вычитание битовых наборов приводит к установкезначений всех флагов, независимо от того, трактуем ли мы эти наборы как числа сознаком или как беззнаковые числа. Для анализа корректности результата в знаковомслучае бесполезен CF, для случая беззнаковых чисел бесполезны OF и SF.2.1. Формальное определение флаговПриведем формулы для определения значений флагов в терминах битовыхнаборов, используя введенные выше обозначения.

После сложения или вычитаниянаборов x и y (результат в z) флаги CF, SF, ZF, OF получают следующие значения 1):CF = ckSF = zk − 1⎧ x k −1 y k −1 z k −1 ∨ x k −1 y k −1 z k −1 при сложении ,ZF = z k −1 z k − 2 K z 0 , OF = ⎨⎩ x k −1 y k −1 z k −1 ∨ x k −1 y k −1 z k −1 при вычитании2.2. Смысловое определение флаговПравила установки значений флагов можно описать и в терминах беззнаковыхили знаковых (в дополнительном коде) чисел. В следующей таблице наборы x, y и zинтерпретируются как числа (со знаком или без знака), набор z — сумма или разность(по модулю 2k) наборов x и y, знаки +, − означают обычные (не по модулю 2k) операциисложения и вычитания над целыми числами.2)Условия установки значения флага в 0 или в 1 дляФлагбеззнаковых чиселзнаковых чисел0101ZFz≠0z=0z≠0z=0SFz∈[0, 2k − 1 − 1]z ∈ [2k − 1, 2k − 1]z≥0z<0при сложении:при сложении:при сложении:при сложении:x ≥ 0, у ≥ 0 илиx < 0, у < 0 илиxу ≤0, x+ y < 0xу < 0, x+ y ≥ 0x+ y < 2kx+ y ≥ 2kCF2при вычитании:при вычитании:при вычитании:при вычитании:x≥yx<yx < 0, у ≥ 0 илиx ≥ 0, у < 0 или1)Горизонтальная черта над переменными (надчеркивание) означает логическое отрицание.2)Доказательство эквивалентности правил, приведенных в таблице, и приведенных вышеформальных правил для битовых наборов, = предлагается в качестве упражнения.Условия установки значения флага в 0 или в 1 дляФлагбеззнаковых чисел01OFk−101x ≥ у ≥ 0 или 0 > x ≥ уx< у < 0 или 0 ≤ x < упри сложении ивычитании:при сложении ивычитании:−2k – 1≤ x ± y < 2k − 1x ± y < −2k − 1 илипри сложении:при сложении:x, y, z< (≥)2знаковых чиселилиx, y < (≥)2k−1,x < (≥)2k − 1 ≤ (>) yz ≥ (<)2k − 1при вычитании:при вычитании:x, y < (≥)2k−1 илиy, z < (≥)2k − 1,x, z < (≥)2k − 1,x ≥ (<)2k − 1x ± y ≥ 2k − 1y ≥ (<)2k − 12.3.

ПримерыПриведем для каждого допустимого набора значений флагов CF, SF, ZF, OFпример операций сложения и вычитания, после выполнения которых устанавливаетсяданный набор значений. Формат чисел во всех примерах — 1 байт. Операнды будемзаписывать в десятичной системе счисления, результат указывать и как число без знака, икак число со знаком.Составим таблицу: в правой колонке перечислим все возможные комбинациизначений флагов, слева для каждой комбинации будем выписывать по одному примеру насложение и на вычитание, если такие примеры существуют.Пример операции(сложение,вычитание)без знакасо знаком1+23+33–12+2Результат как числоне существует−80 − 50126+1260+0001–100не существуетне существует−40 + 20236−20−20 − 40196−60120 + 120240−16не существуетне существуетне существуетЗначение флагаCFSFZFOF00000001001000110100010101103не существуетне существует−2 + 31+140 − (−20)60+60140 + 14024+24не существует−1 + 100не существует−128 + (−128)00не существует−20 + (− 40)196−6020 − 40236−20не существует127 − 128255не существуетне существуетне существуетне существует−10111100010011010101111001101111011113.

Проверка условий с помощью вычитания и флаговПрактически во всех типах ЭВМ существуют команды перехода по условию.Многие такие команды укладываются в схему «Если op1 ‘ op2, то переход по адресу A»,где op1, op2 — операнды (битовые наборы длины k), ‘ — одна из операций отношения: −б,≠б , <б , >б , ≤б , ≥б , =зн , ≠зн , <зн , >зн , ≤зн , зн (здесь индекс «б» означает, что операндытрактуются как числа без знака, «зн» — со знаком).Пусть для представления знаковых чисел используется дополнительный код.Приведем метод, позволяющий проверить истинность условия op1 ‘ op2 по значениямфлагов (OF, CF, SF, ZF), получаемым при вычитании: op1 − op2 по модулю 2k.Поскольку разность (по модулю 2k) двух одинаковых чисел (знаковых илибеззнаковых) равна нулю, разность неравных чисел отлична от нуля и флаг ZF равенединице, если и только если результат операции — ноль, справедливы утверждения:op1 = op2 ⇔ ZF = 1,op1 ≠ op2 ⇔ ZF = 0.Итак, для того чтобы установить, равны или нет два числа, достаточно знать, чемуравен флаг ZF.Значения флагов при других соотношениях между операндами (кроме ≠ и =)различны в знаковом и беззнаковом случаях.

Поэтому рассмотрим эти случаи отдельно.Вспомним, что в терминах беззнаковых чисел флаг CF равен единице, еслиуменьшаемое меньше вычитаемого, и равен нулю в противном случае. Тогда можноутверждать, что:4op1 <б op2 ⇔ CF = 1,op1 ≥б op2 ⇔ CF = 0.Условия для остальных отношений можно логически выразить через ужеустановленные. Например, op1 >б op2 ⇔ (op1 ≥б op2 ) ∧ (op1 ≠ op2), где ∧ означаетконъюнкцию. Следовательно, op1 >б op2 ⇔ ( CF = 0) ∧ (ZF = 0).Для случая знаковых чисел нам важны флаги OF и SF 3). Посмотрим, какиезначения принимают эти флаги в зависимости от знаков операндов и от соотношений 4)между операндами:Возможноепри данныхзнакахсоотношениеВозможные значения флаговпри данном соотношении 5)OFSF<01≥0000110110<01≥00Знак op1Знак op2+++−≥−+<−−Проанализируем эту таблицу.

Заметим, что множества пар значений флагов (OF,SF) для отношений < и ≥ не пересекаются, а их объединение дает все возможные пары изнулей и единиц. Следовательно, по паре значений (OF, SF) можно определить, какое издвух взаимоисключающих соотношений (< или ≥) выполняется. В случае op1 < op2 имеем:либо OF = 0 и SF = 1, либо OF = 1 и SF = 0, или, короче, OF ≠ SF.

В случае op1 ≥ op2справедливо равенство OF = SF. Таким образом, можно утверждать:op1 <зн op2 ⇔ OF ≠ SF,op1 ≥зн op2 ⇔ OF = SFПодытожим полученные результаты в виде таблицы.Соотношениеop1 ‘ op2=Критерий истинности данного соотношения в терминах значений флаговпосле операции вычитания op1 − op2 по модулю 2kдля чисел со знакомдля чисел без знакаZF = 1ZF = 13)В «бесполезности» остальных флагов можно было бы убедиться, включив и их в рассмотрение, ноэто заняло бы больше места.4)Рассмотрим, как и в беззнаковом случае, только отношения < и ≥ — остальные можно выразить припомощи логических связок.5)Читателю предлагается самостоятельно доказать, что именно такие значения флагов возможны вкаждом из рассматриваемых случаев.5≠ZF = 0ZF = 0<OF ≠ SFCF = 1≥OF = SFCF = 0>(OF = SF) ∧ (ZF = 0)(CF = 0) ∧ (ZF = 0)≤(OF ≠ SF) ∨ ( ZF = 1)(CF = 1) ∨ ( ZF = 1)4.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов семинаров