# Bit packing and unpacking

I needed a variadic function to pack and unpack bits into integer types. This is my first attempt:

template<typename T>
constexpr T pack(bool b)
{
return b;
}

template<typename T, typename... Types>
constexpr T pack(bool b, Types... args)
{
return (b << sizeof...(Types)) | pack<T>(args...);
}

template<typename T, typename... Types>
void unpack(T packed, bool& b1)
{
b1 = packed & 1;
}

template<typename T, typename... Types>
void unpack(T packed, bool& b1, Types&... args)
{
b1 = packed & (1 << sizeof...(Types));
unpack(packed, args...);
}


Usage example:

int main(void)
{
std::cout << pack<int>(1, 0, 0, 1, 0, 1, 1, 0) << std::endl; // 150
std::cout << pack<int>(1, 0, 1) << std::endl; // 5
int val = pack<int>(1, 0, 1);
bool b1, b2, b3;
unpack(val, b1, b2, b3);
std::cout << b1 << " " << b2 << " " << b3 << std::endl; // 1 0 1
}


Does this code contain any bugs, can it be improved, and are variadic templates used appropriately here (I still don't master their syntax)?

• Two minor things I see: 1.) Replace each std::endl with "\n" 2.) In C++, main() doesn't need a void parameter.
– Jamal
Apr 4 '14 at 17:50
• OK, thanks. Anything about the core parts?
– gd1
Apr 4 '14 at 17:52
• Nothing that I can see. I'm not familiar with variadic templates.
– Jamal
Apr 4 '14 at 17:53

## Missing overflow check

One serious flaw that I see in this code is that the user needs to determine the number of parameters to unpack. This is a no go for a function whose output depends on a runtime input. Even worse there is no check that would tell the user that the actual number overflows the number of bits given to be unpacked into.

One possible solution would be to return an std::vector<bool> to fit the whole number.

The other solution would be to retain the current interface but to introduce error notification (by exception or return code).

## Unnecessary template parameter

Another thing regarding the unpack function: It seems that you don't need the Types parameter in the recursion end, so it becomes:

template<typename T>
void unpack(T packed, bool& b1)
{
b1 = packed & 1;
}


## Naming

The function parameter names could be better. I assume b1 is only appropriate in the top level call of the function. I cannot decide on a better name now, but it should indicate that it is the current bit. Likewise, args should be named remainingBits or something like this.

• The unnecessary template parameter is a plain oversight. About the rest I will think about it - I will never use a vector, this is exactly the point of this exercise, but if there is a way to make things more robust without a vector, I'll pursue it. About the naming, I have often seen "head" and "tail" but I don't find them quite appropriate.
– gd1
Apr 4 '14 at 18:00
• If it is only for the sake of making it "static" then you could make the packed parameter a template parameter, thus removing the possibility of runtime values that forbid the use of the specific parameter list. Apr 4 '14 at 18:04
• The pack() function needs to be evaluable also at compile-time (provided the passed arguments are), and actually it should be now - I hope the compiler is able to understand it - so that you can even use it in a switch case. The unpack() function should accept whatever packed value at runtime. I will really think about this, but while I consider very valuable writing robust code, I think this is one of the cases in which the client should be really aware of what it's doing. The performance of this should be no worse than a handcrafted sequence of bitwise operations.
– gd1
Apr 4 '14 at 18:09
• It is hard to be aware of the value of runtime variables if you don't check them. And if you check them beforehand you might forget to update the check together with the function call. Best way is to let the function itself do the checking and report an error if there is one. I find it a fairly harsh decision to put the burden onto the user of this function. Apr 4 '14 at 18:12
• We have vector's operator[] that doesn't necessarily check the boundaries (and many implementations don't), and virtually any function in the C++ standard library is prone to undefined behavior. This thing should perform as fast as it can and I do not want to introduce any branching, not to mention dynamic memory allocation. (PS: I forgot... +1 for your excellent answer)
– gd1
Apr 4 '14 at 18:17

I guess you are aware of std::bitset and you have your own reasons for doing this. Your pack seems fine, but unpack requires the user to set up a particular number of bool variables, which is not convenient. An alternative could be to use an std::array for the output:

template<size_t N>
using size = std::integral_constant<size_t, N>;

template<size_t N, typename T>
void unpack(size<N>, array<bool, N>& a, T) { }

template<size_t I, size_t N, typename T>
void unpack(size<I>, array<bool, N>& a, T packed)
{
a[N-I-1] = (packed & (1 << I)) != 0;
unpack(size<I+1>(), a, packed);
}

template<typename T>
std::array<bool, 8*sizeof(T)>
unpack(T packed)
{
std::array<bool, 8*sizeof(T)> a = {};
unpack(size<0>(), a, packed);
return a;
}


which can be used like this

int val = pack<int>(1, 0, 1);
std::cout << unpack(val) << std::endl;
// prints 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1


assuming a simple streaming operator

template<typename S, typename T, size_t N>
S& operator<<(S& s, const std::array<T, N>& a)
{
for (auto i : a)
s << i << " ";
return s;
}


This way you know for sure there is no overflow in the output.

Now, std::vector is another alternative for output that may benefit from its compact std::vector<bool> specialization (and std::bitset of course). On the other hand, using std::array, one may obtain a really constexpr version of unpack, without recursion. pack may similarly be non-recursive, remaining constexpr. If you like this potential, I can elaborate.

Update: constexpr version

It turns out pack is quite tricky to make non-recursive and constexpr, but as promised, here is a non-recursive, constexpr version of unpack (complete, live example):

template <size_t... N>
struct sizes { using type = sizes <N...>; };

template<size_t N, size_t... I, typename T>
constexpr std::array<bool, N>
unpack(sizes<I...>, T packed)
{
return std::array<bool, N>{{(packed & (1 << (N-I-1))) != 0 ...}};
}

template<size_t N, typename T>
constexpr std::array<bool, N>
unpack(T packed)
{
return unpack<N>(typename Range<N>::type(), packed);
}

template<typename T, size_t N = 8*sizeof(T)>
constexpr std::array<bool, N>
unpack(T packed) { return unpack<N>(packed); }


where Range<N> contains sequence 0,...N-1 and is defined here. Now you can use it like this:

int val = pack<int>(1, 0, 1);

// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
std::cout << unpack(val) << std::endl;

// 0 0 0 0 0 1 0 1
std::cout << unpack<8>(val) << std::endl;


The first version returns the entire array needed to represent the precision of the given (integral) type. The second allows you to specify a shorter length for the array; the remaining (leftmost) bits are discarded.

• Altough I am not the OP I would like to hear about the constexpr version of unpack :) Apr 4 '14 at 18:43
• Well obviously yes.
– gd1
Apr 4 '14 at 18:44
• Ok, I will be back as soon as possible... :-)
– iavr
Apr 4 '14 at 18:46
• @gd1 Sorry, I forgot, it's just a shortcut. See edit for the definition.
– iavr
Apr 4 '14 at 18:49
• @Nobody,gd1 Updated with constexpr unpack.
– iavr
Apr 4 '14 at 19:43