Генерация 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 бита в номере, он используется только в качестве примера. Я хочу сгенерировать такой массив полностью в коде, не используя внешние генераторы кода. Массив должен быть сгенерирован во время компиляции.
редактировать.
Чтобы преодолеть ограничения компилятора, я нашел следующее решение, основанное на
Код Bartek Banachewicz`:
#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;
}
Я знаю, что это, возможно, UB …
Решение
Это было бы довольно легко с использованием макросов (недавно вновь обнаруженных мной для моего кода) 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 чтобы что-то значимое, чтобы избежать возможных переопределений.
Другие решения
Мне нравится делать это так:
#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так что вы также можете инициализировать константные массивы.