Оглавление
§ Матчасть
Представим ситуацию: надо сравнить 2 числа и проверить, меньше ли одно число, чем второе число. Для простоты возьмем два 8-битных числа A и B и сравним:
Если в результате A меньше чем B, то так и говорим, что оно меньше, причем, A и B могут быть отрицательными или положительными. С точки зрения математики, можно из левой и правой части уравнения вычесть число B:
И получится весьма важное уравнение, которое гласит, что если A меньше чем B (1.1), то тогда разность этих чисел будет меньше чем 0 (1.2).
§ Несколько примеров
Теперь можно проверить несколько примеров сравнений:
1 < 2 | 1 - 2 = -1 | Меньше
2 < 1 | 2 - 1 = +1 | Больше (не меньше)
2 < 2 | 2 - 2 = +0 | Равно (но не меньше)
-1 < -2 | -1 - (-2) = +1 | Больше (не меньше)
-4 < 5 | -4 - 5 = -9 | Меньше
Для процессора результат "меньше" означает, что в старшем бите результата есть 1, и после инструкции SUB (или CMP – инструкция только вычитает, но не пишет результат в операнд-назначение) устанавливается флаг SF, ZF и остальные. В данном случае пока что интересует флаг SF, и если он равен 1, то левый операнд, даже если он был со знаком, меньше чем правый операнд.
Но не всё так просто, поскольку существует одна проблема: числа в одном байте (тип signed char) строго ограничены диапазоном от -128 до 127. При попытке, допустим, вычесть из -128 единицу, вместо -129 мы получаем 127. Здесь мы говорим о таком явлении как переполнение знакового значения. Как это получается? Дело в том что число -128 представляется в двоичном виде вот так:
-127 | 10000001
-128 | 10000000 <== максимальное отрицательное
127 | 01111111 <-- максимальное положительное
Почему оно является максимальным отрицательным? Все дело в знаке, который всегда находится в самом старшем бите. Так как процессор имеет дело с числом, представленном в дополненном коде, то в любом случае старший бит отвечает за знак, и если он 1, то это значит то, что число идёт со знаком "минус".
§ Учёт переполнения
Но что же делать, если всё-таки надо корректно сравнить два знаковых числа? Давайте возьмем пример двух чисел:
По идее, да, если мы бы вычли из -128 число 1, то получилось бы -129, что явно меньше нуля. Но так как операция вычитания идёт в 8-битном операнде, то в старшем бите вместо 1 мы получаем 0, а само значение будет 127. Однако, процессор после такой операции определяет что было переполнение, и ставит флаги SF=0 (положительный результат) и OF=1 (переполнение результата).
Это важно учитывать в сравнениях со знаком. Установленный флаг переполнения говорит всегда о том, что:
- Результат получился с ошибочным знаком
- Отсюда следует, что если нам нужен правильный знак, надо инвертировать (отрицание бита) значение в
SF, чтобы узнать корректный результат
По итогу, для полностью корректного сравнения надо учитывать флаг и SF и флаг OF. Рассмотрим все 4 варианта получения данных флагов:
OF SF | Результат сравнения
======+=======================
0 0 | 0 - больше или равно
0 1 | 1 - меньше
------+---------------------
1 0 | 1 - меньше
1 1 | 0 - больше или равно
Если рассуждать логически, то при получении SF=0 мы знаем что итоговый результат получается либо 0, либо положительное число. В случае если OF=0, то никаких проблем с переполнением не наблюдается, так что при установленном результате SF=1 также гарантированно установлено что результат является отрицательным. При достижении OF=1 результат SF считается неверным и потому его значение проходит этап инверсии, чтобы определить корректное значение сравнения. Собственно говоря, это и видно в представленной выше таблице.
Отсюда вывод: если SF != OF либо же SF ^ OF = 1, то левый операнд меньше правого, иначе левый операнд либо равен правому, либо больше.
§ Вычисления переполнения
Ранее в тексте я не раз упомянул о том, что процессор умеет определять тот момент, когда при сложении или вычитании чисел получается переполнение и сейчас я разберу то, как это получается и почему.
Для начала необходимо найти все возможные комбинации. Поскольку рассматриваем только знак числа, то составим таблицу из 3 входов: знака операнда A, операнда B и результата R. Как и всегда, если знак (-) то это 1, иначе если (+), то это 0.
A B | R | ПРИМЕР: A + B | ИТОГ | OF | РАССУЖДЕНИЕ
====+===+=================+=======+=====+========================
0 0 | 0 | (+5) + (+1) | +6 | 0 | Плюс + Плюс = Плюс
0 0 | 1 | (+127) + (+1) | -128 | 1 | Плюс + Плюс = Минус (!)
0 1 | 0 | (+64) + (-1) | +63 | 0 | Плюс + Минус = Плюс
0 1 | 1 | (+0) + (-128) | -128 | 0 | Плюс + Минус = Минус
1 0 | 0 | (-64) + (+128) | +64 | 0 | Минус + Плюс = Плюс
1 0 | 1 | (-32) + (+1) | -31 | 0 | Минус + Плюс = Минус
1 1 | 0 | (-128) + (-1) | +127 | 1 | Минус + Минус = Плюс (!)
1 1 | 1 | (-64) + (-32) | -96 | 0 | Минус + Минус = Минус
Из таблицы видно что из всех возможных 8 комбинации переполнение произошло только в 2х случаях:
- Когда при сложении двух положительных значений мы получили отрицательное
- Либо, когда при сложении двух отрицательных мы получили положительное
Что в обоих случаях является заведомо ложным ответом. Как же составить логическую функцию для вычисления флага переполнения? Можно обратить внимание что условие переполнения становится истинным когда A = B. С логической точки зрения, это эквивалент булевой функции not(A xor B) = 1 xor (A xor B) = (A ^ B ^ 1). Но этого недостаточно, потому что такая функция выдает 4 значения из 2, и значит, тут еще надо учесть результат R.
Также обратим внимание, что OF=1 в двух ситуациях: либо если A != R либо если B != R, а поскольку по условию у нас A=B, то не имеет значения, что брать в уравнение, A или B, так что берем A != R. Так как это соответствует булевой функции A xor B = A ^ B, и объединяя условия друг с другом, получается следующая логическая функция, которая и будет функцией вычисления флага переполнения при операции сложения:
OF = (A ^ B ^ 1) & (A ^ R)
Но это лишь половина, поскольку, помимо сложения, для знаковых сравнений требуется именно флаг переполнения после вычитания.
§ Переполнение при вычитании
Если поменять знак у второго операнда при сложении, то мы получим вычитание:
Развернуть знак, соответственно, можно при помощи инверсии через xor, и формула определения переполнения для сложения станет немного иной.
OF = (A ^ B ^ 1) & (A ^ R)
OF = (A ^ (B ^ 1) ^ 1) & (A ^ R)
OF = (A ^ B) & (A ^ R)
Несмотря на очевидный вывод, я все-таки приведу новую таблицу, чтобы продемонстрировать истинность этого выражения.
A B | R | ПРИМЕР: A - B | ИТОГ | OF | РАССУЖДЕНИЕ
====+===+=================+=======+=====+========================
0 0 | 0 | (+5) - (+1) | +4 | 0 | Плюс - Плюс = Плюс
0 0 | 1 | (+10) - (+20) | -10 | 0 | Плюс - Плюс = Минус
0 1 | 0 | (+64) - (-1) | +65 | 0 | Плюс - Минус = Плюс
0 1 | 1 | (+0) - (-128) | -128 | 1 | Плюс - Минус = Минус (!)
1 0 | 0 | (-128) - (+1) | +127 | 1 | Минус - Плюс = Плюс (!)
1 0 | 1 | (-32) - (+1) | -33 | 0 | Минус - Плюс = Минус
1 1 | 0 | (-128) - (-1) | -127 | 0 | Минус - Минус = Плюс
1 1 | 1 | (-64) - (-32) | -32 | 0 | Минус - Минус = Минус
Как и в предыдущей таблице, переполнение может произойти в следующих двух ситуациях:
- Если из положительного значения вычесть отрицательное, то по законам математики, должно будет получиться положительное, но в итоге получилось отрицательное значение, что является признаком переполнения
- Аналогично, если из отрицательного вычесть положительное, то должно получиться тоже отрицательное, но если итоговый результат стал положительным числом – это переполнение
Для этой ситуации мы говорим о том, что первой компонентой булевой функции будет A != B, а второй компонент строго только A != R (либо B = R):
На этом тема о переполнениях и знаковых сравнениях завершена.