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

int ntz(unsigned х)

int n;

if (X = n = 1; if ((X if ((X if ((X if ((X

0) return(32);

Sc OxOOOOFFFF) == 0)

& OxOOOOOOFF) == 0)

& OxOOOOOOOF) == 0)

& 0x00000003) == 0)

return n - (x & 1);

n = n +16;

n = n = in =

n .+ 8 ;

n + 4; n + 2;

= X »16 = X » 8 = X >> 4 = X >> 2

Выражение n + 16 можно упростить до 17, если компилятор недостаточно интеллектуален, чтобы сделать это самостоятельно (это не влияет на подсчитанное нами количество команд).

Еще один вЕфиант представлен в листинге 5.13. Здесь используются малые непосредственно задаваемые значения и выполняются более простые действия. При вычислениях требуется выполнить от 12 до 21 базовой RISC-команды. В отличие от первой процедуры, при меньшем количестве завершающих нулей вьшолняется большее количество команд (но, впрочем, и большее количество условных переходов, пропускающих вычисления).

Листинг 5.13. Подсчет завершающих нулевых битов, малые непосредственные значения

int ntz(unsigned х) {

unsigned у; int n;

if (X == 0) n = 31;

у = X <<1б;

у = X << 8;

у = X « 4;

у = X << 2;

у = X « 1;

return п;

Строку перед оператором return можно заменить строкой, которая экономит один условный переход (но не команду): п = п - ((х « 1) >> 31);

В смысле количества выполняемых команд трудно превзойти поиск по дереву [4]. В листинге 5.14 представлена соответствующая процедура для 8-битового аргумента. В каждом пути этой процедуры выполняется семь команд (за исключением последних двух- return 7 и return 8, где выполняется девять команд). Для 32-битового аргумента требуется выполнить от 11 до 13 команд. К сожалению, для больших размеров слов программа быстро становится все больше и больше. Так, для 8-битового аргумента исходный код занимает 12 исполняемых строк (и компилируется в 41 команду); 32-битовый аргумент требует 48 исполняемых строк кода и 164 команды, а 64-битовый - еще вдвое больше.

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

int ntz(char х) {

if (X Sc 15) {

if (X Sc 13) {

if (x Sc 1) return 0; else return 1;

else if (x Si 4) return 2; else return 3;

else if (X Sc 0x30) {

if (x Sc 0x10) return 4; else return 5;

else if (x к 0x40) return 6; else if (x) return 7; else return 8;

Если ожидается малое или, напротив, большое число завершающих нулевых битов, то лучше использовать простые циклические алгоритмы (листинг 5.15). Код в левой части листинга выполняется за 5+3ntz(jf) команд, а в правой - за 3 + 3(32-п1г(лг)) базовых RISC-команд.

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

int ntz(unsigned х) {

int n;

X = ~X Si (X - 1) ;

n = 0; n = 32;

while(x != 0) { while (x != 0) {

n = n + 1; n= n - 1;

X = X >> 1; X = X + X;

} }

return n; return n;

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

5Hl.0+i.l+i.2 + -L.3 + -i-.4+-L.5 + ...tJL-2 4 8 16 32 64

Чтобы вычислить эту сумму, рассмотрим следующий массив:

1/4 1/8 1/16 1/32 1/64 1/8 1/16 1/32 1/64 1/16 1/32 1/64 1/32 1/64 1/64

Сумма каждого столбца является членом ряда S. Следовательно, S - это сумма всех элементов массива. Вычислим сумму каждой строки.

1111 1 -+-+-+-+... = -4 8 16 32 2

1111 1

-+-+-+ - + ... = -8 16 32 64 4

1111 1

-+-+- +-+ ... = -

16 32 64 128 8

Полная сумма, таким образом, равна - + -+ + ... = 1. Абсолютная сходимость исходного

2 4 8

ряда оправдывает использование перестановки.

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

„fact2(.)={"(;;)-

Эту функцию можно вычислить по формуле 31-nlz(jc &-ж). Применение

В [19] рассматривается несколько интересных применений функции, вычисляющей количество завершающих нулевых битов. Эрик Дженсен (Eric Jensen) назвал ее "функцией линейки" {ruler Junction), так как она задает отметки на линейке, которая разделена на половины, четверти, восьмые части и т.д.

Функция ntz используется в алгоритме Госпера (R.W. Gosper), обнаруживающем циклы и заслуживающем детального рассмотрения в силу своей элегантности и функциональности, которую на первый взгляд от него трудно ожидать.

Пусть имеется последовательность Xq, Xi, Xi,.-., определяемая правилом «+1 =/(»)- Если функция /ограничена, то эта последовательность является периодической. Она состоит из некоторой ведущей последовательности Xq, Xi, Xi, X.i, за которой идет периодически повторяющаяся последовательность Х Х\..... н-я-!

{Xfi=Xfi+x, Xfi+i=XfiM и т.д., где Л- ее период). Нам требуется найти индекс первого элемента периодической подпоследовательности и период Л. Обнаружение цикла часто используется при тестировании генераторов случайных чисел и для определения, имеется ли цикл в связанном списке.

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