зующая данный алгоритм, приведена в листинге 4.4. Здесь за пределы цикла можно вынести вычисление подвыражения Ь & d, а кроме того, работу программы можно ускорить следующей инициализацией:

m = 0x80000000 » п1г(b & d);

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

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

unsigned m, temp;

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

if (b & d & m) {

temp = (b - m) if (temp >= a) temp = (d - m) if (temp >= c)

m = m >> 1;

return b I d;

(m - 1) ; b = temp; break;}

(m - 1) ; d = temp; break;}

Определить диапазон значений выражения х&у , где границы хиу определены неравенствами (9), можно с помощью двух методов: алгебраического и непосредственного вычисления. В основе алгебраического метода лежит закон де Моргана (DeMorgan):

х&у=(Ьу).

Поскольку мы знаем, как определить точные границы выражения х (у, границы х&у

ii и ii ii

вычисляются тривиально с помощью команды не (а<х<Ь -J><-x<-a):

tmnAND{a,b,c,d) = -<msKOR{-I>,-a,-d,-£), niaxAND(fl,6,c,d) = -,rmnOR{-I>,-a,-d,-£).

Код вычисления этих функций, приведенный в листингах 4.5 и 4.6, очень похож на код вычисления границ выражения с или.

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

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

unsigned m, temp;

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

if (-a & -c & m) {

temp = (a I m) & -m;

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

temp =1 (с j m) £q -m;

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

m = ra >> 1;

return a & c;

Листинг 4.6. Вычисление верхней границы х&.у

unsigned maxAND(unsigned a, unsigned b, unsigned c, unsigned d)

unsigned ra, temp;

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

if (b Sc ~d Sc m)

temp = (b Si -m) (m-1) ;

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

else if (~b Sc d Sc m) {

temp = (d Si ~m) (m-1) ;

if (temp >= c) {d и temp; break;}

m = m >> 1;

return b Si d;

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

min (х Ф у) = min ((х &-,у) (-ч* & у)).

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

Для вычисления границ выражения с исключающим или можно использовать следующие выражения:

minXOR (я, 6, с, d) = minAND (я, 6,-.rf,) I min AND (-Л,-л, с, d), тяхХОН(я,6,с,</) = тахОН(0,тахАШ(я,6,-</,-<;),0,maxAND(-*,-Ta,c,d)).

Значения minXOR и maxOR несложно вычислить непосредственно. Код для вычисления minXOR такой же, как и для вычисления minOR (см. листинг 4.3), нужно лишь удалить два оператора break, а в последней строке заменить возвращаемое значение на а * с. Код для вычисления maxXOR тот же, что и для вычисления maxOR (см. листинг 4.4), за исключением того, что четыре строки после onqjaTqja if необходимо заменить фрагментом

temp = (b - m) (m - 1) ; if (temp >= a) b = temp; else {

temp = (d - m) (m - 1) ; if (temp >= c) d = temp;

Кроме того, возвращаемое значение нужно заменить на Ь * d. Знаковые границы

Вычисление целых знаковых границ для логических выражений значительно усложняется. Вычисления границ зависят от расположения числа О по отношению к заданным диапазонам (от а до и от с до г/), и для каждого частного случая используются свои формулы. В табл. 4.1 приведен один из методов вычисления верхней и нижней границ выражения х\у. Если значение переменной больше или равно О, в соответствующей графе таблицы стоит знак "плюс", если значение переменной меньше О - знак "минус". Под заголовком minOR приведены выражения, вычисляющие нижнюю границу х \ у для данных диапазонов, а под заголовком maxOR - формулы для вычисления верхней границы. Вычислить верхнюю и нижнюю границы выражения х \ у можно следующим образом: из битов знаков чисел а,Ь,сий составляется 4-битовое число, значение которого находится в пределах от О до 15, и используется оператор выбора switch. Обратите внимание, что будуг задействованы не все значения от О до 15, так как невозможны ситуации, когда а>Ь или od .

Для знаковых чисел справедливо отношение

а<х<Ь « -Ь<-х<-а ,

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

Таблица 4.1. Вычисление знаковых функций minOR и nraxOR с помощью беззнаковых