Генерация LUT BitCount во время компиляции

Допустим, мне нужно создать LUT, содержащую предварительно вычисленные значения счетчика битов (счетчик 1 бит в числе) для значений 0...255:

int CB_LUT[256] = {0, 1, 1, 2, ... 7, 8};

Если я не хочу использовать жестко закодированные значения, я могу использовать хорошее шаблонное решение Как подсчитать количество установленных битов в 32-битном целом?

template <int BITS>
int CountBits(int val) 
{
    return (val & 0x1) + CountBits<BITS-1>(val >> 1);
}

template<>
int CountBits<1>(int val) 
{
    return val & 0x1;
}

int CB_LUT[256] = {CountBits<8>(0), CountBits<8>(1) ... CountBits<8>(255)};

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

Generate(CB_LUT, 0, 255);  // array declaration
...
cout << CB_LUT[255];       // should print 8

Примечания. Этот вопрос не о подсчете 1 бит в числе, он используется только в качестве примера. Я хочу сгенерировать такой массив полностью в коде, без использования внешних генераторов кода. Массив должен быть сгенерирован во время компиляции.

Изменить. Чтобы преодолеть ограничения компилятора, я нашел следующее решение, основанное на коде Бартека Банашевича:

#define MACRO(z,n,text) CountBits<8>(n)
int CB_LUT[] = {
    BOOST_PP_ENUM(128, MACRO, _)
};
#undef MACRO

#define MACRO(z,n,text) CountBits<8>(n+128)
int CB_LUT2[] = {
    BOOST_PP_ENUM(128, MACRO, _)
};
#undef MACRO

for(int i = 0; i < 256; ++i)   // use only CB_LUT
{
    cout << CB_LUT[i] << endl;
}

Я знаю, что это, возможно, УБ...


c++ boost templates boost-preprocessor
person Alex F    schedule 24.07.2013    source источник
comment
Почему вам не нужна простая таблица поиска с жестко закодированными значениями? В чем проблема с этим?   -  person orlp    schedule 24.07.2013
comment
если вам не нравится магия препроцессора, вы можете попробовать магию вариативного шаблона: stackoverflow.com/q/2978259/819272   -  person TemplateRex    schedule 24.07.2013

Ответы (2)


arrow_upward
5
arrow_downward

Было бы довольно легко использовать макросы (недавно заново обнаруженные мной для моего кода) Boost.Preprocessor - я не уверен, подпадает ли он под действие без использования внешних генераторов кода.

Версия PP_ENUM

Спасибо @TemplateRex за BOOST_PP_ENUM, как я уже сказал, у меня пока нет большого опыта в PP :)

#include <boost/preprocessor/repetition/enum.hpp>

// with ENUM we don't need a comma at the end
#define MACRO(z,n,text) CountBits<8>(n)
int CB_LUT[256] = {
    BOOST_PP_ENUM(256, MACRO, _)
};
#undef MACRO

Основное отличие PP_ENUM в том, что он автоматически добавляет запятую после каждого элемента и удаляет последний.

Версия PP_REPEAT

#include <boost/preprocessor/repetition/repeat.hpp>
 
#define MACRO(z,n,data) CountBits<8>(n),
int CB_LUT[256] = {    
    BOOST_PP_REPEAT(256, MACRO, _)
};
#undef MACRO

Примечания

На самом деле он очень прост и удобен в использовании, хотя вам решать, будете ли вы принимать макросы. Я лично много боролся с Boost.MPL и методами шаблонов, чтобы найти решения PP легко читаемые, короткие и мощные, особенно для подобных перечислений. Дополнительным важным преимуществом PP перед TMP является время компиляции.

Что касается запятой в конце, то ее должны поддерживать все разумные компиляторы, но если у вас ее нет, просто измените количество повторений на 255 и добавьте последний регистр вручную.

Вы также можете переименовать MACRO во что-то значимое, чтобы избежать возможных переопределений.

person Bartek Banachewicz    schedule 24.07.2013
comment
о запятой в конце, это законно в соответствии со Стандартом, так что это было бы совершенно неразумно ни одному компилятору это не принять ;-) - person TemplateRex; 24.07.2013
comment
@TemplateRex Я знаю, что это законно, но опять же, к сожалению, несовместимых компиляторов больше, чем совместимых. - person Bartek Banachewicz; 24.07.2013
comment
Тем временем я получаю fatal error C1009: compiler limit : macros nested too deeply. Работает примерно до размера 230. По данным Microsoft, The compiler has a limit of 256 levels of nested macros. - person Alex F; 24.07.2013
comment
@AlexFarber больше похож на BOOST_PP_REPEAT_FROM_TO - person Bartek Banachewicz; 24.07.2013
comment
По какой-то причине использование BOOST_PP_REPEAT_FROM_TO дважды для создания подмассивов дает ту же ошибку вложенности макросов. В любом случае, я принимаю этот ответ, потому что он обеспечивает путь в пределах ограничений компилятора. Спасибо. - person Alex F; 24.07.2013
comment
Вопрос отредактирован, я нашел способ, основанный на вашем коде (хотя, возможно, это хак). Спасибо. - person Alex F; 24.07.2013

arrow_upward
2
arrow_downward

Мне нравится делать это так:

#define MYLIB_PP_COUNT_BITS(z, i, data) \
        CountBits< 8 >(i)

int CB_LUT[] = {
        BOOST_PP_ENUM(256, MYLIB_PP_COUNT_BITS, ~)
};

#undef MYLIB_PP_COUNT_BITS
  • Разница с BOOST_PP_REPEAT заключается в том, что BOOST_PP_ENUM генерирует последовательность значений, разделенных запятыми, поэтому не нужно беспокоиться о поведении запятых и последнего регистра.
  • Кроме того, рекомендуется делать ваши макросы действительно громкими и неприятными, используя схему именования NAMESPACE_PP_FUNCTION.
  • Небольшая настройка заключается в том, чтобы опустить [256] в пользу [] в размере массива, чтобы вам было легче изменить его позже.
  • Наконец, я бы порекомендовал сделать ваш CountBit шаблон функции constexpr, чтобы вы также могли инициализировать константные массивы.
person TemplateRex    schedule 24.07.2013
comment
Спасибо, это похоже на решение Бартека Банашевича, опубликованное ранее. Если бы вы могли подробнее рассказать о решении вариативных шаблонов, упомянутом в вашем комментарии, было бы неплохо... - person Alex F; 24.07.2013
comment
@AlexFarber Я не пробовал это решение, но ответ Георга Фрицше можно вставить в онлайн-компилятор - person TemplateRex; 24.07.2013