Automatically pick a variable type big enough to hold a specified number

Question

Is there any way in C++ define a type that is big enough to hold at most a specific number, presumably using some clever template code. For example I want to be able to write :-

Integer<10000>::type dataItem;

And have that type resolve to the smallest type that is big enough to hold the specified value?

Background: I need to generate some variable defintions using a script from an external data file. I guess I could make the script look at the values and then use uint8_t, uint16_t, uint32_t, etc. depending on the value, but it seems more elegant to build the size into the generated C++ code.

I can't see any way to make a template that can do this, but knowing C++ templates, I'm sure there is a way. Any ideas?

Supersensible

Do you mean that dataItem should not exceed 10000 at runtime ? – Nahshu

@iammilind: I think what JohnB means is that for example Integer<10000>::type should resolve to uint16_t because you can't store 10000 in a uint8_t but you can store it in a uint16_t. – Excitant

@iammilind: He meant the template should define the nested type in such a way that it should be big enough to hold 10000. – Thermotensile

Unrelated to whether such a template could be made, I don't think that'll work for the situation that you describe: Templates are resolved at compile time, but you want to make a decision at runtime based on user input. You could just have a runtime function that computes the base-2 logarithm of the input numbers, though. – Becker

@Kerrek SB: The OP says that he's generating "variable definitions from an external data file". So presumably the OP is generating .h or .cpp files after parsing some other file. – Excitant

Yes I just want to pick the smallest type able to hold that value (or less). I don't need it checking – Supersensible

Yes I could manually write in my .h file uint16_t data1; uint8_t data2; etc but I thought that the compiler could do the work for me. – Supersensible

@JohnB: Since you're parsing the file yourself, why not have the parser check the minimum range and write out uint8_t or uint16_t, etc? For example if you find that the value you need to write out is 10000, then the parser will figure out that it'll also need to write out uint16_t. – Excitant

@In silico Yes I could do that, and that's likely what I'll do. It just looked elegent to do this, so I thought I'd ask if it was possible – Supersensible

I see -- if you are actually going to use the fixed-width types uint16_t etc, then you might as well let your preprocessor compute the correct type right there and then. If you do want some template magic that picks platform dependent types, see my answer below. – Becker

Did you not find python's simple dataItem = 1000 elegant? – Ventriloquist

Do you only want to choose an unsigned type? Do you have a lower bound as well as an upper bound? Or is this 10000 a constant and not an upper bound? – Sochor

For this particular application I needed unsigned types. And could find the maximum that would ever be needed for that field from an external data dictionary. – Supersensible

@Lie Ryan: where do you find python syntax to help in C++ templates? – Scharf

Answer 1

Boost.Integer already has facilities for Integer Type Selection:

boost::int_max_value_t<V>::least

The smallest, built-in, signed integral type that can hold all the values in the inclusive range 0 - V. The parameter should be a positive number.

boost::uint_value_t<V>::least

The smallest, built-in, unsigned integral type that can hold all positive values up to and including V. The parameter should be a positive number.

Homeo

Ha, so it does and I'm already using boost in the project so I guess I'll just use that! The answers to the question have all been good and very educational though :) – Supersensible

To use those type selection templates, #include <boost/integer.hpp> – Josie

Answer 2

Sure, it's possible. Here are the ingredients. Let's start with my two favorite meta-functions:

template<uint64_t N>
struct constant
{
    enum { value = N };
};

template<typename T>
struct return_
{
    typedef T type;
};

Then, a meta-function that counts the bits required to store a number:

template<uint64_t N>
struct bitcount : constant<1 + bitcount<(N>>1)>::value> {};

template<>
struct bitcount<0> : constant<1> {};

template<>
struct bitcount<1> : constant<1> {};

Then, a meta-function that counts the bytes:

template<uint64_t N>
struct bytecount : constant<((bitcount<N>::value + 7) >> 3)> {};

Then, a meta-function that returns the smallest type for a given number of bytes:

template<uint64_t N>
struct bytetype : return_<uint64_t> {};

template<>
struct bytetype<4> : return_<uint32_t> {};

template<>
struct bytetype<3> : return_<uint32_t> {};

template<>
struct bytetype<2> : return_<uint16_t> {};

template<>
struct bytetype<1> : return_<uint8_t> {};

And finally, the meta-function that you asked for:

template<uint64_t N>
struct Integer : bytetype<bytecount<N>::value> {};

Stalk

That's one of the neatest and best explained examples of template meta programming I've ever seen :) – Supersensible

