How to figure out the smallest integral type that can represent a number, in compile time

Question

I need to figure out the smallest unsigned integral type that can represent a particular number, in compile time. Something like this...

//////////////////////////////////////////////////////////////////////////
template<size_t Bits>
struct uint_least{};

template<>
struct uint_least<8>{ typedef std::uint8_t type; };

template<>
struct uint_least<16>{ typedef std::uint16_t type; };

//////////////////////////////////////////////////////////////////////////
template<size_t max>
struct uint_least_bits
{
    static const size_t value = 14; // just a placeholder
};

//////////////////////////////////////////////////////////////////////////
template<size_t max>
class A
{
    typedef typename uint_least<uint_least_bits<max>::value>::type underlying_type;

    underlying_type m_X;
};

uint_least is meant to give you the smallest unsigned integral type that is at least Bits large and it should work for any value up to 64 (not just 8, 16, 32, 64 but also 1, 4, 13, etc).

uint_least_bits is meant to give you the minimum number of bits needed to represent max.

• How can I implement uint_least?
• How can I implement uint_least_bits?
• What types should bits, min, and max be? If the answer is a template type, how can I guard against invalid input?

The exact structuring of the traits doesn't matter. Feel free to scrap what I provided. I just need to provide a number and get back the smallest unsigned integral type that can hold it.

Answer 1

I did this just yesterday, what a coincidence. I'll leave it here, even though it's not exactly what you need(it fixes the best integral type thing anyway):

#include <type_traits>
#include <stdint.h>

template<size_t i>
struct best_type {
    typedef typename std::conditional<
        (i <= 8),
        uint8_t,
        typename std::conditional<
            (i <= 16),
            uint16_t,
            typename std::conditional<
                (i <= 32),
                uint32_t,
                uint64_t
            >::type
        >::type
    >::type type;
};

Then, you'd use it like this:

#include <type_traits>
#include <iostream>
#include <stdint.h>

template<size_t i>
struct best_type {
    typedef typename std::conditional<
        (i <= 8),
        uint8_t,
        typename std::conditional<
            (i <= 16),
            uint16_t,
            typename std::conditional<
                (i <= 32),
                uint32_t,
                uint64_t
            >::type
        >::type
    >::type type;
};   

int main() {
    std::cout << sizeof(best_type<2>::type) << std::endl;
    std::cout << sizeof(best_type<8>::type) << std::endl;
    std::cout << sizeof(best_type<15>::type) << std::endl;
    std::cout << sizeof(best_type<17>::type) << std::endl;
}

Live demo, here.

Answer 2

If you've got constexpr, this will work:

#include <climits>
#include <cstdint>
#include <cstddef>

inline
constexpr
unsigned
clz(unsigned x)
{
    return x == 0 ? sizeof(x)*CHAR_BIT : x & 0x80000000 ? 0 : 1 + clz(x << 1);
}

inline
constexpr
unsigned
clp2(unsigned x)
{
    return x == 0 ? 0 : 1 << (sizeof(x)*CHAR_BIT - clz(x-1));
}

inline
constexpr
unsigned
at_least8(unsigned x)
{
    return x < 8 ? 8 : x;
}

template<size_t Bits>
struct uint_least{};

template<>
struct uint_least<8>{ typedef std::uint8_t type; };

template<>
struct uint_least<16>{ typedef std::uint16_t type; };

template<>
struct uint_least<32>{ typedef std::uint32_t type; };

template<>
struct uint_least<64>{ typedef std::uint64_t type; };

template<size_t max>
struct uint_least_bits
{
    static const size_t value = clp2(max);
};

template<size_t max>
class A
{
    typedef typename uint_least<at_least8(uint_least_bits<max>::value)>::type underlying_type;

    underlying_type m_X;
};

int main()
{
    A<3> a;
}

If you don't have constexpr, you could translate clp2 into a template meta-function (and that's left as an exercise for the reader :-)).

Oh, disclaimer: Assumes a 32 bit unsigned. That could be generalized too if needed.