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

int nlz(unsigned х)

unsigned у; int n;

n =32; у = X »1б; у = X » 8; у = X » 4; у = X » 2; у = X » 1; return п - X;

Этот алгоритм позволяет использовать метод поиска в таблице, при этом последние четыре исполняемые строки кода заменяются строками

static char table[256] = (0,1,2,2,3,3,3,3,4,4,..., 8); return n - table[x];

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

Для компактности два последних алгоритма можно кодировать с использованием циклов. Например, алгоритм из листинга 5.7 является вариантом алгоритма из листинга 5.6 с использованием цикла. Выполняется этот вариант алгоритма за 23-33 базовые RISC-команды, 10 из которых представляют собой команды условного ветвления.

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

int nlz(unsigned х) (

unsigned у; int n. С;

n =32; с = 16; do (

у = X >> С;

if (у с = с } while (с п = п - (X

!= 0) (п = п -» 1; 0) ; 31);

С; X

! = >>

return п - X;

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

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

Листинг 5.8. Двухсторонний подсчет ведущих нулевых битов

int nlz(int х) (

int у, n;

n = О ; у = х;

L: if (х < 0) return n;

if (у == 0) return 32 - п; n = n + 1; X = X << 1; У = у » 1; goto L;

Ha машине с базовым набором RISC-команд этот код выполняется за min(3 + 6nlz(jc),5 + 6(32-nlz(x))) команд, что в худшем случае равно 99 командам. Однако можно представить суперскалярную или VLIW-машину, в которой тело цикла выполняется за один такт (если результат сравнения получается как побочный результат выполнения команд сдвига; в противном случае потребуется два такта), плюс накладные расходы на команды ветвления.

Достаточно просто преобразовать код из листингов 5.5 и 5.6 в эквивалентный, но без использования условных переходов. В листинге 5.9 представлен метод вычисления функции nlz за 28 основных RISC-команд.

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

int nlz(unsigned х) (

int у, m, n;

у = -(x >> 16); Если левая половина х = О,

m = (у >> 16) & 16; п = 16. Если левая половина п = 16 - ш; не нулевая, установить п = О и

X = X >> т; сдвинуть х вправо на 16 бит.

X принимает вид ООООхххх у = X - 0x100; Если разряды 8-15 нулевые,

m = (у » 16) & 8; к п добавляется 8 и выполняется п = п + т; сдвиг X влево на 8

X = X << т;

у = X - 0x1000; Если разряды 12-15 нулевые,

m = (у >> 16) & 4; увеличиваем n на 4 и

п = п + m; сдвигаем х влево на 4 X = X << т;

у = X - 0x4 000; Если разряды 14-15 нулевые,

m = (у » 16) & 2; увеличиваем п на 2 и п = п + т; сдвигаем х влево на 2

X = X << т;

у = X » 14; Устанавливаем у = О, 1, 2 или 3

m = у & ~(у >> 1); m = О, 1, 2 или 2 соответственно return п + 2 - m;

Если ваш компьютер оснащен командой для вычисления фушщии рор(х), то существует

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

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

Листинг 5.10. Подсчет ведущих нулевых битов с использованием функции рор(д:)

int nlz(unsigned х) (

int pop(unsigned x);

X = X (X >> 1) X = X (X » 2) X = X (X » 4) X = X (X >> 8) X = X (X >>16) return pop (-x);

Методы с плавающей точкой

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

Листинг 5.11. Подсчет ведущих нулевых битов с использованием чисел с плавающей точкой в IEEE-формате

int nlz(unsigned к) { union {

unsigned aslnt[2]; double asDouble;

int n;