Hehe ... anyway, my real "moral issue" with many of the answers is that using fixed-width types like uint16_t somehow obviates the need for any sort of TMP: If the size of the data type is already known from the standard, independent of the platform, then we don't really need a C++ solution - the OP's preprocessor can make the correct decision right away, and the result will be the same on all platforms. I thought this would be more interesting if you want to find the fitting primitive type independent of their sizes and of CHAR_BIT... but I'm not claiming that that would be useful :-) – Becker

Answer 3

#include <stdint.h>

template<unsigned long long Max>
struct RequiredBits
{
    enum { value =
        Max <= 0xff       ?  8 :
        Max <= 0xffff     ? 16 :
        Max <= 0xffffffff ? 32 :
                            64
    };
};

template<int bits> struct SelectInteger_;
template<> struct SelectInteger_ <8> { typedef uint8_t type; };
template<> struct SelectInteger_<16> { typedef uint16_t type; };
template<> struct SelectInteger_<32> { typedef uint32_t type; };
template<> struct SelectInteger_<64> { typedef uint64_t type; };

template<unsigned long long Max>
struct SelectInteger : SelectInteger_<RequiredBits<Max>::value> {};

int main()
{
    SelectInteger<12345>::type x = 12345;
}

Colpin

Beware, 256ull * 256 * 256 * 256 * 256 * 256 * 256 * 256 is zero. – Stalk

Personally, I think this is the best solution to the problem. – Stalk

I like this too :) How am I supposed to choose which one to accept! – Supersensible

@MaximYegorushkin Occam's razor = KISS in software parlance :) – Autocratic

Are you sure your initializing expression doesn't require constexpr support ? in other words, is this really C++03 compliant ? – Autocratic

@Autocratic Enumerator values are compile time constants, so it is C++03 compliant. – Colpin

Lol, no, this answer is misplaced; but fortunately I found the perfect answer right here: #16550131 – Autocratic

Answer 4

Do you necessarily want the smallest, as opposed to using int for types smaller than int?

If not, and your compiler supports it, could you do:

int main()
{
    typeof('A') i_65 = 0; // declare variable 'i_65' of type 'char'
    typeof(10) i_10 = 0; // int
    typeof(10000) i_10000 = 0; // int
    typeof(1000000000000LL) i_1000000000000 = 0; // int 64
}

Package

Beautiful. The question is tagged C++ but this should also be accepted by any C compiler that accepts typeof. – Zaria

Answer 5

How about a conditional:

#include <type_traits>
#include <limits>

template <unsigned long int N>
struct MinInt
{
  typedef typename std::conditional< N < std::numeric_limits<unsigned char>::max(),
       unsigned char, std::conditional< N < std::numeric_limits<unsigned short int>::max(),
         unsigned short int>::type,
         void*>::type>::type
    type;
};

This would have to be extended to encompass all desired types, in order; at the final stage you could use enable_if rather than conditional to have an instantiation error right there if the value is too large.

Becker

It will not work. std::numeric_limits<unsigned char>::max() is a function, which will be executed at runtime, while the std::conditional needs value at compile time. – Thermotensile

@Nawaz: Isn't that a constexpr? If not, use T(-1) instead. – Becker

I don't recognize std::conditional. Is it c++0x? – Supersensible

@JohnB: Yeah, but it's in TR1 as well, and you can trivially write it yourself, too - it's just the template version of the ternary ?:. – Becker

@LucDanton certainly not : #2738935 – Autocratic

@Autocratic That’s pre-C++11. There is no constexpr pre-C++11. – Zachar

Of course, but there already was the concept of constant expressions and what could be used as inline initializers for integers, or integral constant literals in template. numeric_limits was not a static expression (it was a static function) which is not evaluatable in constant expression. In C++11 it was made constexpr thanks to a very powerful standard point that makes functions evaulatable by the compiler. And in C++14 they may even be multiple lines. – Autocratic

This is much more portable than the other answers, if a tad clunky. – Cardioid

Answer 6

Easy peasy with C++11:

#include <cstdint>
#include <limits>
#include <type_traits>


template <class T, class U =
    typename std::conditional<std::is_signed<T>::value,
      std::intmax_t,
      std::uintmax_t
    >::type>
constexpr bool is_in_range (U x) {
  return (x >= std::numeric_limits<T>::min())
      && (x <= std::numeric_limits<T>::max());
}

