При проверке слова на четность можно использовать функцию рор(х) - в таком

случае четность представляет собой младший бит значения, возвращаемого этой функцией. Этот метод вполне применим при наличии команды для вычисления pop(jt). Если

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

Х»1

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

Ниже приводится более быстрый способ проверки на четность для не слишком больших значений п (в примере л = 32; сдвиги могут быть как знаковыми, так и беззнаковыми).

у = X * (X >> 1)

у = у (у » 2) У = У (у » 4) у = у " (у » 8) У = У * (у » 16) ;

Всего вьшолняется 10 команд, что значительно меньше, чем в первом методе (62 команды), даже при полном развертывании цикла. Здесь бит четности также оказывается в младшем разряде у. В действительности всегда при выполнении беззнаковых сдвигов i-й бит результата у дает четность битовой строки, состоящей из всех битов х от i-го до старшего. 1фоме того, так как исключающее или представляет собой свою собственную инверсию, четность (jt»г) Ф(х з> у) равна четности подслова, состоящего из битовх с; по i -1 (ij).

Приведенный выше метод является примером метода "параллельншч) префикса", или "сканирования", который применяется в параллельных вычислениях [30,41]. При наличии достаточного количества процессоров он позволяет преобразовать некоторые кажущиеся последовательными процессы в параллельные, сокращая время вычислений от 0(л) до o(logn). Например, если необходимо выполнить операцию поразрядного исключающего или над целым массивом, вы можете сначала выполнить действия (3) над каждым словом массива и затем применить, по сути, ту же методику к массиву, выполняя операцию исключающего или над словами массива. При таком подходе выполняется большее количество элементарных (с отдельными словами) команд исключающего или, чем в простом алгоритме, работающем слева направо, а следовательно, для однопроцессорного компьютера применять данный метод не стоит. Но на компьютере с достаточным количеством параллельных процессоров проверка на четность по описанному выше алгоритму занимает время O(logn), а не 0[п) (где п - количество слов в массиве).

Непосредственным приложением метода (3) является преобразование целых чисел в код Грея (см. главу 13).

Если изменить код (3), заменив все сдвиги вправо сдвигами влево, то результат проверки на четность целого слова х отображается в старшем бите у, а i-й бит слова у содержит четность битов словах, расположенных в i-й позиции и правее нее.

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

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

X = X * (х >> 1);

X = (X * (X » 2)) & 0x11111111; X = Х*0х11111111; р = (X »28) & 1;

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

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

Добавление бита четности к 7-битовой величине

В [25, item 167] есть интересный алгоритм, добавляющий бит четности к 7-битовой величине (выровненной вправо и помещенной в регистр). Под этим подразумевается установка бита четности слева от семи битов таким образом, чтобы получить восьмибитовую величину с четным количеством единичных битов. В указанной работе приведен пример кода для 36-битовой машины, но он корректно работает и на 32-битовых машинах.

modu((x*0xl0204081)&0x888888FF,1920).

Здесь modu(fl,6) означает остаток от беззнакового деления а на Ь, аргументы и результат интерпретируются как целые числа без знака, " * " означает умножение по модулю 2, а константа 1920 равна 15-2. Фактически здесь вычисляется сумма битов в слове х с размещением этой суммы слева от семи битов х. Например, это выражение преобразует число OxOOOOOQ7F в ОхОООООЗРР и 0x00000055 в 0x00000255.

В [25] есть еще одна остроумная формула для добавления битов четности к 7-битовому числу (при этом образуется 8-битовое число с нечетным количеством единичных битов):

modu((**0x00204081)0x3DB6DB00,1152),

где 1152 = 9-2. Понять, как работает эта формула, поможет тот факт, что степень 8 по модулю 9 равна ±1. Если заменить 0x3DB6DB00 значением 0xBDB6DB00, эта формула будет давать восьмибитовое число с четным количеством единичных битов.

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

Применение

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

5.3. Подсчет ведущих нулевых битов

Существует ряд простых способов подсчета ведущих нулевых битов слова, реализуемых при помощи метода бинарного поиска. Ниже приведена модель, имеющая ряд вариаций. На процессоре с базовым набором RISC-команд вычисления выполняются за 20-29 команд. Все сравнения беззнаковые.

В другом варианте все сравнения заменяются командами и:

if if

((X ((X

Sc OxFFFFOOOO) Sc OxFFOOOOOO)

0) 0)

+ 16; + 8;

X <<16; X << 8;

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

Последний из операторов if просто прибавляет единицу к п, если старший бнг х равен О, так что в в)ианте без использования условного перехода можно прибегнуть к инструкции

п = п + 1 - (х >> 31);

Здесь "+1" можно опустить, если инициализировать переменную п не О, а 1. Это наблюдение приводит к алгоритму, дяя работы которого потребуется выполнение от 12 до 20 основных RISC-команд (листинг 5.5). Этот код можно улучшить еще немного, если х начинается с единичного бита; тогда первую строку можно заменить следующей:

if ((int)x <= 0) return (~х » 26) Sc 32;

Листинг 5.5. Подсчет ведущих нулевых битов бинарным поиском

int nlz(unsigned х) {

int П;

if (х == 0) return(32); n =1;

if ((X >> 16) ==0) n = n +16; X = X <<16; if ((X >> 24) ==0) n = n + 8; X = X « 8; if ((X » 28) ==0) n = n + 4; X = X << 4; if ((X » 30) ==0) n = n + 2; X = X « 2; n = n - (X » 31); return n;

В листинге 5.6 показан вариант подсчета одним из методов, обратных приведенному выше. Он требует выполнения тем меньшего количества операций, чем больше ведущих нулей имеется в слове, и позволяет избежать использования больших непосредственно задаваемых чисел и больших сдвигов. Всего вьшолняется от 12 до 20 основных RISC-команд,