Sometimes, it is desirable to perform computations already at compile-time — either for efficiency or to avoid redundancy. Alas, what a compiler can compute at compile-time is rather limited — mostly just a combination of unary and binary operators. What if you need to do something more complex?
For the sake of illustration, I chose computing the (floored) log2 of an integer as an example, but the techniques presented below can be easily adapted to other use cases:
|
1 2 3 4 |
const int MY_CONST = STATIC_LOG2(1234); // Compute log2(1234) // at compile-time |
In C++ — provided you’re brave enough — you can always resort to template metaprogramming:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
template<int value, int shift> struct static_log2_impl { enum { result = value & (1 << shift) ? shift : static_log2_impl<value, shift - 1>::result }; }; template<int value> struct static_log2_impl<value, -1> { enum { result = -1 }; }; #define STATIC_LOG2(value)\ (static_log2_impl<value, sizeof(int) * CHAR_BIT - 1>::result) |
But since template metaprogramming was not deliberately built into C++ but rather discovered by accident, template metaprogramming code is far from pleasant to look at. If you are lucky and your compiler supports C++11 (or rather C++11’s constexpr feature), you have a better option:
|
1 2 3 4 5 6 7 8 9 10 |
constexpr int static_log2_constexpr_impl(int value, int shift) { return shift == -1 ? -1 : value & (1<< shift) ? shift : static_log2_constexpr_impl(value, shift - 1); } #define STATIC_LOG2(value)\ (static_log2_constexpr_impl(value, sizeof(int) * CHAR_BIT - 1)) |
It’s still recursive, but at least this solution is using real functions and not structs to achive its goal — much easier on the eyes!
But what if you code at the other end of the spectrum? What if you are limited to plain C?
Many years ago, I discovered the following technique that has proven useful in quite a few situations; it is used like this:
|
1 2 3 4 5 |
#define STATIC_LOG2_ARG 89 #include static_log2.h char myarray[STATIC_LOG2_VALUE]; // sizeof(myarray) == 6 |
The “argument” is passed via a symbolic constant (STATIC_LOG2_ARG), the computation is done by “calling the function” (by including static_log2.h) and the “return value” is stored in another symbolic constant (STATIC_LOG2_VALUE).
Here’s an excerpt of what’s contained in the static_log2.h header file:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#if STATIC_LOG2_ARG & (1 << 31) #define STATIC_LOG2_VALUE 31 #elif STATIC_LOG2_ARG & (1 << 30) #define STATIC_LOG2_VALUE 30 #elif STATIC_LOG2_ARG & (1 << 29) #define STATIC_LOG2_VALUE 29 #elif STATIC_LOG2_ARG & (1 << 28) #define STATIC_LOG2_VALUE 28 ... #elif STATIC_LOG2_ARG & (1 << 2) #define STATIC_LOG2_VALUE 1 #elif STATIC_LOG2_ARG & (1 << 1) #define STATIC_LOG2_VALUE 0 #else #define STATIC_LOG2_VALUE -1 #endif |
In the C++ examples, iteration is done using recursion, but here everything is unrolled/inlined.
For another case where this approach is employed, checkout this post. You probably don’t need this technique very often, but it’s good to have it in your bag of macro tricks.