template <std::intmax_t x>
using int_fit_type =
    typename std::conditional<is_in_range<std::int8_t>(x),
      std::int8_t,
      typename std::conditional<is_in_range<std::int16_t>(x),
        std::int16_t,
        typename std::conditional<is_in_range<std::int32_t>(x),
          std::int32_t,
          typename std::enable_if<is_in_range<std::int64_t>(x), std::int64_t>::type
        >::type
      >::type
    >::type;

template <std::uintmax_t x>
using uint_fit_type =
    typename std::conditional<is_in_range<std::uint8_t>(x),
      std::uint8_t,
      typename std::conditional<is_in_range<std::uint16_t>(x),
        std::uint16_t,
        typename std::conditional<is_in_range<std::uint32_t>(x),
          std::uint32_t,
          typename std::enable_if<is_in_range<std::uint64_t>(x), std::uint64_t>::type
        >::type
      >::type
    >::type;

Jakejakes

Answer 7

I think it should pick the smallest type which would hold the given integer:

class true_type {};
class false_type {};

template<bool> 
struct bool2type 
{ 
  typedef true_type  type; 
};

template<>
struct bool2type<false>
{
  typedef false_type  type;
};

template<int M, int L, int H>
struct within_range
{
   static const bool value = L <= M && M <=H;
   typedef typename bool2type<value>::type type;
};

template<int M, class booltype> 
struct IntegerType;

template<int Max> 
struct IntegerType<Max,typename within_range<Max, 0, 127>::type >
{
   typedef char type;
};

template<int Max> 
struct IntegerType<Max,typename within_range<Max, 128, 32767>::type >
{
   typedef short type;
};

template<int Max> 
struct IntegerType<Max,typename within_range<Max, 32768, INT_MAX>::type >
{
   typedef int type;
};

template <int Max>
struct Integer {
    typedef typename IntegerType<Max, true_type>::type type;
};

Test code:

int main() {
        cout << typeid(Integer<122>::type).name() << endl;
        cout << typeid(Integer<1798>::type).name() << endl;
        cout << typeid(Integer<890908>::type).name() << endl;
        return 0;
}

Output: (c=char, s=short, i=int - due to name mangling)

c
s
i

Demo : http://www.ideone.com/diALB

Note: of course, I'm assuming the size and the range of the types, and even despite of this I might have choosen the wrong range; if so, then providing the correct range to the within_range class template, one can pick smallest type for a given integer.

Thermotensile

Answer 8

#include <stdio.h>

#ifdef _MSC_VER
typedef unsigned __int8 uint8_t;
typedef unsigned __int16 uint16_t;
typedef unsigned __int32 uint32_t;
typedef unsigned __int64 uint64_t;
#else
#include <stdint.h> // i dunno
#endif

template <class T> struct Printer       { static void print()   { printf("uint64_t\n"); } };
template <> struct Printer<uint32_t>    { static void print()   { printf("uint32_t\n"); } };
template <> struct Printer<uint16_t>    { static void print()   { printf("uint16_t\n"); } };
template <> struct Printer<uint8_t>     { static void print()   { printf("uint8_t\n"); } };

//-----------------------------------------------------------------------------

template <long long N> struct Pick32 { typedef uint64_t type; };
template <> struct Pick32<0> { typedef uint32_t type; };

template <long long N> struct Pick16 { typedef typename Pick32<(N>>16)>::type type; };
template <> struct Pick16<0> { typedef uint16_t type; };

template <long long N> struct Pick8 { typedef typename Pick16<(N>>8)>::type type; };
template <> struct Pick8<0> { typedef uint8_t type; };

template <long long N> struct Integer
{
    typedef typename Pick8<(N>>8)>::type type;
};


int main()
{
    Printer< Integer<0ull>::type >::print(); // uint8_t
    Printer< Integer<255ull>::type >::print(); // uint8_t

    Printer< Integer<256ull>::type >::print(); // uint16_t
    Printer< Integer<65535ull>::type >::print(); // uint16_t

    Printer< Integer<65536ull>::type >::print(); // uint32_t
    Printer< Integer<0xFFFFFFFFull>::type >::print(); // uint32_t

    Printer< Integer<0x100000000ULL>::type >::print(); // uint64_t
    Printer< Integer<1823465835443ULL>::type >::print(); // uint64_t
}

Conglobate

Answer 9

Here we go, for unsigned types:

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

