c++c++11compile-timeconstexprlogarithm

Compute at compile time the number of bits needed to encode N different states

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

// constexpr or template, either is ok

The results should be:

Input - Number of states Output - Bits needed
0 0 (or Not Defined)
1 0
2 1
3-4 2
5-8 3
9-16 4
17-32 5
... ...

Edit The initial question had a wrong formula and the algorithm shown was doing something completely different than what was intended. That's what some of the comments reference. I apologise and the question is now rewritten.

Solution

  • Due to the confusion caused by the initial question I chose to post this answer. This is built upon the answers of @DanielKO and @Henrik.

    The minimum number of bits needed to encode n different states:

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