ГЛАВА 5 ПОДСЧЕТ БИТОВ

5.1. Подсчет единичных битов

На компьютере ШМ Stretch (выпущенном в 1960 году) имелась возможность подсчета количества единичных битов в слове и количества ведущих нулевых битов слова (причем эти величины являлись побочным результатом выполнения любой логической операщ1и!). Функция подсчета количества единичных битов иногда носила название степени заполнения (population count), нагфимер на машинах Stretch или SPARCv9.

Если на машине нет отдельной команды для вычисления этой функции, то для подсчета единичных битов в слове можно воспользоваться другими методами. Обычно исходное слово делится на двухразрядные поля и в каждое поле помещается количество имевшихся в нем единичных битов. Затем значения, содержащиеся в соседних двухразрядных полях, складываются и результат помещается в четырехразрядное поле и т.д. Более подробно этот метод обсуждается в [54]. Этот метод проиллюстрирован на рис. 5.1. Слово, в котором под-считьтается количество единичных битов, находится в первой строке, в последней строке содержится результат (равный 23 в десятичной системе счисления).

00000000000010010000000000001 1 10

00000000000000000000000000010111

Рис. 5.1. Подсчет количества единичных битов, стратегия "разделяй и властвуй"

Рассмотренный метод - пример стратегии "разделяй и властвуй": исходная задача (суммирование в 32-битовом слове) разбивается на две подзадачи (суммирование в 16-битовом слове), каждая из которых решается независимо от другой. Затем результаты обьединяются (в нашем случае суммируются). Данная стратегия является рекурсивной: 16-битовые слова обрабатываются как два 8-битовых и т.д.

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

Другими примерами стратегии "разделяй и властвуй" являются хорошо всем известные алгоритмы бинарного поиска, быстрой сортировки, а также метод реверса битов слова, рассматриваемый в разделе 7.1.

Метод, приведенный на рис. 5.1, может быть выражен на языке С следующим образом:

В первой строке можно было бы написать, пожалуй, более естественное выражение (х к охАААААААА) » 1, НО в данном случае лучше использовать приведенное выражение (X » 1) к 0x55555555, так как при этом удается избежать загрузки в регистры двух больших констант, что на машине с отсутствующей командой и-не будет стоить дополнительной команды. Аналогичные замечания справедливы и для остальных строк кода.

Очевидно, что последняя команда и не является необходимой; кроме того, если точно известно, что при суммировании полей не произойдет переноса в соседнее поле, остальные команды и тоже не нужны. Этот код можно еще немного усовершенствовать, а именно преобразовать первую строку так, чтобы в ней выполнялось на одну команду меньше. Такой упрощенный код показан в листинге 5.1; он не содержит условных переходов и выполняется за 21 команду.

Листинг 5.1. Подсчет количества единичных битов в слове

int pop(unsigned х) {

X = X - ((X » 1) Sc 0x55555555); X = (X Sc 0x33333333) + ((X » 2) X = (X + (X » 4)) Sc OXOFOFOFOF; X = X + (X >> 8) ; X = X + (X >> 16) ; return X к 0X0000003F;

Sc 0x33333333) ;

Первое присвоение x основано на первых двух членах одной удивительной формулы:

рор(л)=

В формуле (1) значение х должно быть не меньше 0. Если х- целое беззнаковое число, формула (1) может быть реализована в виде последовательности из 31 команды сдвига вправо на единицу и 31 команды вычитания. Процедура в листинге 5.1 использует параллельно первые два члена этой формулы для каждого двухбитового поля.

Существует простое доказательство уравнения (1), приведенное ниже для случая 4-битового слова. Пусть имеется слово 2*1*0 > "Д каждое bj равно О или 1. Тогда

= u,-2+fcj-24fc,-2+fco-2-

-{b,2+b2+b,2)--{b,2 + b,20)--(V2°) =

= з(2-2=-2-2°) + Ь,(2-2-2) + Й1(2-2°) + о(2°)

= fc,+fej+fc,

Формулу (1) можно получить и иначе: например, заметив, что 1-й бит в двоичном представлении неотрицательного числа л: вычисляется по формуле

и вычисляя сумму всех fc„ где i принимает значения от О до 31. Последний член будет равен нулю, так как х<2.

Формулу (1) можно обобщить для других систем счисления. Например, для системы счисления с основанием 10 получим следующее выражение:

suHL-digits (д;) = д; - 9

где слагаемые вычисляются до тех пор, пока их значение не становится равным нулю. Полученная формула доказывается аналогично предыдущей.

Если применить описанный алгоритм для системы счисления по основанию 4, можно получить другой код для вычисления функции рор(д;), который аналогичен приведенному в листинге 5.1, но вторая строка которого заменяется строкой X = X - 3 * ((X » 2) & 0X33333333);

Этот код выполняется за те же шесть команд, что и замененный, но требует наличия ко-манды быстрого умножения на 3.

При подсчете количества единичных битов в слове по алгоритму, предложенному в НАКМЕМ [25, item 169], используется только три первых члена из формулы (1) для формирования трехбитовых слов, в каждом из которых помещается сумма его единичных битов. Затем значения, содержащиеся в соседних трехбитовых полях, складываются, а результат помещается в шестибитовое поле. После этого суммируются значения, содержащиеся в шестибитовых полях, вычисляя значение слова по модулю 63. На языке С этот алгоритм записывается следующим образом (обратите внимание, что длинные константы здесь записаны в восьмеричной системе счисления):

int pop(unsigned х) {

unsigned n;

n = (X » 1) Sc 033333333333; X = X - n;

n = (n » 1) Sc 033333333333; X = X - n;

X = (X + (X » 3)) Sc 030707070707; X = modu(x,63) ; return X;

Подсчет битов

в 3-битовых

полях

б-разрядные суммы

Сложение б-разрядных сумм