编译编码n个不同状态所需的比特数的时间计算

Question

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

我需要在编译时计算(结果将用作非类型模板参数)存储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)
      );
}

这会产生正确的结果(for num_states_ != 0),但递归以指数方式爆发,对于任何大于10的输入(编译期间的内存使用量增长超过2GB,操作系统冻结且编译器崩溃)几乎无法使用.

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

Answer 1

存储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在反序列化时分配.

Answer 2

由于最初的问题引起的混乱，我选择发布此答案。这是建立在@DanielKO 和@Henrik 的回答之上的。

编码n不同状态所需的最小位数：

constexpr unsigned bitsNeeded(unsigned n) {
  return n <= 1 ? 0 : 1 + bitsNeeded((n + 1) / 2);
}

Answer 3

试试这个:

constexpr unsigned numberOfBits(unsigned x)
{
    return x < 2 ? x : 1+numberOfBits(x >> 1);
}

表达更简单,结果正确.

编辑:"正确的结果",如"提出的算法甚至没有接近"; 当然,我正在计算"代表值x的位数"; 如果要知道从0到x-1计数的位数,请从参数中减去1.要表示1024,您需要11位,从0到1023(1024个状态)计数,您需要10位.

编辑2:重命名函数以避免混淆.