V: С, Ф Со (знаковое переполнение)

х=у: Z

хФу: Z

х<у: N®V

хйу: {N®V) + Z

х>у: {N=V)Z

х>у: N=V

х<у: С1

х<у: CZ

х>у: C,Z

хку: С,

2.12. Обнаружение переполнения

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

Знаковое сложение и вычитание

Если в результате сложения и вычитания целых чисел произошло переполнение, то, как правило, старший бит результата отбрасывается и сумматор выдает только младшие биты. Переполнение при сложении целых знаковых чисел возникает тогда и только тогда, когда операнды имеют одинаковые знаки, а знак суммы противоположен знаку операндов. Удивительно, но это правило справедливо даже тогда, когда в сумматоре был выполнен перенос, т.е. при вычислении суммы х + у + 1. Данное правило играет важную роль при сложении знаковых целых чисел, состоящих из нескольких слов, так как в этом случае последнее сложение представляет собой знаковое сложение двух полных слов и бита переноса, значение которого может быть равно О или +1.

Дня доказательства этого правила предположим, что слагаемые хиу представляют собой целые знаковые значения, состоящие из одного слова, а бит переноса с равен О или I. Предположим также для простоты, что сложение выполняется на 4-разрядной машине. Если х иу имеют разные знаки, to-8SxS-1 и05у<7 (аналогичные границы получаются и при отрицательном у и неотрицательном х). В любом случае после сложения этих неравенств и необязательного добавления с получим -8<х + у+с<7.

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

Теперь предположим, чтох и у имеют одинаковые знаки. Здесь возможны два случая.

(а) (б)

-8<х<-1 0<х<7

Таким образом:

(а) (б)

-\6<х + у+с<,-\ 0<jc + y + c<15

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

(а) (б)

-16<JC + y+c<-9 8<Jc + y+cS15

В случае (а) старший разряд 4-битовой суммы равен О, т.е. противоположен знакам х иу. В случае (б) стший бит 4-битовой суммы равен 1, т.е. также противоположен знакам х иу.

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

Это приводит нас к следующему выражению предиката наличия переполнения (помещающему результат в бит знака). Беззнаковый или знаковый сдвиг вправо на 31 бит дает нам результат в виде чисел 1/0 или -1/0.

х + у+с х-у-с

{х = у)&.[{х + у+с)®х) {х®у)&.[{х-у-с)®х)

{{х + у+с)®х)Щх + у + с)®у) [{х-у-с)®х)&{{х-у-с)у)

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

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

х+у+с х-у-с

z<-(xsy)&0x80000000 г <-(x® у) & 0x80000000

{{x + y+c)®x)&.{{x®z) + y+c) = y [х® y)&.[(x®z)-у -с)® у

Присваивание в левом столбце устанавливает значение z равным 0x80000000, если знаки х иу одинаковы, и О в противном случае. Таким образом, во втором выражении слагаемые имеют противоположные знаки и переполнение возникнуть не MOJiler. Если их иу неотрицательны, значение знакового бита в результате во втором выражении будет равным 1 тогда и только тогда, когда (jc-2") + y+cS0, т.е. если jc + y+c&2, что и представляет собой условие возникновения переполнения при вычислении х + у+с. Если их hj отрицательны, то значение бита знака во втором выражении будет равным 1 тогда и только тогда, когда (jc+2") + y+c<0, т.е. если х + у+с<-2\ что также представляет собой условие

переполнения при вычислении х + у+с. Член х = у гантирует корректность результата (равный О знаковый бит), если хиу имеют разные знаки. Условия переполнения ддя разности (приведенные в правом столбце) получаются аналогично. Для реализации этих формул понадобится выполнить девять команд из базового множества RISC.

Может показаться, что использование значения разряда переноса дает эффективный алгоритм проверки на переполнение в случае знакового сложения, но на самом деле это не так. Однако есть еще один метод.

Еслих-целое знаковое число, то х + 2" представляет собой корректное беззнаковое число, которое получается в результате инвертирования старшего бита х. При сложении положительных знаковых чисел переполнение возникает тогда, когда х + у>2", т.е. если (х + 2) + (у + 2") S 3 • 2. Последнее выражение означает, что при сложении беззнаковых операндов был перенос (так как сумма не меньше 2) и старший бит суммы равен 1. Аналогично, при сложении отрицательных чисел переполнение возникает тогда, когда значение разряда переноса и значение старшего разряда суммы равны 0.

Это дает нам следующий алгоритм обнужения переполнения при знаковом сложении.

Вычисляем (хФ2") + (у Ф2") и получаем сумму s и значение бита переноса с.

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

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

При вычитании используется такой же алгоритм, с тем отличием, что на первом шаге вместо суммы вычисляется разность. Мы считаем, что перенос в данном случае генерируется при вычислении х-у как х + у + 1. Полученная разность представляет бой корректный результат знакового вычитания.

Несмотря на то что рассмотренные методы крайне интересны, на многих компьютерах они работают не так эффективно, как методы без использования переноса (например, вычисление переполнения как (х = у)&(*Фх) для сложения и (хФу)&(Фх) для вычитания, где S и </ - соответственно сумма и разностьх иу).

Установка переполнения при знаковом сложении и вычитании

Зачастую переполнение при сложении знаковых операндов устанавливается посредством правила: "перенос в знаковый разряд отличается от переноса из знакового разряда". Как ни удивительно, но эта логика позволяет корректно определять переполнение как при сложении, так и при вычитании, считая, что разность х-у вычисляется как X + У+1. Более того, это утверждение корректно независимо от того, был ли перенос или заем либо нет. Конечно, то, что перенос в знаковый разряд легко вычислить, вовсе не означает, что существуют эффективные методы определения знакового переполнения. В случае сложения и вычитания перенос/заем формируется в знаковом разряде после вычисления приведенных ниже выражений (здесь с равно О или 1).

Перенос: Заем:

(х + у+с)ФхФу (х-у-с)ФхФу

В действительности для каждого разряда i эти выражения дают перенос/заем в разряд i.