c++ - 编译时计算对n种不同状态进行编码所需的位数

编辑:在最初的问题中有一个错误的公式，尝试的算法所做的事情与预期的完全不同。我很抱歉，我决定重写这个问题，以消除所有的困惑。

我需要在编译时计算 (结果将用作非类型模板参数)以存储n不同状态所需的最小位数:

constexpr unsigned bitsNeeded(unsigned n);

或通过模板

结果应为:

+-----------+--------+
| number of | bits   |
| states    | needed |
+-----------+--------+
|     0     |    0   | * or not defined
|           |        |
|     1     |    0   |
|           |        |
|     2     |    1   |
|           |        |
|     3     |    2   |
|     4     |    2   |
|           |        |
|     5     |    3   |
|     6     |    3   |
|     7     |    3   |
|     8     |    3   |
|           |        |
|     9     |    4   |
|    10     |    4   |
|    ..     |   ..   |
|    16     |    4   |
|           |        |
|    17     |    5   |
|    18     |    5   |
|    ..     |   ..   |
+-----------+--------+

初始(经某种方式更正)以供引用:

我需要在编译时计算 (结果将用作非类型模板参数)存储n不同状态所需的最小位数，即二进制对数的整数部分(四舍五入):

constexpr unsigned ceilLog2(unsigned n);

这是我想出的(完全错误的):

constexpr unsigned intLog2(unsigned num_states_) {
  return
    num_states_ == 1 ?
      1 :
      (
      intLog2(num_states_ - 1) * intLog2(num_states_ - 1) == num_states_ - 1 ?
        intLog2(num_states_ - 1) + 1 :
        intLog2(num_states_ - 1)
      );
}

这会产生正确的结果(对于num_states_ != 0)，但是递归运算会成指数增长，对于任何大于10的输入，实际上是不可用的(编译期间的内存使用量超过2GB，OS冻结并且编译器崩溃)。

如何在编译时以实用的方式计算此值？

最佳答案

存储n不同状态所需的最小位数是ceil(log2(n))。

constexpr unsigned floorlog2(unsigned x)
{
    return x == 1 ? 0 : 1+floorlog2(x >> 1);
}

constexpr unsigned ceillog2(unsigned x)
{
    return x == 1 ? 0 : floorlog2(x - 1) + 1;
}

注意ceillog2(1) == 0。这非常好，因为如果您要序列化一个对象，并且知道其数据成员之一只能采用42值，则无需为此成员存储任何内容。只需在反序列化上分配42即可。