C++ meta-programming a powerful tool. Not only can you use it to build generic types (such as the STL’s std::list), you can also use it to have compile-time evaluation. Let’s have a look at a simple problem that can be solved in two very different ways: computing the Log base 2 of an integer.

The goal here is to find how many bits you need to store a range of values. For example, to store the range from 0 to 2000, you’d need 11 bits (because ). Normally, you’d write a (normal) function, likely using bit-twiddling hacks to speed the computation up. But that function wouldn’t be usable as a template parameter.

That means that the solution is itself likely a template, or some kind of compile-time expression. Template arguments don’t have to be types, they can be constants, and we could exploit that to create a template class, or struct, to compute the log2 “function”. What we need is a general case, for x, and an explicit specialization for the base case, when, say, x is 1. That’s what I came up with:

I’ve tried to get rid of the struct by using enum class, but for some reason, the compiler refuses explicitly to use enum classes. Well, whatever, this solution works perfectly, and computes the desired values: log2<127>::value will yield 7, the number of bits to store values from 0 to 127.

* * *

C++11 introduces the concept of constexpr that can be used to instruct the compiler that an expression is really constant, without side-effects, and that it can therefore be evaluated at compile-time if applied on constant arguments. The above templates can be replaced by a much friendlier function:

This entry was posted on Tuesday, March 22nd, 2016 at 13:09 pm and is filed under algorithms, C-plus-plus. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

I may have adjusted it so that 1 and 0 take 1 bit (log2 0 would be, according to the strict definition of log, -infinity, which is infintely inconvenient).

RT @petriefriends: I is for Ichneumon
The Ichneumon or Egyptian mongoose (Herpestes ichneumon) is larger than a domestic cat. It was... htt… 15 hours ago

Your C++11 code is off-by-one!

The code should be:

I may have adjusted it so that 1 and 0 take 1 bit (log2 0 would be, according to the strict definition of log, -infinity, which is infintely inconvenient).

Hello,

your C++11 code is off-by-one!

The code should be: