编译时生成BitCount查找表

Question

假设我需要为0.255值创建一个LUT，其中包含预先计算过的位计数值(数字中的1位数)：

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

如果我不想使用硬编码的值，我可以使用漂亮的模板解决方案How to count the number of set bits in a 32-bit integer?。

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

Notes.这个问题不是关于在一个数字中计数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;
}

我知道这可能是..。

Answer 1

使用宏(最近我为我的代码重新发现) Boost.Preprocessor相当容易--我不确定它是否属于“不使用外部代码生成器”。

PP_ENUM版本

感谢@TemplateRex for 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解决方案，特别是对于类似的枚举。与TMP相比，PP的另一个重要优势是编译时间。

至于结尾处的逗号，所有合理的编译器都应该支持它，但如果您不支持，只需将重复次数更改为255，然后手工添加最后一个例子。

您还可能希望将MACRO重命名为有意义的东西，以避免可能的重新定义。

Answer 2

我喜欢这样做：

#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，以便也可以初始化const数组。