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

Простейший пример шаблонного метапрограммирования в C++

Под метапрограммированием обычно понимают предоставление специальных средств внутри или снаружи исходного кода, которые позволяют выводить часть программы автоматически. Таким спецсредством в C++ являются шаблоны (templates). Шаблоны C++ обеспечивают особый метаязык, по своим характеристикам являющийся функциональным и понимаемый исключительно компилятором C++. С функциональными языками шаблонный метаязык сближают наличие общих подходов (сопоставление с образцом, рекурсия) и запрет переменных-состояний.
Рассмотрим следующую ситуацию. Допустим мы хотим создать класс, услуги которого базируются на сходных по назначению, но отличных в их реализации классах BaseA и BaseB. Если оба базовых класса обладают схожим интерфейсом, то логично оформить наш класс в виде шаблона:

    template  < typename  Base >
    class  Derived  : public Base
    {
    };

(Я не буду заострять внимание на содержимом классов, поэтому наш класс пустой, хотя фактически он может содержать множество полей и методов.)
Подразумевается, что вместо шаблонного аргумента Base нужно будет подставлять BaseA либо BaseB в зависимости от требований разработчика. А теперь главный вопрос: что если разработчику необходима информация о базовых классах объектов, основанных на шаблоне Derived. Как ее получить?
На вскидку я могу перечислить четыре способа:

1. Вполне возможно, что классы BaseA и BaseB сами предоставляют информацию о своих типах. Но это не всегда так, а изменять эти классы мы не можем.
2. Использование RTTI и dynamic_cast. Во-первых, это не всегда доступно, ведь для использования dynamic_cast необходимо, чтобы BaseA и BaseB были полиморфными, т.е. содержали виртуальные функции. Во-вторых, использование RTTI чревато потерей эффективности.

Оставшиеся два способа связаны с введением в шаблон класса Derived нового метода GetBaseClass(), предоставляющего информацию о базовом типе:

    template  < typename  Base >
    class  Derived : public Base
    {
        public:
            BaseClass  GetBaseClass( void ) const;
    };

BaseClass - это enum, перечисляющий базовые классы, а также значение Prohibited:

    enum  BaseClass
    {
        Prohibited,
        BaseClassA,
        BaseClassB
    };

Итак, оставшиеся способы:

3. Специализация шаблона Derived для отдельных типов базового класса. К сожалению, шаблон класса Derived может содержать большое число полей и методов, его полная специализация приведет к нежелательному дублированию кода.
4. Использование трюка, основанного на шаблонном метапрограммировании.

Четвертый способ - это и есть то, что я хотел здесь показать. Он основан на введении вспомогательного шаблона класса (или структуры) BaseClassInstance, не содержащего ничего, кроме статической константы типа BaseClass, и специализированного для разных фактических типов базовых классов:

    template  < typename >
    struct  BaseClassInstance
    {
        static const BaseClass  value = Prohibited;
    };


    template  <>
    struct  BaseClassInstance< BaseA >
    {
        static const BaseClass  value = BaseClassA;
    };


    template  <>
    struct  BaseClassInstance< BaseB >
    {
        static const BaseClass  value = BaseClassB;
    };

(В первом определении после ключевого слова typename можно было указать имя аргумента, например Base, но, поскольку оно не используется в теле шаблона, я его опустил.)
Несмотря на то, что по форме здесь перечисляются разные специализации шаблона структуры C++, по сути, если рассматривать это с точки зрения функционального программирования, здесь объявлены клозы простейшей функции, возвращающей значение типа BaseClass в зависимости от результата сопоставления с образцом (типом - шаблонным аргументом)!
Нам осталось написать тело метода GetBaseClass():

    template  < typename  Base >
    BaseClass Derived< Base >::GetBaseClass( void ) const
    {
        return BaseClassInstance< Base >::value;
    }

Теперь объекты классов, основанных на шаблоне Derived, обладают информацией о своем базовом классе. Эта информация закладывается в момент инстанцирования классов, а значит нет дополнительных нагрузок в ран-тайме, и, что не менее важно, нам не пришлось дублировать исходный код.