Automatically pick a variable type big enough to hold a specified number
C++TemplatesTemplate Meta-ProgrammingC++ Problem Overview
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?
C++ Solutions
Solution 1 - C++
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.
Solution 2 - C++
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> {};
Solution 3 - C++
#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;
}
Solution 4 - C++
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
}
Solution 5 - C++
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.
Solution 6 - C++
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;
Solution 7 - C++
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.
Solution 8 - C++
#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
}
Solution 9 - C++
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.
Solution 10 - C++
#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.
Solution 11 - C++
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
Solution 12 - C++
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
Solution 13 - C++
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.
Solution 14 - C++
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.
Solution 15 - C++
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;