在编译时生成位计数查找表

Question

假设我需要创建一个包含预计算的比特数（数字中的1位数目）的LUT，用于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;
}

我知道这可能是未定义行为...

- Alex F

---

为什么你不想要一个带有硬编码值的简单查找表？这样做有什么问题？ - orlp

如果您不喜欢预处理器魔法，可以尝试可变参数模板魔法：https://dev59.com/MnA85IYBdhLWcg3wBO3h - TemplateRex

Answer 1

使用宏可以很容易地实现，最近我在我的代码中重新发现了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和模板技术上苦苦挣扎，发现使用预处理器更容易阅读、简短而且强大，特别是对于枚举类型等情况。与TMP相比，预处理器的一个重要优点是编译时间更短。

至于最后的逗号，在合理的编译器中应该是支持的。但如果你的编译器不支持，请将重复次数更改为255，并手动添加最后一个情况。

你可能还想将MACRO重命名为有意义的名称，以避免可能的重新定义。

- Bartek Banachewicz

---

关于末尾的逗号，根据标准是合法的，因此任何编译器不接受它都是相当不合理的；-) - TemplateRex

@TemplateRex 我知道这是合法的，但不幸的是，市面上的非符合编译器比符合编译器还要多。 - Bartek Banachewicz

同时我遇到了“fatal error C1009: compiler limit : macros nested too deeply”错误。它大约可以工作到230大小。根据微软的说法，“编译器有256个嵌套宏的级别限制”。 - Alex F

@AlexFarber 更像是 BOOST_PP_REPEAT_FROM_TO。 - Bartek Banachewicz

由于某些原因，使用BOOST_PP_REPEAT_FROM_TO两次生成子数组会导致相同的宏嵌套错误。无论如何，我接受这个答案，因为它提供了编译器限制内的方法。谢谢。 - Alex F

问题已修改，我根据您的代码找到了解决办法（尽管这可能是一种不太正规的方法）。谢谢。 - Alex F

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_ENUM 与 BOOST_PP_REPEAT 的区别在于，BOOST_PP_ENUM 生成一个用逗号隔开的值序列，所以不需要担心逗号和最后一种情况的行为。
• 此外，建议使用 NAMESPACE_PP_FUNCTION 命名方案，使您的宏真正响亮而且让人讨厌。
• 一个小的配置问题是，在数组大小中省略 [256]，改用 []，这样您可以更轻松地进行修改。
• 最后，我建议将您的 CountBit 函数模板定义为 constexpr，这样您也可以初始化 const 数组。

- TemplateRex

---

谢谢，它看起来与Bartek Banachewicz之前发布的解决方案相似。如果您能更详细地阐述您在评论中提到的可变模板解决方案，那就太好了... - Alex F

@AlexFarber 我还没有尝试过那个解决方案，但是Georg Fritzsche的答案可以粘贴到一个在线编译器中。 - TemplateRex