{a-b)b +(b-c)c +{с-а)а

{a-b)ab + (b-c)bc + {c-a)ac]}.

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

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

f{x)={{-(x=c))&a)m-ix=a))&b) + {{-{x=b))&c).

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

Данную формулу можно упростить, если предварительно вычислить значения я-с и Ь-с [19]:

/(х)=((-(х = с))&(а-с)) + ((-(х=а))&(6-с))+с или /(х)=((-(х=с))&(аФс))ф((-(х=а))&(6Фс))Фс.

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

if (X == а) X = Ь; else if (х == b) х = с; else X = а;

В [19] предлагается еще один оригинальный метод без переходов с циклом выборки из трех значений, работающий даже там, где нет команд сравнения. На большинстве машин его можно выполнить за восемь команд.

Пусть а, Ьис не равны друг другу. Следовательно, имеются два разряда «1 и «2 такие, что биты чисел а,Ьисв этих разрядах различны, и два числа, оба бита которых отличаются от битов другого числа. Проиллюстрируем это на примере чисел 21, 31 и 20.

10 10 1 с 11111 а 10 10 0 b

«1 «2

Без потери общности переименуем а, b и с так, чтобы биты а и b были различны в обоих разрядах, как и показано выше. Тогда существует два возможных набора битов в позиции И], а именно (а,,с„ ) = (0,0,1) или (1,0,0). Аналогично, для битов в позиции Иг

также возможны два варианта: (a„,6„,,c,J = (0,1,0) или (1,0,1). Это приводит нас к рассмотрению четырех возможных случаев, формулы для которых приведены ниже. Случай 1. („,6 ) = (0,1,1), («.,6.) = (0,1,0): /(*) = .,*(«-*) + Jf-.*(c-«) + ft

Случай2. («,6. .c.,) = (0,U), («,.6,,c.J = (l,0,l):

f{x) = x,*{a-b) + x„*{a-c) + {b+c-a)

Случай3. (й,б ,с„) = (1,0,0). («,,.6..c.J = (0.1.0):

/(jf) = Jf-,*(ft-«) + Jf..*(-«)+«

(«,cj = (1.0,0), KA..J=(1.0,1):

/(jf) = Jf-, + .(я-с)+с

в этих формулах левый операнд каждого умножения представляет собой отдельный бит. Умножение на О или 1 можно заменить операцией и с О или с числом, все биты которого равны 1. Таким образом, эти формулы можно переписать иначе, например для первого случая получим:

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

Данная идея может быть распространена на случай циклической выборки из четырех и более констант. Главное - найти такие номера битов пиПг.....которые бы идентифицировали константы единственным образом. Дня четырех констант всегда достаточно трех позиций битов. Затем (в случае четырех констант) решаются уравнения для s,t,uHv (т.е. решается система из четырех линейных уравнений, в которой f(x) принимает значения а, Ь, с и d,a коэффициенты jt„ равны О или 1):

f{x) = \s+x,/+x,u+v .

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

f{x) = x„s+x„J+x„x„u + v.

ГЛАВА 3

ОКРУГЛЕНИЕ К СТЕПЕНИ 2

3.1. Округление к кратному степени 2

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

« 3 . Этот способ работает и со знаковыми целыми числами, просто здесь "округ-

ление в меньшую сторону" означает округление к меньшему отрицательному числу, например: (-37) & (-8) =-40.

Округление в большую сторону выполняется практически так же просто. Например, округление беззнакового целого х в большую сторону к следующему кратному 8 реализуется одной из формул: (лг + 7) & -8 или х + (-лг &7).

Эти формулы корректны и для знаковых целых чисел, причем "округление в большую сторону" означает округление в положительном направлении. Второе слагаемое во втором выражении может быть полезно само по себе, так как означает разность между ближайшим кратным 8 числом, большим х, и самим х [22].

Для округления знаковых целых чисел к ближайшему кратному 8 по направлению к О (т.е. -37 округляется до -32) можно просто скомбинировать приведенные ранее выражения:

*»31 (*+0&-8.

&7;

лг»2 »29, что может

Первую формулу можно переписать несколько иначе: t

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

Иногда при округлении указывается множитель округления, представляющий собой logj от величины округления (так, значение 3 означает округление к числу, кратному 8, так как log, 8 = 3). В этом случае можно использовать приведенные ниже формулы, где к - множитель округления.

Округление к меньшему числу: х & ((-1)«it)

х»к «Л

Округление к большему числу: f<-(l«jt)-l; {x+l)&-i или

f<-(-l)«Jt; (лг-/-1)&/