Равенство (о) показывает, как реализовать исключающее или, используя всего три базовых RISC-команды. Использование логики и-или-не потребует выполнения четырех команд {{х\у)&-,{х&у)). Аналогично, равенства (х) и (ц) реализуют операции и и или с помощью трех элементарных команд (хотя по законам де Моргана (DeMorgan) их требуется четыре.

2.3. Неравенства с логическими

и арифметическими выражениями

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

{х®у)к{х\у) и {х&у)к{ху).

Их легко получить из табл. 2.1, в которой представлены все логические операции. Таблица 2.1. Результаты работы 16 логических операций

Пусть функции f{x,y) и g{x,y) представлены двумя столбцами табл. 2.1. Если в каждой строке, где f{x,y) равна 1, g{x,y) также равна 1, то для любых значений {х,у) выполняется соотношение f{x,y)<g{x,y). Очевидно, что это неравенство справедливо и для побитовых логических операций. Легко вывести и более сложные соотношения (многие из которых тривиальны), например: (х&у)х{х\-у) и т.п. Если же значения функций f{x,y) и g{x,y) в одной строке таблицы равны О и 1, а в другой- 1 и О соответственно, то между этими логическими функхщями не существует отношения неравенства. Таким образом, всегда можно выяснить, выполняется ли для каких-то функций/и g соотношение f{x,y)<g{x,y) или нет.

При работе с неравенствами требуется внимание. Например, в обычной арифметике, если х+у<а и гид;, то г + ><а.Но этот вывод становится неверным, если "+" заменить оператором или.

Неравенства, включающие как логические, так и арифметические выражения, более интересны. Ниже приведены некоторые из них.

а) (jcy)2max(jc,y)

б) {х&у)ктп{х,у)

в) [х\у)<х + у Если сложение не вызывает nqjenonHCHHA

г) {х\у)>х + у Если сложение вызывает переполнение

д) \х-у\<{хФу)

Доказать все эти неравенства достаточно просто, за исключением, возможно, только неравенства (д). Под \х-у\ подразумевается абсолютное значение х-j, которое может быть вычислено в области беззнаковых чисел как тах(лг,з)-пип(ж,з). Это неравенство можно доказать по индукции по длинамх чу (доказать неравенство будет проще, если длины хиу расширять справа налево, а не наоборот).

2.4. Абсолютное значение

Если нет отдельной команды вычисления абсолютного значения, ее можно реализовать тремя или четырьмя командами (без ветвления). Сначала вычисляется значение y«-jc»31, а затем одно из перечисленных ниже выражений (разумеется, 2х означает х + х, или JC«1).

abs nabs

{хФу)-у у-{хФу)

{х + у)Фу {у-х)Фу

х-{2х&у) {2х&у)-х

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

2.5. Распространение знака

Под "распространением знака" (sign extension) подразумевается наличие бита в определенной позиции слова, выступающего в роли бита знака, и распространение этого бита влево при игнорировании всех остальных битов слова. Стандартный способ решения этой задачи состоит в логическом сдвиге влево, за которым следует знаковый сдвиг вправо. Однако, если эти команды работают медленно или их вообще нет на вашем компьютере, можно поступить иначе. Ниже приведены примеры распространения влево бита в седьмой позиции.

((ж + 0x00000080) & OxOOOOOOFF) - 0x00000080 [{х & OxOOOOOOFF) Ф 0x00000080) - 0x00000080

Вместо "+" можно использовать "-" или "Ф". Если известно, что все ненужные старшие биты нулевые, вторая формула оказывается более практичной, так как в этом случае можно не выполнять команду и.

2.6. Знаковый сдвиг вправо

на основе беззнакового сдвига

Если на машине нет команды знакового сдвига вправо {shift right signed), ее можно заменить другими командами. Первая формула взята из [21], вторая основана на той же идее, что и первая. На 64-разрядной машине первые четыре формулы применимы для 0<и<31, а последняя - для 0<и<б3. В принципе она применима для любых и, где под "применима" подразумевается "рассматривает величину сдвига по тому же модулю, что и логический сдвиг".

Для переменной и реализация каждой формулы требует пяти или шести команд из базового множества RISC-команд.

(ж+0х80000000):«>п r«-0x80000000:it>R; «-(д;&0х80000000)з>и; х:»п

3>И

В первых двух формулах выражение 0x80000000:t>n можно заменить на 1« 31 - и . Если и - константа, то для реализации первых двух формул на большинстве машин требуется всего лишь три команды. Если п=31, функция может быть вычислена с помо-

щью двух команд: -

2.7. Функция sign

Функция sign, или signum, определяется как

sign(jc) =

-1. л:<0,

0, д: = 0,

1, д:>0.

На большинстве машин ее можно вычислить с помощью четырех команд [29].

(«i3i)l

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