в последней строке рспользуется беззнаковая функция получения значения х по мод) лю 63 (зто может быть как знаковое, так и беззнаковое число, если длина слова кратна З; Данная функция складывает значения, содержащиеся в 6-битовых полях слова х, что ста новится понятно, если рассматривать слово х как целое число, записанное в системе счис ления с основанием 64. Остаток от деления целого числа в системе счисления с ocHOBanHCN 6 на Ь -1 для S 3 сравним по модулю fc -1 с суммой цифр этого числа и, конечно, меньше fc. Так как сумма цифр в нашем случае не превышает 32, значение пкх1и(х,63) должно

быть равно сумме цифр х, т.е. количеству единичных битов в этом слове.

На компьютерах DEC PDP-10 есть команда, вычисляющая остаток от деления, второй операнд которой содержит адрес слова в памяти, а потому на этих машинах подсчет единичных битов в слове выполняется за 10 команд. На компьютере RISC требуется около 13 команд, если в их числе имеется отдельная команда остатка от деления по модулю. Однако, вероятно, это не очень быстрый метод, так как деление - операция довольно медленная. Простое расширение констант не позволяет работать с 64-битовыми словами, но вполне применимо для слов длиной до 62 бит.

В [26] предложена вариация алгоритма НАКМЕМ. Сначала с использованием формулы (1) параллельно подсчитывается количество единичных битов в восьми 4-битовых полях. Полученные 4-битовые значения преобразуются в 8-битовые суммы, а затем четыре байта суммируются при помощи умножения на число 0x01010101.

int pop(unsigned х)

unsigned n;

n = (X » 1) Sc 0x77777777 X = X - n;

n = (n » 1) & 0x77777777 X = X - n;

n = (n » 1) Sc 0x77777777 X = X - n;

Подсчет битов в 4-битовых полях

X = (X + (х >> 4)) Si OXOFOFOFOF; Вычисление сумм

X = х*0х01010101; Сложение байтов

return X >> 24;

Здесь для вычислений требуется 19 базовых RISC-команд. Этот код эффективно работает на двухадресной машине, так как в первых шести строках выполняется только одна команда пересылки регистра. Неоднократно используемую маску OyiTnillll можно однократно загрузить в регистр и обращаться к ней при помощи команд, работающих только с регистрами. Кроме того, большинство сдвигов в этом коде - на один разряд.

Совсем другой метод подсчета битов предложен в [54, 60] (листинг 5.2). Здесь циклически сбрасывается крайний справа единичный бит исследуемого слова, до тех пор пока это слово не станет равным 0. Этот метод, для работы которого требуется выполнение 2+5pop(jt) команд, эффективно работает со словами, в которых содержится только небольшое количество единичных битов.

Листинг 5.2. Подсчет единичных битов в малозаполиениых словах

int pop(unsigned х) I

int n; n = 0;

while (x != 0) {

n = n + l, x = X Sc (x - 1) ;

return n;

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

Еще один интересный алгоритм подсчета единичных битов предложен в [47]. В этом алгоритме вычисляется сумма всех 32 слов, полученных в результате циклического сдвига слова влево на один разряд. Итоговая сумма равна значению рор(х) со знаком минус!

Следовательно:

, (2)

1=0 V /

где все сложения выполняются по модулю длины слова, а итоговая сумма рассматривается как целое, дополненное до 2. Этот способ - не более чем красивая, но не эффективная для практического применения формула: цикл выполняется 31 раз, т.е. требуется выполнение 63 команд, не считая команд управления циклом.

Чтобы понять, как работает уравнение (2), посмотрим, что происходит с каждым отдельным битом слова X. Этот бит при циклическом сдвиге оказывается в каждом разряде, и при сложении всех 32 чисел, полученных в результате 31 циклического сдвига, в итоговом слове в каждом разряде будет единица. Но это число представляет собой -1. Для иллюстрации рассмотрим 6-битовое слово х =001001.

001001 X

010010 *«1 100100 х<к2

001001 хЪ 010010 *«4 100100 *«5

Разумеется, сдвиг вправо работает не менее корректно.

Метод подсчета единичных битов по формуле (1) очень похож на метод циклического сдвига и сложения, что становится понятно, если уравнение (1) переписать как

*3>1

Вычисление функции рор(ж) по этой формуле будет происходить немного быстрее по

сравнению с подсчетом единичных битов по формуле (2) по двум причинам. Во-первых, в нем используется команда сдвига вправо, которая, в отличие от команды циклического сдвига, есть практически на всех машинах; во-вторых, если при сдвиге слова получается нулевое значение, цикл завершается. Таким образом, это позволяет упростить цикл и сэкономить несколько итераций. Сравнение алгоритмов показано в листинге 5.3.

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

int pop(unsigned х) {

int i, sum;

Циклический сдвиг и сложение Сдвиг вправо и вычитание

sum = X; sum = х;

ford = 1; i <= 31; 1++) while(x != 0)

{ {

X = rotatel(X,1); x = x >> 1;

sum = sum + x; sum = sum - x;

} }

return -sum; return sum;

Алгоритм, вычисляющий функцию pop(jt) с использованием массива значений, менее оригинален по сравнению с предыдущими алгоритмами, тем не менее вполне может конкурировать с ними. Например, пусть для значений от О до 255 имеется массив table значений функции pop(jt). При подсчете единичных битов в слове выполняется четыре обращения к массиву table и затем складываются четыре полученных числа. Вот один из вариантов этого алгоритма (без условных переходов): int pop(unsigned х) Поиск в таблице

static char table[256] = {

О, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,

4, 5, 5, б, 5, б, б, 7, 5, б, б, 7, б, 7, 7, 8};

return table [х & OxFF] +

table [(х » 8) & OxFF] + table [(x » 16) & OxFF] + table [(X » 24)];

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

X = X * 0x08040201; Создаются 4 копии

X = X >? 3; Удаление соответствующих битов

X = X & 0x11111111; Каждый 4-й бит

X = X * 0x11111111; Сумма цифр (О или 1)

X = X >> 28; Положение результата

Вот версия алгоритма для 7-битовых величин:

X = X * 0x02040810 X = X & 0x11111111 X = X * 0x11111111

Создаются 4 копии Каждый 4-й бит Сумма цифр (О или 1)

X = X >> 28; Положение результата

Здесь последние два шага могут быть заменены вычислением остатка от л; по модулю 15. 80 ГЛАВА 5. ПОДСЧЕТ БИТОВ