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?

Do you mean that `dataItem` should not exceed `10000` at runtime ? — iammilind, Aug 12 '11 at 10:30
@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`. — In silico, Aug 12 '11 at 10:32
@iammilind: He meant the template should define the nested `type` in such a way that it should be big enough to hold `10000`. — Nawaz, Aug 12 '11 at 10:33
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. — Kerrek SB, Aug 12 '11 at 10:36
@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. — In silico, Aug 12 '11 at 10:37
Yes I just want to pick the smallest type able to hold that value (or less). I don't need it checking — jcoder, Aug 12 '11 at 10:37
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. — jcoder, Aug 12 '11 at 10:38
@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`. — In silico, Aug 12 '11 at 10:39
@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 — jcoder, Aug 12 '11 at 10:41
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. — Kerrek SB, Aug 12 '11 at 10:46
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? — hippietrail, Aug 13 '11 at 07:31
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. — jcoder, Aug 13 '11 at 10:10
@Lie Ryan: where do you find python syntax to help in C++ templates? — Zoey, Aug 16 '11 at 18:38

score 63 · Accepted Answer · answered Aug 12 '11 at 12:07

63

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.

answered Aug 12 '11 at 12:07

Georg Fritzsche

97,545
26
194
236

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 :) – jcoder Aug 12 '11 at 12:16
To use those type selection templates, `#include ` – Kai Petzke May 08 '21 at 08:49

fredoverflow · Answer 2 · 2011-08-12T11:33:59.203

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> {};

That's one of the neatest and _best explained_ examples of template meta programming I've ever seen :) — jcoder, Aug 12 '11 at 11:53
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 :-) — Kerrek SB, Aug 13 '11 at 10:49

score 27 · Answer 3 · edited Aug 12 '11 at 11:57

27

#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;
}

edited Aug 12 '11 at 11:57

fredoverflow

256,549
94
388
662

answered Aug 12 '11 at 11:12

Maxim Egorushkin

131,725
17
180
271

6

Beware, `256ull * 256 * 256 * 256 * 256 * 256 * 256 * 256` is zero. – fredoverflow Aug 12 '11 at 11:28
2

Personally, I think this is the best solution to the problem. – fredoverflow Aug 12 '11 at 12:05
I like this too :) How am I supposed to choose which one to accept! – jcoder Aug 12 '11 at 13:47
@MaximYegorushkin Occam's razor = KISS in software parlance :) – v.oddou Dec 22 '14 at 01:35
Are you sure your initializing expression doesn't require `constexpr` support ? in other words, is this really C++03 compliant ? – v.oddou Dec 22 '14 at 01:38
@v.oddou Enumerator values are compile time constants, so it is C++03 compliant. – Maxim Egorushkin Dec 22 '14 at 10:31
Lol, no, this answer is misplaced; but fortunately I found the perfect answer right here: http://stackoverflow.com/questions/16549631/conditional-operator-in-constant-expression – v.oddou Dec 25 '14 at 02:48

score 7 · Answer 4 · answered Aug 12 '11 at 14:20

7

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
}

answered Aug 12 '11 at 14:20

Jack V.

1,381
6
20

1

Beautiful. The question is tagged C++ but this should also be accepted by any C compiler that accepts `typeof`. – Pascal Cuoq Aug 13 '11 at 21:43

score 6 · Answer 5 · answered Aug 12 '11 at 10:43

6

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.

answered Aug 12 '11 at 10:43

Kerrek SB

464,522
92
875
1,084

1

It will not work. `std::numeric_limits::max()` is a function, which will be executed at runtime, while the `std::conditional` needs value at compile time. – Nawaz Aug 12 '11 at 10:47
1

@Nawaz: Isn't that a `constexpr`? If not, use `T(-1)` instead. – Kerrek SB Aug 12 '11 at 10:48
I don't recognize std::conditional. Is it c++0x? – jcoder Aug 12 '11 at 10:55
1

@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 `?:`. – Kerrek SB Aug 12 '11 at 11:03
@LucDanton certainly not : http://stackoverflow.com/questions/2738435/using-numeric-limitsmax-in-constant-expressions – v.oddou Dec 22 '14 at 01:41
@v.oddou That’s pre-C++11. There is no `constexpr` pre-C++11. – Luc Danton Dec 22 '14 at 06:06
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. – v.oddou Dec 22 '14 at 06:41
This is much more portable than the other answers, if a tad clunky. – Pharap May 04 '17 at 09:43

score 5 · Answer 6 · answered Jul 07 '15 at 15:02

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;

score 3 · Answer 7 · answered Aug 12 '11 at 11:06

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.

score 2 · Answer 8 · answered Aug 12 '11 at 11:02

#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
}

score 1 · Answer 9 · answered Jan 24 '17 at 20:08

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

score 1 · Answer 10 · answered Jul 09 '20 at 11:31

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

Steve Jessop · Answer 11 · 2011-08-12T11:32:25.567

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.

You'll never reach 65536 with (N+1)/2 starting from 1000000. It does not work. — Didier Trosset, Aug 12 '11 at 10:55
@Steve: I would like to hear your comment on my solution. :-) — Nawaz, Aug 12 '11 at 11:07
@Didier: good point, fixed I think. There may be a more elegant fix. — Steve Jessop, Aug 12 '11 at 11:25

iammilind · Answer 12 · 2011-08-12T15:52:59.883

#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.

alfredo lavín · Answer 13 · 2020-07-08T05:06:31.407

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.

Does it look better my friend? – alfredo lavín Jun 27 '20 at 03:11 — alfredo lavín, Jun 27 '20 at 03:11

score 0 · Answer 14 · answered Apr 21 '21 at 14:55

0

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;

answered Apr 21 '21 at 14:55

SuibianP

99
1
11

score 0 · Answer 15 · answered Aug 12 '11 at 10:36

0

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.

answered Aug 12 '11 at 10:36

Didier Trosset

36,376
13
83
122

I want it to work for _any_ number though, not just the ones I programmed explicit specializations for. – jcoder Aug 12 '11 at 10:37
6

Hmm, good answer, but that looks like a recipe for hitting the compiler's template recursion limit. :) – Dark Falcon Aug 12 '11 at 10:37
@Dark Falcon: true, compiler's template recursion limit is the issue! – Didier Trosset Aug 12 '11 at 10:40
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... – jcoder Aug 12 '11 at 10:43
3

Much quicker: `typedef typename Integer> 1) | (MAX >> 4) | (MAX >> 16)>::type type;`. This will quickly fill out bits to the right. – MSalters Aug 12 '11 at 10:44

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

15 Answers15

Linked