asDouble = (double)к + 0.5; n = 1054 - (aslnt[LE] » 20); return n;

Этот код использует анонимное (безымянное) объединение С++ для перекрытия це лого числа и величины с плавающей точкой двойной точности. Переменная LE должн; быть равна 1, если процедура выполняется на машинах, где адрес младшего байта мень ше адреса старшего, и О в противном случае. Слагаемое 0.5 (иди другое малое число) не обходимо для корректной работы гфограммы при к = о.

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

Код в листинге 5.11 ие соответствует ANSI-стандарту языков С и С++, поскольку он обращается к одной и той же области памяти как к двум различным типам данных. Следовательно, нет никаких гарантий, что этот код будет правильно работать на всех машинах или со всеми компиляторами. Тем не менее он работает с компилятором XLC IBM на платфор ме AIX и с компилятором GCC на платформах AIX и Windows 2000 при всех уровнях оптимизации (по крайней мере на момент написания книги). Если изменить код как показано ниже, то код в режиме оптимизации в указанных системах работать не станет.

XX = (double)к + 0.5;

п = 1054 - (*((unsigned *)&хх + LE) » 20);

Кстати, этот код нарушает еще один стандЕфт ANSI, а именно то, что арифметические действия могут выполняться только с указателями на элементы массива [8]. Проблема, тем не менее, связана с первым нарушением стандарта.

Несмотря на то что данный код не совсем корректен, далее приведено несколько его вариантов.

asDouble = (double)к;

П = 1054 - (aslnt[LE] » 20);

п = (п & 31) + (п » 9) ;

к = к & -(к » 1) ; asFloat = (float)к 0.5f; п = 158 - (aslnt » 23);

к = к & -(к » 1) ; asFloat = (float)к; п = 158 - (aslnt >> 23); п = (п & 31) + (п » 6) ;

Некорректен в силу способа использования языка программирования С. Эти методы совершенно корректно будут работать прн кодировании на машинном языке либо будучи сгенерированными компилятором дня конкретного типа компьютера.

в первом варианте проблема с к = о решена не путем добавления слагаемого 0.5, а при помощи дополнительных арифметических действий над результатом п (которое без применения коррекции будет равно 1054 (0х41Е)).

В следующих двух вариантах этого кода используются числа с плавающей точкой одинарной точности, которые преобразуются обычным методом с использованием анонимного объединения. Правда, здесь возникает новая проблема: при округлении результата возможны неточности, как при округлении к ближайшему числу (наиболее распространенный метод округления), так и при округлении в большую сторону. В режиме округления к ближайшему числу проблемы с округлением к возникают в диапазонах (в щестнадцатеричной записи) от FFFFFF80 до FFFFFFFF, от 7FFFFFC0 до 7FFFFFFF,*or 3FFITFE0 до 3FFFFFFF и т.д. При округлении этих чисел добавление единицы приводит к появлению переноса в левых разрядах, что влечет за собой изменение позиции старшего единичного бита. Показанные выше способы коррекции сбрасывают бит справа от старшего единичного бита, позволяя тем самым избежать переноса.

Компилятор GNU C/C++ дает возможность кодировать любой из этих методов в виде макроса, позволяя вместо вызова функтдаи использовать встроенный код [57]. Компилятор разрешает использовать в макросе объявления, а последнее выражение среди операторов макроса дает возвращаемое макросом значение. Ниже приводится пример макроопределения для алгоритма с применением чисел с одинарной точностью. (В языке С в названиях макросов обычно используются прописные буквы.)

#define NLZ (к) \

((union (unsigned asInt; float asFloat;}; \

unsigned kk = (k) & -((unsigned)(k) >> 1); \ asFloat = (float) kk + 0.5f; \

158 - ( aslnt » 23);})

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

Связь с логарифмом

По существу, nlz представляет собой функцию "целого логарифма по основанию 2". Для беззнакового хФй справедливы следующие соотношения (см. также раздел 11.4):

log,(jc)J = 31-nlz(jc), \og{xf\ = 31-n\z{x-l).

Другой тесно связанной с ней функцией является функция bitsize - количество битов, которое требуется для представления ее аргумента как знаковой величины в дополнительном коде. Эта функция определяется следующим образом:

1, Jt = -1 или О,

2, х = -1 или 1

3, -4<х<-3или2йл<3,

4, -8<jc<-5 или4<л-й7,

32, -2<xi-2°+\юail°<.x<l-\.

bitsize(jt) =

Из определения очевидно, что bitsize(jc) =bitsize(-jt-l). Но, поскольку -х-\=-л,

можно записать следующий код для вычисления функции bitsize (сдвиг в коде - знаковый):

X = X * (х >> 31); Если (х < 0), X = -X - 1;

return 33 - nlz(х);

Применение

.Функции вычисления ведущих нулевых битов слова обычно используются при моделировании арифметических действий над числами с плавающей точкой и в различных алгоритмах деления (см. листинги 9.1 и 9.3). Кроме этого, команда nlz(jt) имеет множество других применений.

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

Еще одно интересное применение функции- для генерации экспоненциально распределенных случайных целых чисел. Для этого генерируются случайные равномерно распределенные целые числа и к результату применяется функция nlz [19]. Вероятность возврата функцией значения О равна 1/2, вероятность значения 1 равна 1/4, 2 - 1/8 н т.д. Кроме того, функция применяется в качестве вспомогательной при поиске в слове подстроки определенной длины, состоящей из единичных (или нулевых) битов (процесс, используемый в некоторых алгоритмах распределения дискового пространства). В последних двух задачах используется также функция, вычисляющая количество завершающих нулевых битов.

5.4. Подсчет завершающих нулевых битов

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

32-nlz(-*&(x-l)).

При наличии команды вычисления количества единичных битов слова существует более эффективный метод, состоящий в формировании маски для выделения всех завершающих нулевых битов и подсчете единиц в этой маске [27], например так:

рор(-тг&(jc-l)) или

32-pop(jc-Jc).

Сформировать маску для выделения завершающих нулевых битов можно по формулам, которые приводятся в разделе 2.1. Эти методы применимы даже в случае, когда среди команд компьютера команда подсчета количества единичных битов слова отсутствует. Например, если для подсчета единичных битов воспользоваться алгоритмом нз листинга5.1, то первое из приведенных выше вьфажений вычисляется за 3 + 21 = 24 команды, среди которых нет команд ветвления.

В листинге 5.12 показан алгоритм, который выполняет описанные действия непосредственно, требуя от 12 до 20 базовых RISC-команд (для хфО).