Log2 (with C++ metaprogramming)

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 2^{11}=2048). 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:

template <int x>
 struct log2 { enum { value = 1 + log2<x/2>::value }; };
 
template <> struct log2<1> { enum { value = 1 }; };

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:

constexpr size_t log2(size_t n)
 {
  return ( (n<2) ? 1 : 1+log2(n/2));
 }

This can be used, as well, as a template argument. We’ll put that to use next week.

3 Responses to Log2 (with C++ metaprogramming)

  1. ajneu says:

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

    The code should be:

    constexpr size_t Log2(size_t n)
    {
        assert(n);
        return ( (n<2) ? 0 : 1+Log2(n/2));
    }
    
    
    Here's a test:
    
    #include 
    #include 
    #include 
    #include 
    
    constexpr size_t Log2(size_t n)
    {
        assert(n);
        return ( (n<2) ? 0 : 1+Log2(n/2));
    }
    
    int main()
    {
        for (int i = 1; i < 33; ++i) {
    	std::cout << "Log2(" << std::setw(3) << i << ") == " << Log2(i) << "     "
    		  << std::floor(std::log2(i)) << " == std::floor(std::log2(" << std::setw(3) << i << "))" << std::endl;
        }
        return 0;
    }
    
  2. ajneu says:

    Hello,

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

    The code should be:

    constexpr size_t Log2(size_t n)
    {
        assert(n);
        return ( (n<2) ? 0 : 1+Log2(n/2));
    }
    
    
    Here's a test:
    
    #include 
    #include 
    #include 
    #include 
    
    constexpr size_t Log2(size_t n)
    {
        assert(n);
        return ( (n<2) ? 0 : 1+Log2(n/2));
    }
    
    int main()
    {
        for (int i = 1; i < 33; ++i) {
    	std::cout << "Log2(" << std::setw(3) << i << ") == " << Log2(i) << "     "
    		  << std::floor(std::log2(i)) << " == std::floor(std::log2(" << std::setw(3) << i << "))" << std::endl;
        }
        return 0;
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: