生成 table 指示编译时字节中第 n 个 1 位的位置

Question

我正在尝试弄清楚如何在 C++ (C++11) 的编译时生成一组预先计算的值。

数组声明为unsigned char precalcalated_positions[256][8]，对于precalcalated_positions[x][y]给出字节值x中从右数第y+1个1位的位位置（0-7）或者数字 8 如果 x

中没有那么多 1 位

因此，例如数组条目 precalculated_positions[51][2] 将是 4，因为 51 = 00110011 在二进制中，并且从右边数第 3 (2+1) 1 位等于 1<<4。

虽然我可以很容易地编写一个程序来生成这个数组的源代码，但我想知道编译器本身是否有可能在编译时生成这个数组，也许是通过使用一些聪明的模板元编程或者一些constexpr 函数？

在运行时（未优化）生成 table 的代码如下：

int calculate_index(unsigned char c,unsigned char pos)
{
    int mask = 1;
    for(int i=0;i<8;i++) {
        if (c&mask) {
            if (pos==0) {
                return i;
            } else {
                pos--;
            }
        }
        mask<<=1;
    }
    return 8;
}
void generate_table() {
   for(int i=0;i<256;i++) for(int j=0;j<8;j++) {
      precalulated_positions[i][j] = calculate_index(i,j);
   }
}

虽然我们真诚地感谢任何帮助，但请注意，这仅适用于 C++11。出于我的目的，我不能使用 C++14 的新结构。

如有不明之处，请追问，我会尽量详细说明。

Answer 1

所以，我没有意识到你不能使用 C++14。我想出了另一个仅使用 C++11 的解决方案。我在下面留下了 C++14 代码。

我将您的算法转换为递归版本（以适应 constexpr 函数），并使用模板参数包来填充 table.

template<int... Is>
struct Seq {};
template<int N, int... Is>
struct Gen : Gen<N-1, N-1, Is...> {};
template<int... Is>
struct Gen<0, Is...> : Seq<Is...> {};

constexpr auto computePosition(int c, int bit, int pos = 0) -> unsigned char {
    return pos == 8 ?
        8 :
        (c & (1 << pos)) == 0 ?
            computePosition(c, bit, pos+1) :
            bit == 0 ?
                pos :
                computePosition(c, bit-1, pos+1);
}

template<int c, int... Is>
constexpr auto generatePositions(Seq<Is...>) -> std::array<unsigned char, 8> {
    return {{ computePosition(c, Is)... }};
}

template<int c>
constexpr auto generatePositions() -> std::array<unsigned char, 8> {
    return generatePositions<c>(Gen<8>{});
}

template<int... Is>
constexpr auto generateTable(Seq<Is...>) -> std::array<std::array<unsigned char, 8>, 256> {
    return {{ generatePositions<Is>()... }};
}

constexpr auto generateTable() -> std::array<std::array<unsigned char, 8>, 256> {
    return generateTable(Gen<256>{});
}

Live example

C++14 版本：

struct Table {
    constexpr Table() : positions() {
        for (auto c = 0; c < 256; ++c) {
            for (auto i = 0; i < 8; ++i) {
                int mask = 1;
                auto pos = -1;
                auto bit = i;
                while (pos < 8 && bit >= 0) {
                    if (c & mask) {
                        --bit;
                    }
                    ++pos;
                    mask <<= 1;
                }
                positions[c][i] = pos;
            }
        }
    }

    unsigned char positions[256][8];
};

int main()
{
    constexpr auto precalculated_positions = Table();
    static_assert(precalculated_positions.positions[51][2] == 4, "wrong");
}

这些值在 Table 类型的任何变量的 positions 字段中。

Live example

生成 table 指示编译时字节中第 n 个 1 位的位置

generating table that indicates position of nth 1 bit in a byte at compile time

arrays

c++11

compile-time