template <uint64_t N>
struct Integer {
    static const uint64_t S1 = N | (N>>1);
    static const uint64_t S2 = S1 | (S1>>2);
    static const uint64_t S4 = S2 | (S2>>4);
    static const uint64_t S8 = S4 | (S4>>8);
    static const uint64_t S16 = S8 | (S8>>16);
    static const uint64_t S32 = S16 | (S16>>32);
    typedef typename Integer<(S32+1)/4>::type type;
};

template <> struct Integer<0> {
    typedef uint8_t type;
};

template <> struct Integer<1> {
    typedef uint8_t type;
};

template <> struct Integer<256> {
    typedef uint16_t type;
};

template <> struct Integer<65536> {
    typedef uint32_t type;
};

template <> struct Integer<4294967296LL> {
    typedef uint64_t type;
};

int main() {
    std::cout << 8 << " " << typeid(uint8_t).name() << "\n";
    std::cout << 16 << " " << typeid(uint16_t).name() << "\n";
    std::cout << 32 << " " << typeid(uint32_t).name() << "\n";
    std::cout << 64 << " " << typeid(uint64_t).name() << "\n";
    Integer<1000000>::type i = 12;
    std::cout << typeid(i).name() << "\n";
    Integer<10000000000LL>::type j = 12;
    std::cout << typeid(j).name() << "\n";
}

Note that this doesn't necessarily pick the smallest applicable type, since there's nothing in principle to stop an implementation from having a 24 bit integer. But for "normal" implementations it's OK, and to include unusual sizes all you need to do to fix it is to change the list of specializations.

For implementations that don't have a 64-bit type at all you need to change the type of the template parameter N - or you could use uintmax_t. Also in the case the right shift by 32 might be dodgy.

For implementations that have a type bigger than uint64_t, there's trouble too.

Pricilla

You'll never reach 65536 with (N+1)/2 starting from 1000000. It does not work. – Adoree

@Steve: I would like to hear your comment on my solution. :-) – Thermotensile

@Didier: good point, fixed I think. There may be a more elegant fix. – Pricilla

Answer 10

#define UINT8_T   256
#define UINT16_T  65536
#define UINT32_T  4294967296

template<uint64_t RANGE, bool = (RANGE < UINT16_T)>
struct UInt16_t { typedef uint16_t type; };
template<uint64_t RANGE>
struct UInt16_t<RANGE, false> { typedef uint32_t type; };

template<uint64_t RANGE, bool = (RANGE < UINT8_T)>
struct UInt8_t { typedef uint8_t type; };
template<uint64_t RANGE>
struct UInt8_t<RANGE, false> { typedef typename UInt16_t<RANGE>::type type; };

template<uint64_t RANGE>
struct Integer {
  typedef typename UInt8_t<RANGE>::type type;
};

You can extend upto uint64_t or whatever your platform supports.

Demo.

Nahshu

Answer 11

No enum, just typedef.

#include<stdio.h>
#include<stdint.h>

template <unsigned long long V> struct valuetype
{
    typedef typename valuetype<(V & (V-1)) ? (V & (V-1)) : (V >> 1)>::val val;
};
template <> struct valuetype<(1ull << 0)> { typedef uint8_t val; };
template <> struct valuetype<(1ull << 8)> { typedef uint16_t val; };
template <> struct valuetype<(1ull << 16)> { typedef uint32_t val; };
template <> struct valuetype<(1ull << 32)> { typedef uint64_t val; };

int main ()
{
    valuetype<123>::val a = ~0;
    printf ("%llu\n", (unsigned long long) a);  
    valuetype<456>::val b = ~0;
    printf ("%llu\n", (unsigned long long) b);  
    valuetype<123456>::val c = ~0;
    printf ("%llu\n", (unsigned long long) c);  
    valuetype<123456123>::val d = ~0;
    printf ("%llu\n", (unsigned long long) d);
    valuetype<123456123456>::val e = ~0;
    printf ("%llu\n", (unsigned long long) e);
    return 0;
}

255
65535
4294967295
4294967295
18446744073709551615

Runge

Answer 12

A (IMHO) much more readable C++11 version :

#include <inttypes.h>
#include <cstdlib>
#include <type_traits>
#include <typeinfo>
#include <iostream>


template <long long n, typename ...An>
struct inttype;

template <long long n, typename A0, typename ...An>
struct inttype<n, A0, An...>{
  typedef A0 least;
};

template <long long n, typename A0, typename A1, typename ...An>
struct inttype<n, A0, A1, An...>{
  typedef typename std::conditional< n == (A0) n, A0, typename inttype<n, A1, An...>::least >::type least ;
};

