Compile time computing of number of bits needed to encode n different states

Question

Edit: In the initial question had a wrong formula and the algorithm tried was doing something completely different than what was intended. I apologise and I decided to rewrite the question to eliminate all the confusion.

I need to compute at compile time (the result will be used as a non-type template parameter) the minimum number of bits needed to store n different states:

constexpr unsigned bitsNeeded(unsigned n);

or via template

The results should be:

+-----------+--------+
| 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   |
|    ..     |   ..   |
+-----------+--------+

---

The initial (somehow corrected) version for reference:

I need to compute at compile time (the result will be used as a non-type template parameter) the minimum number of bits needed to store n different states i.e. the integral part (rounded down) rounded up of binary logarithm:

constexpr unsigned ceilLog2(unsigned n);

This is what I came up with (completely wrong):

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

This produces the correct result (for num_states_ != 0), but the recursion blows out exponentially and it is practically unusable for any input greater than 10 (the memory usage during compilation grows beyond 2GB, the OS freezes and the compiler crashes).

How can I compute this at compile time in a practical manner?

Answer 1

The minimum number of bits required to store n different states is 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;
}

Note that ceillog2(1) == 0. This perfectly fine, because if you want to serialize an object, and you know that one of its data members can only take on the value 42, you don't need to store anything for this member. Just assign 42 on deserialization.