Беззнаковое сложение/вычитание

При беззнаковом сложении/вычитании для вычисления предикатов переполнения можно использовать следующий метод без переходов, результат работы которого помещается в знаковый разряд. Методы, использующие команды сдвига вправо, эффективно работают только тогда, когда известно, что с = О. Выражения в скобках вычисляют перенос или заем, который появляется из младшего разряда.

Беззнаковое вычисление х + у+с:

(х&у)\{{х\у)&{х + у+с))

Беззнаковое вычисление х-у-с: (&у)((дг = у)&(дг-у-с)) (&у)((у)&(ж-у-с))

у»1

ryj&c

&1

В [46] для беззнаковых сложения и вычитания есть существенно более простые формулы, использующие команды сравнения. При беззнаковом сложении переполнение (перенос) возникает, если полученная сумма меньше (при беззнаковом сравнении) любого из операндов. Эта и подобные формулы приведены ниже. К сожалению, нет возможности обобщить эти формулы для использования в них переменной с, которая представляет собой перенос или заем. Вместо этого приходится сначала проверять значение с, а затем, в зависимости от того, равно оно О или 1, использовать одно из следующих типов сравнений (напомним - вычисления сумм и разностей беззнаковые).

х+у х+у+1 х-у х-у-\

-л<у х + у<х

-<у х + у + \<х

х<у

х-у>х

х<у

х-у-Их

В каждом из приведенных случаев перед выполнением сложения/вычитания вычисляется первая формула, которая проверяет, возможно ли переполнение, не вызывая при этом самого переполнения. Вторая формула вычисляется после вьшолнения сложения/вычитания, при которых возможно переполнение.

Для случая знакового сложения/вычитания аналогичного (с использованием сравнений) Простого метода проверки, похоже, не существует.

Умножение

При умножении переполнение означает, что результат не помещается в 32 разрядах (результат как знакового, так и беззнакового умножения 32-битовых чисел всегда может быть представлен в виде 64-битового числа). Если доступны старшие 32 разряда произведения, то определить, имеет ли место переполнение, очень просто. Пусть Ы(лгху) и lo(jcxу) - старшая и младшая половины 64-битового произведения. Тогда условия переполнения можно записать следующим образом [46].

Беззнаковое произведение хху : Ы{хху)0

Знаковое произведение хху. M(jcxy)?61o(jcxy)»3lj

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

Переполнение при умножении имеет место, если приведенные ниже выражения истинны.

Беззнаковое умножение: z<-jc*y

Знаковое умножение: z<-JC*y

{у<0&х = -2)\[у*0&.г-У*х)

y*0&z*y*x

Затруднения возникают при х = -2" и при у = -1. В этом случае при умножении будет переполнение, но результат может получиться равным -2. Такой pesyjaTaT приводит к переполнению при делении, и таким образом оказывается возможным любой результат (на некоторых машинах). Поэтому да1шый частный случай должж проверяться отдельно, что и делается добавлением члена (у < О & ж = -2"). Чтобы в приведенных выше выражениях предотвратить деление на О, используется оператор "условного и" (в языке С - оператор ьь).

Можно также использовать проверку делением без выполнения самого умножения (т.е. без генерации переполнения). При беззнаковом умножении переполнение возникает тогда и только тогда, когда лу>2--1, или jc> ((2"-l)/y), или, поскольку х- целое число, х> (2-l)/y . В обозначениях компьютерной арифметики это выглядит следующим образом: уФО&х> OxFFFFFFFF+y .

Для целых знаковых чисел переполнение в результате умножения хиу определить сложнее. Если операнды имеют одинаковые знаки, то переполнение будет тогда и только тогда, когда ху > 2" -1. Если хиу имеют противоположные знаки, то переполнение будет тогда и только тогда, когда ху < -2" . Эти условия могут быть проверены с помощью знакового деления (табл. 2.2).

Таблица 2.2. Проверка иа переполнение произведения знаковых операндов

Как видно из таблицы, при проверке необходимо учесть четыре возможных случая. Вследствие проблем переполнения и представления числа +2 с объединением этих выражений могут возникнуть трудности.

В случае доступности беззнакового деления тест можно упростить. Если использовать абсолютные значения хиу, которые корректно представимы в виде целых чисел без знака, то весь тест можно записать так, как показано ниже. Переменная с имеет значение 2" -1, еслих и у имеют одинаковые знаки, и 2" в противном случае.

(x = y)»31j + 2" x<-abs(x)

y<r-abs{y)

y*0&.x>

Чтобы выяснить, будет ли переполнение при вычислении произведения х*у , можно использовать команду, вычисляющую количество ведущих нулей у операндов. Способ, основанный на использовании этой функции, позволяет более точно определить условие переполнения. Сначала рассмотрим умножение беззнаковых чисел. Легко показать, что если дг и у - 32-разрядные величины, содержащие тип ведущих нулей соответственно, то в 64-разрядном произведении будет т + п или т + п + 1 ведущих нулей (или 64, если лг = О или у = О). Переполнение возникает тогда, когда в 64-разрядном произведении количество ведущих нулей оказывается меньше 32. Из этого следует:

если п1г(лг) + nlz(y) > 32, переполнения точно не будет; если nlz(jf)+nlz(y) < 30, переполнение точно будет.

Если же nlz(jf)+nlz(y) = 31, то переполнение может быть, а может и не быть. Чтобы узнать, будет ли переполнение в этом частном случае, вычисляется значение t = x[y/2j (переполнения при этом вычислении не возникает). Поскольку ху равно 2t (или 2t + x, если у нечетно), переполнение при вычислении ху будет в том случае, когда ? > 2". Все это приводит к коду, показанному в листинге 2.2, который вычисляет значение произведения ху с проверкой переполнения (в этом случае выполняется переход к метке overflow).

Листинг 2.2. Беззнаковое умножение с проверкой переполнения

unsigned х, у, z, m, n, t;

m = nlz(x);

n = nlz(y);

if (m + n <= 30) goto overflow; t = X* (y » 1) ;

if ((int)t < 0) goto overflow; z = t * 2; if (y Sc 1) { Z = Z + X;

if (z < x) goto overflow;

В z содержится произведение x и у.

При знаковом умножении условие переполнения можно определить через количество ведущих нулей положительных аргументов и количество ведущих единиц отрицательных аргументов. Пусть 1я =nlz(jf)+nlz(jc) и и = nlz(y) + nlz(y),тoгдa:

если m + и > 34, переполнения точно не будет; если я + и < 31, переполнение точно будет.

Остались два неоднозначных случая - 32 и 33. В случае m +и = 33 переполнение возникает только тогда, когда оба Ефгумента отрицательны и произведение равно в точности 2 (машинный результат равен -2), так что распознать эту ситуацию можно при помощи проверки корректности знака произведения (т.е. переполнение будет, если 1яФиФ(я*и)<0). Для случая т+п = 32 определить наличие переполнения не так просто.