Эти методы работают недостаточно эффективно. Большинство программистов предпочитают при подсчете единичных битов пользоваться таблицами значений этой функции. Последний из рассмотренных алгоритмов, однако, имеет версию с использованием 64-битовой арифметики и может оказаться полезным на 64-битовых машинах, у которых есть команда быстрого умножения. Аргументом данного алгоритма является 15-битовая величина (я не думаю, что есть похожий алгоритм для 16-битовых величин, кроме случая, когда заранее известно, что не все 16 бит являются единичными). Тип данных long long представляет собой расширение языка С в компиляторе GNU [57] и означает целое число вдвое большей длины, чем тип int (в нашем случае тип long long имеет длину 64 бита). Суффикс ULL означает константы типа unsigned long long.

int pop(unsigned x) {

unsigned long long у,-

у = X * 0X0002000400080010ULL,-

у = у & OxllllllllllllllllULL;

у = у * OxllllllllllllllllULL;

у = у » 60;

return У;

Подсчет единичных битов в массиве

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

Другой путь, который может оказаться более быстрым, состоит в использовании первых двух строк этой процедуры для групп из трех слов с последующим сложением трех промежуточных значений. Поскольку максимальное значение каждого промежуточного результата в каждом 4-разрядном поле равно 4, после сложения этих трех промежуточных результатов в каждом 4-разрядном поле будет максимум число 12, так что переполнения при сложении возникнуть не может. Затем каждая из полученных сумм может быть преобразована в слово с четьфьмя 8-битовыми полями с максимальным значением поля, равным 24, с использованием

X = (X & OXOFOFOFOF) + ((X » 4) & OxOFOFOFOF);

Полученные таким образом слова складываются до тех пор, пока максимальное значение их суммы в каждом поле результирующего слова остается меньше 255; всего можно сложить десять таких слов ([255/24J). После сложения 10 слов полученный результат преобразуется в слово с двумя 16-битовыми полями с максимальным значением 240 в каждом из них;

X = (X & OXOOFFOOFF) + ((X » 8) & OxOOFFOOFF);

Теперь, прежде чем потребуется применить очередное преобразование в 32-битовое слово, можно сложить 273 таких слова ([65535/240J). Это гфеобразование выполняется

следующим образом:

X = (X & OxOOOOFFFF) + ((X » 16);

На практике команды управления циклом существенно превыскт полученную при использовании этого метода экономию, так что ciporo следовать описанной гфоцедуре, вероятно, не имеет смысла. Например, код в листинге 5.4 использует только один промежуточный уровень. Сначала формируются слова с четырьмя 8-битовыми полями с промежуточными суммами в каждом поле. Затем все эти слова складываются с образованием целого слова, содержащего сумму. Количество слов с 8-битовымн полями, которое можно просуммировать без риска переполнения, равно [255/8J = 31.

Листинг 5.4. Подсчет единичных битов в массиве

int pop array(unsigned A[l, int n) {

int i, j, lim; unsigned s, s8, x;

s = 0;

for (i = 0; i < n; i = i + 31) {

lim = min(n, i + 31); s8 = 0;

for (j = i; j < lim; j++)

X = A[j];

X = X - ((X » 1) Sc 0x55555555);

X = (X Sc 0X33333333) + ((X » 2) Sc 0x33333333); X = (X + (X » 4)) Sc OXOFOFOFOF; S8 = S8 + X;

X = (s8 & OxOOFFOOFF) + ( (s8 » 8) Sc OxOOFFOOFF); X = (x & OxOOOOFFFF) + (X » 16) ; S = s + X;

return s;

Интересно сравнить этот алгоритм с простым циклическим алгоритмом. Обе гфоце-дуры были откомпилированы GCC на одной машине, очень похожей на RISC с основным набором команд. Результат - 22 команды на одно слово для простого циклического метода и 17.6 команды на слово по алгоритму из листинга 5.4, т.е. экономия на слово составляет 20%.

Применение

Функция pop(jc) используется, например, при вычислении расстояния Хемминга"

(Hamming distance) между двумя битовыми векторами. Расстояние Хемминга (концепция из теории кодов с исправлением ошибок) представляет собой количество разрядов, в которых эти векторы отличаются, т.е.

dist(jc,y) = pop(jc®y).

(Смотрите, например, главу о кодах с исправлением ошибок в [12].)

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

есть вспомогательный массив битовых строк bits (содержащих 32-разрадные слова), имеющий единичный бит для каждого индекса г, для которого определен элемент A[i].

Для ускорения доступа имеется также массив слов bitsum, такой, что bitsum[j] представляет собой общее количество во всех словах массива bits единичных битов, предшествующих у-му. Проиллюстрируем сказанное на массиве, в котором определены О, 2, 32, 47,48 и 95-й элементы.

bits bitsum Данные

0x00000005 О Л[0]

0x00018001 2 Л[2]

0x80000000 5 Л[32]

А[47]

А[48]

А[95]

Для заданного индекса /, О < i < 95, соответствующий индекс sparsej в массиве данных задается через количество единичных битов элементов массива bits, предшествующих биту, соответствующему i. Его можно вычислить следующим образом:

j = i » 5,- j = i/32

к = i Sc 31; к = rem(i,32)

mask = 1 « k; "l" в разряде к

If ((bits[j] Sc mask) 0)

goto no such element; mask = mask - 1; единицы справа от к

sparse i =

bitsum[j] + pop (bits [j] Si mask);

Затраты памяти при таком представлении разреженного массива - два бита на элемент полного массива.

Функция рор(х) применяется также при вычислении количества завершающих нулей слова (см. раздел 5.4).

5.2. Четность

Под "четностью" (parity) битовой строки понимается, какое количество единичных битов - четное или нечетное - содержит эта строка. Строка считается "нечетной", если она содержит нечетное количество единичных битов; в противном случае строка является четной.

Вычисление четности слова

Результат проверки на четность равен 1, если некоторое слово х является нечетным, и равен О, если слово является четным. Этот результат представляет собой сумму всех битов слова по модулю 2, т.е. над всеми битами х вьшолняется операция исключающего ши.

В данном разделе значения терминов "четное" и "нечетное" отличаются от обычных. Везде в разделе, где не оговорено иное, "четность" означает наличие четного числа единичных битов в рассматриваемом значении, а "нечетность" - нечетное количество битов. - Прим. ред.

5.2. ЧЕТНОСТЬ 83