Формулы для отрицания можно получить из выражений для разности знаковых чисел в предположении а = Ь = 0, отбросив ряд невозможных комбинаций, переименовав переменные и проведя некоторые упрощения.

a=-.2",fc = -2": -х = -2" а = -2", b * -2" : -2" < -ж < 2* -1 аэ-г": -Ьйх<-а

Программа на языке С, вычисляющая границы арифметических выражений, несколько сложновата, поэтому рассмотрим только код определения диапазона значений суммы двух знаковых операндов. По-видимому, проще всего выполнить гфоверку границ в двух случаях из (8) - когда нижняя и верхняя границы равны крайним отрицательному и положительному числам соответственно. Переполнение в отрицательном направлении имеет место, есяи оба операнда отрицательны, а их сумма- неотрицательна (см. раздел 2.12). Таким образом, дтя проверки условия а + с <-2 сначала необходимо вычислить сумму s г= а + с;, а затем использовать код наподобие if (а<0 && с<0 && s>=0) .... Однако программа будет более эффективной, если все логические операции будут выполняться непосредственно над £фиф-метическими переменными, при этом результат будет находиться в бите знака. Тогда рассмотренное условие можно представить иначе: if ((а & с & -s) < 0).... Таким образом, получаем фрагмент кода, приведенный в листинге 4.2.

Листинг 4.2. Определение границ знакового сложения

S = а + c,• t = b + d;

u = а & с & -s & ~ (b & d Sc ~t) ; V = ((a с) I ~(a s)) Sc (-b Sc ~d & t) ; if ( (u I v) < 0)

S = 0x80000000; t = 0X7FFFFFFF;

Переменная u имеет значение true (т.е. бит знака равен 1), если при вычислении а + с происходит переполнение в отрицательном направлении, а при вычислении b + d переполнения в отрицательном направлении нет. Переменная v имеет значение true, если при вычислении а + с переполнения нет, а при вычислении b + d имеет место переполнение в положительном направлении. Первое условие можно записать как "а и с имеют разные знаки, или а и S имеют один и тот же зншс". Проверка if ((uv)<0) эквивалентна проверке if (и<01 I v<0), т.е. если истинно или и, или v (или оба одновременно).

4.3. Определение границ логических выражений

Как и в гфедыдущем разделе, предположим, что границы двух переменных л: и у задаются следующим образом (все величины беззнаковые):

а<х<Ь, c<y<d.

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

Необходимо определить компактные границы выражений х\у, х&.у, х®у и -х.

Комбинируя неравенства (9) с неравенствами из раздела 2.3 и учитывая, что -л = 2" -1 - JC, получим

niax(a,c) й[х\у)<Ь +d,

Ou{x+y)<mn{b,d), 0<{x®y)ub+d, -iu-x<-a,

где предполагается, что при сложении b+d переполнения не возникает. Эти формулы легко вычисляются и достаточно эффективны для использования в компиляторах, о чем упоминалось в предыдущем разделе. Однако границы в первых двух неравенствах не являются компактными. Пусть, например, диапазон значений переменных х и у в двоичной записи задан следующим образом:

00010Sx< 00100, 01001<у<10100.

После проверки (перебора всех 36 возможных комбинаций значений хиу) получим, что 01010 < (х I у) < 10111, т.е. нижняя граница не равна ни тах(я,с), ни я с ; верхняя граница также не равна ни b+d, ни b\d .

Можно ли определить компактные границы логических выражений, если известны значения а, Ь, с и d из (9)? Давайте сначала найдем минимальное значение выражения х\у. Естественно предположить, что значение этого выражения будет минимальным при минимальных значениях хиу, равным я с . Однако, как видно из примера (10), минимальное значение на самом деле может оказаться меньше предполагаемого.

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

Процедура состоит в сканировании битов а и с слева направо. Если оба бита равны О, то в соответствующем разряде результата будет 0. Если оба бита равны 1, то и соответствующий бит результата будет равен 1 (очевидно, никакие другие значения X и у не могут уменьшить полученный результат). В обоих этих случаях переходим к сравнению следующих разрядов. Если в следующем разряде одной из границ содержится единичный бит, а у другой границы - нулевой, то, возможно, замена О на 1 в этом разряде и установка всех следующих за ним битов в О снизит значение я с . Такое изменение границ не может увеличить значение я с , так как в любом случае в этом разряде результата 6y,!ieT 1 за счет другой границы. Итак, мы формируем число с нулевым битом, замененным на единичный, а все последующие биты этого числа заменяем нулями. Если полученное таким образом число меньше или равно соответствующей верхней границе, такая замена возможна. Выполним эту замену, а затем применим операцию или к полученному значению и другой нижней границе. Если же после описанной замены битов новое значение нижней границы оказалось больше верхней, то такая замена невозможна, и мы переходим к следующим битам.

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

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

Программа на языке С для данного алгоритма представлена в листинге 4.3. Предполагается, что оптимизирующий компилятор вынесет вычисление подвыражений ~а&с и а&~с за пределы цикла. Если у нас есть функция вычисления количества ведущих нулевых битов, код можно ускорить, инициализируя m следующим образом:

m = 0x80000000 >> nl2(a*c);

При этом в а * с опускаются те разряды, в которых изначально у обеих констант оба бита равны О или оба равны 1. Это ускорение работы программы будет особенно эффективным при а*с равным О (т.е. если а = с); при этом сдвиг вправо должен выполняться по модулю 64. Если функции nlz в вашем распоряжении нет, можно воспользоваться одной из версий функции flp2 (см. раздел 3.2) с аргументом а * с.

Листинг 4.3. Вычисление нижней границы х \ у

unsigned minOR(unsigned а, unsigned b, unsigned с, unsigned d)

unsigned m, temp;

m = 0x80000000; while (m != 0)

{ ,

if (~a Sc с Sc m)

temp = {a I m) Si -m;

if (temp <= b) {a = temp; break;}

else if (a Si ~c Si m) {

temp = (c I m) Si -m;

if (temp <= d) {c = temp; break;}

m = m >> 1;

return a I c;

Рассмотрим теперь алгоритм поиска максимального значения "выражения х\у, где, как и ранее, значения переменных ограничены неравенствами (9). Этот алгоритм аналогичен алгоритму поиска минимального значения. Верхние границы поразрядно сканируются слева направо до тех пор, пока в некоторой позиции биты в b и d не окажутся равными единицам. Если такая позиция обнаружена, алгоритм пытается увеличить значение b\d , уменьшая одну из границ заменой в соответствующем разряде 1 на О и заменяя все последующие биты единичными. Если такая замена корректна (т.е. полученное таким образом новое значение верхней границы не ниже соответствующей нижней границы), то изменения принимаются. Если же замена оказывается некорректной, пытаемся изменить другую границу. Если и эта замена некорректна, сканируются следующие биты. Программа на языке С, реали-