Вычисление времени компиляции количества битов, необходимых для кодирования n различных состояний

Минимальное количество битов, необходимое для хранения 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 при десериализации.

Попробуй это:

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

Более простое выражение, правильный результат.

EDIT: "правильный результат", например, "предложенный алгоритм даже близко не подходит"; конечно, я вычисляю «количество битов для представления значения x»; вычтите 1 из аргумента, если вы хотите знать, сколько битов нужно считать от 0 до x-1. Для представления 1024 нужно 11 бит, для счета от 0 до 1023 (1024 состояния) нужно 10.

EDIT 2: функция переименована, чтобы избежать путаницы.

Из-за путаницы, вызванной первоначальным вопросом, я решил опубликовать этот ответ. Это основано на ответах @DanielKO и @Henrik.

Минимальное количество бит, необходимое для кодирования n различных состояний:

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

может быть

constexpr int mylog(int n) {
    return (n<2) ?1:
           (n<4) ?2:
           (n<8) ?3:
           (n<16)?4:
           (n<32)?5:
           (n<64)?6:
           …
           ;
}

поскольку вы будете использовать его как параметр tempalte, вы можете проверить, что буст может предложить

В C++20 у нас есть (в заголовке <bit>):

template<class T>
  constexpr T log2p1(T x) noexcept;

Возвраты: Если x == 0, 0; в противном случае один плюс логарифм x по основанию 2, при этом любая дробная часть отбрасывается. Примечания. Эта функция не должна участвовать в разрешении перегрузки, если T не является целым числом без знака.

constexpr немного слабоват и будет до C++14. Я рекомендую шаблоны:

template<unsigned n> struct IntLog2;
template<> struct IntLog2<1> { enum { value = 1 }; };

template<unsigned n> struct IntLog2 {
private:
  typedef IntLog2<n - 1> p;
public:
  enum { value = p::value * p::value == n - 1 ? p::value + 1 : p::value };
};

Что-то, что я использовал в своем собственном коде:

static inline constexpr
uint_fast8_t log2ceil (uint32_t value)
/* Computes the ceiling of log_2(value) */
{
    if (value >= 2)
    {
        uint32_t mask = 0x80000000;
        uint_fast8_t result = 32;
        value = value - 1;

        while (mask != 0) {
            if (value & mask)
                return result;
            mask >>= 1;
            --result;
        }
    }
    return 0;
}

Он требует, чтобы C++14 использовался как constexpr, но у него есть приятное свойство, заключающееся в том, что он достаточно быстр во время выполнения — примерно на порядок быстрее, чем при использовании std::log и std::ceil — и я убедился, что он дает те же результаты для все представимые ненулевые значения (логарифм не определен для нуля, хотя 0 является разумным результатом для этого приложения; вам не нужны биты, чтобы различать нулевые значения), используя следующую программу:

#include <iostream>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include "log2ceil.hh"

using namespace std;

int main ()
{
    for (uint32_t i = 1; i; ++i)
    {
        // If auto is used, stupid things happen if std::uint_fast8_t
        // is a typedef for unsigned char
        int l2c_math = ceil (log (i) / log (2));
        int l2c_mine = log2ceil (i);
        if (l2c_mine != l2c_math)
        {
            cerr << "Incorrect result for " << i << ": cmath gives "
                 << l2c_math << "; mine gives " << l2c_mine << endl;
            return EXIT_FAILURE;
        }
    }

    cout << "All results are as correct as those given by ceil/log." << endl;
    return EXIT_SUCCESS;
}

Это также не должно быть слишком сложно обобщить на различную ширину аргумента.