template <long long n>
struct inttype<n>{
  typedef typename inttype<n, uint8_t, uint16_t, uint32_t, uint64_t>::least least;
};


int main(int argc, char * argv[])
{
  std::cout << sizeof(inttype<0x0ULL>::least) << std::endl;
  std::cout << sizeof(inttype<0xFFULL>::least) << std::endl;
  std::cout << sizeof(inttype<0xFFFULL>::least) << std::endl;
  std::cout << sizeof(inttype<0xFFFFFULL>::least) << std::endl;
  std::cout << sizeof(inttype<0xFFFFFFFFFULL>::least) << std::endl;
}

Pass to inttype the number you want to hold, and optionally the type you want to try, in ascending sizeof. It will then pick the first type so that the casting n doesn't change n. If no type specified (the case of the Op) defaults to all uint types

Camilacamile

Answer 13

You mean something along the lines of:

template <int MAX>
struct Integer {
    typedef typename Integer<MAX+1>::type type;
};

template <>
struct Integer<2147483647> {
    typedef int32_t type;
};

template <>
struct Integer<32767> {
    typedef int16_t type;
};

template <>
struct Integer<127> {
    typedef int8_t type;
};

And maybe another templated struct for UnsignedInteger.

You could maybe even use numeric_limits instead of the hard coded values.

Adoree

I want it to work for any number though, not just the ones I programmed explicit specializations for. – Supersensible

Hmm, good answer, but that looks like a recipe for hitting the compiler's template recursion limit. :) – Mudra

@Dark Falcon: true, compiler's template recursion limit is the issue! – Adoree

I wounder if this could be made to work by instead of adding 1 for each instantation, round it down to the nearest power of two, and then multiply up by 2 for each instantation... – Supersensible

Much quicker: typedef typename Integer<MAX | (MAX >> 1) | (MAX >> 4) | (MAX >> 16)>::type type;. This will quickly fill out bits to the right. – Pigling

Answer 14

I'm a bit late but...

#include <cstdint>
#include <cstdio>
#include <tuple>

template<uint64_t data, int8_t test_bit= sizeof(data)-1>
struct getMinimalByteSize{
    using type= typename std::conditional< (bool)(data & (uint64_t)0xFFL << (test_bit*8)),
        typename std::tuple_element_t<test_bit, std::tuple<uint8_t, uint16_t, uint32_t, uint32_t, uint64_t, uint64_t, uint64_t, uint64_t>>,
        typename getMinimalByteSize<data, test_bit - 1>::type>::type;};

template<uint64_t data>
struct getMinimalByteSize<data, -1>{using type = uint64_t;};

int main()
{
  static_assert(sizeof(getMinimalByteSize<0x0>::type)==8);
  static_assert(sizeof(getMinimalByteSize<0xFF>::type)==1);
  static_assert(sizeof(getMinimalByteSize<0xFFF>::type)==2);
  static_assert(sizeof(getMinimalByteSize<0xFFFFF>::type)==4);
  static_assert(sizeof(getMinimalByteSize<0xFFFFFFFFF>::type)==8);
}

The difference with all the other methods is on the testing. Instead of testing if the value is bigger than the biggest number possible given N bits, it goes byte for byte, testing if it is the last (most significant) non zero byte. If it is, then this is the minimal number of bits needed. Lastly we use a hand made list to fix the fact that there are not 24, 48, 56 bit integers defined in C++.

This is how this template metaprogram would look as a simple C function:

#include <stddef.h>

int tuple_element_t[]={8,16,32,32,64,64,64,64,64};

int getMinimalByteSize(uint64_t data, int8_t first_hi_byte = sizeof(data)-1){
    if (!data) return 0;
    /* Does the N bit of test is set? If so, we are done*/
    if (data &  (uint64_t)0xFFL << (first_hi_byte*8))
        return tuple_element_t[first_hi_byte];
    else/*Else, we tray with the next bit*/
        return getMinimalByteSize(data, first_hi_byte-1);}

Don't worry if you don't see it the first time, give yourself time . I've being working on AVRs for more than 10 years, in a platform where every byte counts. If you understand it in less than those 10 years, you already beat my.

Amputate

Does it look better my friend? – Coper

Answer 15

For enums, it might be useful to know about std::underlying_type.

Example:

typedef enum {west, north, east, south, dir_count} dir_t;
std::underlying_type_t<dir_t> tmp;

Callant