title: Compile time computing of number of bits needed to encode n different states
body: <p><em>Edit:</em> 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.</p>
  
  <p>I need to compute <strong>at compile time</strong> (the result will be used as a non-type template parameter) the minimum number of bits needed to store <code>n</code> different states:</p>
  
  <pre><code>constexpr unsigned bitsNeeded(unsigned n);
  </code></pre>
  
  <p>or via template</p>
  
  <p>The results should be:</p>
  
  <pre><code>+-----------+--------+
  | 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   |
  |    ..     |   ..   |
  +-----------+--------+
  </code></pre>
  
  <hr>
  
  <p>The initial (somehow corrected) version for reference:</p>
  
  <p>I need to compute <strong>at compile time</strong> (the result will be used as a non-type template parameter) the minimum number of bits needed to store <code>n</code> different states i.e. the integral part <del>(rounded down)</del> rounded up of binary logarithm:</p>
  
  <p><img src="https://i.stack.imgur.com/kxVCZ.png" alt="ceil(log2(n))"></p>
  
  <pre><code>constexpr unsigned ceilLog2(unsigned n);
  </code></pre>
  
  <p>This is what I came up with (<strong>completely wrong</strong>):</p>
  
  <pre><code>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)
        );
  }
  </code></pre>
  
  <p><del>This produces the correct result</del> (for <code>num_states_ != 0</code>), but the recursion blows out exponentially and it is <strong>practically unusable</strong> for any input greater than 10 (the memory usage during compilation grows beyond 2GB, the OS freezes and the compiler crashes).</p>
  
  <p>How can I compute this at compile time in a practical manner?</p>