а) б) в)

г) Д)

-128<*S127 x+128<255

х»7

х»1 = х»31

х»7

х»31

JC1C24 3>24 = jc

х»Ъ\

<127

Соотношения (б) и (в) получены непосредственно из предыдущего материала главы (в формуле (в) преобразование применено к значению х, сдвинутому вправо на 7 бит). Выражения (в)-{е) (а, возможно, и (ж)), вероятно, следует использовать, только если константы из (а) и (б) превышают размеры полей непосредственно задаваемых значений в командах сравнения и сложения.

Для еще одного частного случая проверки границ применимо преобразование

или в более общем виде

0<jt<2"-l«.

aSjt<a + 2"-l<=>

х:»п

(х-а)з>л

= 0.

4.2. Определение границ суммы и разности

Ряд оптимизирующих компиляторов в процессе работы выполняют анализ области значений выражений, который представляет собой процесс определения верхней и нижней границ значений ифметического выражения в программе. Хотя такая оптимизация реально не приводит к большому выигрышу, тем не менее она позволяет вносить в программу определенные улучшения, например избежать проверки диапазона в операторе выбора switch языка С или проверки значений индексов в режиме отладки.

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

а<х<Ь,

c<y<d.

Каковы в этом случае компактные границы значений выражений х+у , х-у и -х7 Очевидно, что арифметически a+cix + y<b + d. Но проблема в том, что при вычислении вполне может возникнуть переполнение.

Один из способов определения диапазона значений основан на следующей теореме.

4.2. ОПРЕДЕЛЕНИЕ ГРАНИЦ СУММЫ И РАЗНОСТИ

Теорема. Если а, b,c,d,xuy - беззнаковые целые числа, причем

aixib и ckykd.

0<JC + y<2"-l, еслиа + с22-1и + </>2\

а+сйх + уЬ +d в противном случае;

okx-ykl-1, eaiHO-d <Oiib-c>0,

a-d<x-y<b-c в противном случае;

0<-JC2"-l, fx,ima = Qw.b*Q,

-Ь<-х~а в протонном случае.

(4) (5) (6)

Неравенство (4) гласит, что значения суммы х + у обычно находятся в диапазоне от а+с до b+d . Однако если при вычислении b+d было переполнение, а при вычислении а + с переполнения не было, то нижней и верхней границами суммы х + у будут соответственно О и максимальное беззнаковое целое число. Выражения (5) интерпретируются аналогично, но значение истинной разности, меньшее О, означает, что имело место переполнение (в отрицательном направлении).

Доказательство. Пусть значения хиу находятся в указанных выше диапазонах. Если при вычислении обеих сумм - а + с и b+d - переполнения не было, то и при вычислении суммы х + у переполнения не будет и вычисленный результат будет правильным (что и утверждает второе неравенство из выражения (4)). Если же переполнение возникло при вычислении как а+с , так и * + d, то при вычислении х + у также произойдет переполнение. С арифметической точки зрения ясно, что

a + c-2ix+y-2ub+d-2.

Но именно так и выполняются вычисления в случае, когда переполнение происходит во всех трех суммах. Следовательно, и в этом случае

a+c<x + y<b+d .

Если при вычислении а + с переполнения нет, а при вычислении b+d - есть, то

а+с<2-\ и b + d>2\ Поскольку х + у может принимать все значения из диапазона от а+с до b + d, значение этой суммы находится между 2-1 и т.е. вычисленное значение суммы х+у будет находиться между 2-1 и О (хотя и не принимает все значения из указанного диапазона).

Случай, когда при вычислении а+с возникает переполнение, а при вычислении b+d не возникает, невозможен, поскольку а<Ь и cud .

Доказательство неравенств (4) завершено. Неравенства (5) доказываются аналогично, с тем отличием, «гю здесь "переполнение" означает, что истинное значение разности меньше 0.

При доказательстве неравенств (б) можно воспользоваться неравенствами (5), в которых о = А = 0, а затем переименовать переменные. (Выражение -х , гдех- беззнаковое число, означает вычисление значения 2- - х или -л +1 - что вам больше нравится.)

Поскольку беззнаковое переполнение легко распознается (см. раздел 2.12), полученные результаты несложно перевести в код, показанный в листинге 4.1, где вычисляется верхняя (переменная s ) н нижняя (переменная t) границы суммы и разности.

Листинг 4.1. Верхняя и нижняя границы беззнаковых суммы и разности

S = а + С; S = а - d;

t = b + d; t = b - с;

if (s >= a ScSc t < b) if (s > a ScSc t <= b)

S = 0; S = 0;

t = OxFFFFFFFF; t = OxFFFFFFFF;

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

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

а< хйЬ, ей у < d.

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

a + c<-l\b + d<-l. а+сйх+уйЬ+d

a + c<-2\b + d>-2: -2*S* + y <2"-1 -2"ua + c<2\b + d<2: a+c<x + yub + d (8)

-2"ua + c<2\b + d>2": -2"Sx + y <2"-l a + c>T\b + d>2: a+cux + y<b+d

Первая строка означает, что если при вычислении обеих сумм- а+с и b + d - было переполнение в отрицательном направлении, то вычисленная сумма х+у будет находиться между вычисленными суммами а+с и b+d, так как все три вычисленные суммы оказываются слишком велики на одну и ту же величину (2). Вторая строка означает, что если при вычислении суммы а + с происходит переполнение в отрицательном направлении, а при вычислении b + d переполнения либо не было, либо оно было в положительном направлении, то вычисленное значение суммы х+у находится между крайним отрицательным и крайним положительным числом (хотя и может принимать не все значения из указанного диапазона). Остальные строки интерпретируются аналогично.

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

a-d<-2",b-c<-2": a-dux-yub-c

a-d<-2",b-c>-2: -2*<x-y<2"-l -24a-d<2",b-c<2: a-d<x-y<.b-c -2<a-d<2",b-c>2". -2ix-yi2"-l a-d2",b-c>2": a-d<x-y<b-c

4.2. ОПРЩЩЛЕНИЕ ГРАНИЦ СУММЫ И РАЗНОСТИ 67