Алгоритм подсчета установленных битов в 32-битном слове прекрасно описан в книге Генри Уоррена мл. "Hacker's Delight" (которую по непонятным причинами перевели на русский как "Алгоритмические трюки для программистов"). Алгоритм по своей сути является рекурсивным и основан на методе дихотомии: сначала 32-битное слово делится пополам и задача разбивается на 2 одинаковых подзадачи, в свою очередь, получившиеся 16-битные половинки также делятся пополам, добавляя еще 4 подзадачи, и так происходит до тех пор, пока всё слово не будет разделено на 16 2-битовых полей, в каждом из которых биты подсчитываются 16-ю независимыми подзадачами. Сам автор приводит пример, изображенный на рисунке ниже. Поскольку алгоритм подсчета битов рекурсивен, то его удобней изображать снизу вверх: соответственно нижние 16 подзадач изображены в верхней части рисунка сразу после исходного значения в слове, а итоговый результат находится внизу:
x = ( x & 0x55555555 ) + ( ( x >> 1 ) & 0x55555555 ); x = ( x & 0x33333333 ) + ( ( x >> 2 ) & 0x33333333 ); x = ( x & 0x0F0F0F0F ) + ( ( x >> 4 ) & 0x0F0F0F0F ); x = ( x & 0x00FF00FF ) + ( ( x >> 8 ) & 0x00FF00FF ); x = ( x & 0x0000FFFF ) + ( ( x >> 16 ) & 0x0000FFFF );В верхнем выражении используется маска 0x55555555, которая в двоичном выражении соответствует циклическому повторению 01; первое слагаемое выделяет биты в этой маске (т.е. все нечетные биты), во втором слагаемом сначала все биты сдвигаются вправо на одну позицию и к полученному значению применяется та же маска (таким образом, выделяются все четные биты). Два полученных значения складываются и результат подобным же образом обрабатывается маской 0x33333333, которая соответствует циклическому повторению 0011. И так далее. Легко видеть, что маски соответствуют "стенкам" битовых полей, характерных для текущего этапа алгоритма дихотомии; "стенки" обозначены на рисунке красными разделителями. Маска подбирается таким образом, чтобы каждое отделение между "стенками" было заполнено ровно наполовину единицами справа и нулями слева.
Наша задача - адаптировать данный алгоритм для 9-битового поля. Для хранения нашего битового поля выберем целочисленный тип с достаточной емкостью (например 8-битный char не подходит), пусть это будет 32-битный int. Пусть наше битовое поле находится в 9 младших битах. Принудительно занулять старшие биты нет необходимости, так как на работу алгоритма они не повлияют.
К сожалению, 9 не делится на 2, поэтому нужно выбрать другое число: 3 - отличный (и единственный) кандидат. 3 в степени 2 и есть 9, соответственно нам понадобятся всего два шага (заметьте, что 2 в пятой степени равно 32, поэтому предыдущий алгоритм выполнялся за 5 шагов). С другой стороны, раз мы поменяли базу с 2 на 3, то вместо двух слагаемых на каждом шаге нам понадобятся 3, что соответствует двум сдвигам битов для выделения по маскам.
Давайте приведем функцию, которая выполняет подсчет:
int countSetBits9( int nmb ) { nmb = ( nmb & 0x49 ) + ( ( nmb >> 1 ) & 0x49 ) + ( ( nmb >> 2 ) & 0x49 ); return ( nmb & 0x07 ) + ( ( nmb >> 3 ) & 0x07 ) + ( ( nmb >> 6 ) & 0x07 ); }Маска 0x49 соответствуе двоичному числу 001001001, а 0x07 - это 000000111. Маски соответствуют заполнению единицами справа на треть отделений битового поля, разделенных "стенками", характерными для двух этапов алгоритма.
