Подсчет числа установленных битов в 9-битовом поле

Задача подсчета установленных битов возникла при разработке библиотеки для решения японской игры судоку. В судоку нужно заполнять клетки цифрами от 1 до 9 так, чтобы ни в одной горизонтальной и вертикальной линиях (поле в игре представлено линиями 9x9 и разбито на 9 квадратов 3x3), а также ни в одном из квадратов, не было одинаковых цифр. С точки зрения алгоритма решения задачи, состояние каждой клетки удобно хранить в 9-битовом поле, где установленными битами помечены "выбывшие" цифры; соответственно поле без установленных битов означает, что в клетку можно вставить любую из 9 цифр, а если, скажем, в поле остался не установленным единственный 6-ой бит, то в эту клетку можно поместить только цифру 6.
Алгоритм подсчета установленных битов в 32-битном слове прекрасно описан в книге Генри Уоррена мл. "Hacker's Delight" (которую по непонятным причинами перевели на русский как "Алгоритмические трюки для программистов"). Алгоритм по своей сути является рекурсивным и основан на методе дихотомии: сначала 32-битное слово делится пополам и задача разбивается на 2 одинаковых подзадачи, в свою очередь, получившиеся 16-битные половинки также делятся пополам, добавляя еще 4 подзадачи, и так происходит до тех пор, пока всё слово не будет разделено на 16 2-битовых полей, в каждом из которых биты подсчитываются 16-ю независимыми подзадачами. Сам автор приводит пример, изображенный на рисунке ниже. Поскольку алгоритм подсчета битов рекурсивен, то его удобней изображать снизу вверх: соответственно нижние 16 подзадач изображены в верхней части рисунка сразу после исходного значения в слове, а итоговый результат находится внизу:

На языке C этот алгоритм можно представить следующим образом:

    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. Маски соответствуют заполнению единицами справа на треть отделений битового поля, разделенных "стенками", характерными для двух этапов алгоритма.