Generating BitCount LUT at compile time

Question

Let's say that I need to create a LUT containing precomputed bit count values (count of 1 bits in a number) for 0...255 values:

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

If I don't want to use hard-coded values, I can use nice template solution 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)}; 

This array is computed completely at compile time. Is there any way to avoid a long list, and generate such array using some kind of templates or even macros (sorry!), something like:

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

Notes. This question is not about counting 1 bits in an number, it is used just as example. I want to generate such array completely in the code, without using external code generators. Array must be generated at compile time.

Edit. To overcome compiler limits, I found the following solution, based on Bartek Banachewicz` code:

#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;
}

I know that this is possibly UB...

Answer 1

It would be fairly easy with macros using (recently re-discovered by me for my code) Boost.Preprocessor - I am not sure if it falls under "without using external code generators".

---

PP_ENUM version

Thanks to @TemplateRex for BOOST_PP_ENUM, as I said, I am not very experienced at PP yet :)

#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

The main difference with PP_ENUM is that it automatically adds the comma after each element and strips the last one.

---

PP_REPEAT version

#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

---

Remarks

It's actually very straightforward and easy to use, though it's up to you to decide if you will accept macros. I've personally struggled a lot with Boost.MPL and template techniques, to find PP solutions easy to read, short and powerful, especially for enumerations like those. Additional important advantage of PP over TMP is the compilation time.

As for the comma at the end, all reasonable compilers should support it, but in case yours doesn't, simply change the number of repetitions to 255 and add last case by hand.

You might also want to rename MACRO to something meaningful to avoid possible redefinitions.

Answer 2

I like to do it like this:

#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

• The difference with BOOST_PP_REPEAT is that BOOST_PP_ENUM generates a comma-separated sequence of values, so no need to worry about comma's and last-case behavior.
• Furthermore, it is recommended to make your macros really loud and obnoixous by using a NAMESPACE_PP_FUNCTION naming scheme.
• a small configuration thing is to omit the [256] in favor of [] in the array size so that you can more easily modify it later.
• Finally, I would recommend making your CountBit function template constexpr so that you also can initialize const arrays.