Store array integers using smallest possible amount of memory. Uses a lot C++ template metaprogramming.

tightlypacked.hh

#include <array>
#include <tuple>

typedef unsigned int _uint;

template <_uint _shift, _uint _size>
struct _FieldDescription {
    static const _uint shift = _shift;
    static const _uint size = _size;
};
#define DEBUG(name) //std::cout << #name << ": " << name << std::endl

template <int fields, typename Field>
class _PackedAccessor {
    std::array<uint8_t, fields>& arr;

    static const _uint firstItem = Field::shift / 8;
    static const _uint lastItem = (Field::shift + Field::size - 1) / 8;
    static const _uint firstBit = Field::shift % 8;
    static const _uint firstEndBit = (lastItem == firstItem) ? (Field::shift + Field::size) : 8;
    static const _uint firstSize = firstEndBit - firstBit;
    static const _uint lastItemEndBit = uint((int(Field::size - firstSize) - 1) % 8 + 1);
    static const _uint middleBitCount = (Field::size - firstSize - lastItemEndBit);
    static_assert((middleBitCount % 8) == 0, "");
    static const _uint middleCount = middleBitCount / 8;
public:
    _PackedAccessor(std::array<uint8_t, fields>& arr): arr(arr) {}

    inline _PackedAccessor& operator=(uint32_t v) {
        arr[firstItem] &= ~(((uint32_t(1)<<firstSize)-1) << firstBit);
        arr[firstItem] |= ((v & ((uint32_t(1)<<firstSize)-1)) << firstBit);

        for(_uint i=1; i < lastItem - firstItem; i++)
            arr[firstItem + i] = (v >> (firstSize + i * 8 - 8)) & 0xFF;

        if(lastItem != firstItem) {
            arr[lastItem] &= ~((uint32_t(1)<<lastItemEndBit)-1);
            arr[lastItem] |= (v >> (firstSize + middleBitCount)) & ((uint32_t(1)<<lastItemEndBit)-1);
        }

        return *this;
    }

    inline operator uint32_t() const {
        uint32_t result = 0;

        DEBUG(firstItem);
        DEBUG(lastItem);
        DEBUG(firstBit);
        DEBUG(firstEndBit);
        DEBUG(firstSize);
        DEBUG(lastItemEndBit);
        DEBUG(middleBitCount);
        DEBUG(middleCount);

        result = (uint32_t(arr[firstItem]) >> firstBit) & ((uint32_t(1)<<firstSize)-1);
        for(_uint i=1; i < lastItem - firstItem; i++)
            result |= (uint32_t(arr[firstItem + i]) << _uint(firstSize + 8 * i - 8));

        if(lastItem != firstItem)
            result |= (uint32_t(arr[lastItem]) & ((uint32_t(1)<<lastItemEndBit)-1))
                << _uint(firstSize + middleBitCount);

        return result;
    }
};

template <int i, int size, typename Fields>
inline _PackedAccessor<size, typename std::tuple_element<i, Fields>::type >
_packed_get(std::array<uint8_t, size>& arr) {
    return _PackedAccessor<size, typename std::tuple_element<i, Fields>::type >(arr);
}

template <int Size, typename Fields>
class _PackedTuple {
public:
    std::array<uint8_t, Size> storage;
    static const int size = Size;

    template <int i>
    _PackedAccessor<size, typename std::tuple_element<i, Fields>::type> get() {
        return _packed_get<i, size, Fields>(storage);
    }
};

template <typename First, typename Rest>
struct _TupleCar {
};

template <typename First, typename... RestTypes>
struct _TupleCar<First, std::tuple<RestTypes...> > {
    using Type = std::tuple<First, RestTypes...>;
};

template <int shift, int... args>
struct _PackedTupleCalc {};

template <int shift, int size, int... rest>
struct _PackedTupleCalc<shift, size, rest...> {
    using Next = _PackedTupleCalc<shift + size, rest...>;
    using Fields = typename _TupleCar<_FieldDescription<shift, size>, typename Next::Fields>::Type;
    static const int byte_size = Next::byte_size;
};

template <int shift>
struct _PackedTupleCalc<shift> {
    using Fields = std::tuple<>;
    static const int byte_size = (shift + 7) / 8;
};

template <typename Calc>
using _AutosizedPackedTuple = _PackedTuple<Calc::byte_size, typename Calc::Fields>;

template <int... args>
using PackedTuple = _AutosizedPackedTuple<_PackedTupleCalc<0, args...> >;

template <int n>
struct DownLog2 {
    static const int value = DownLog2<n / 2>::value + 1;
    static const int valueFor = DownLog2<n / 2>::valueFor * 2;
};

template <>
struct DownLog2<1> {
    static const int value = 0;
    static const int valueFor = 1;
};

template <int n>
struct Log2 {
    using Down = DownLog2<n>;
    static const int value = (Down::valueFor == n) ? Down::value : (Down::value + 1);
};