CODEWITHSUNDEEP
c++
Neil Kirk
Neil Kirk

Reputation: 21803

Problems using template meta-programming to count number of set bits in integer

As an experiment, I'm trying to write template code to count the number of set bits in an integer at compile-time. Here is my first attempt:

template<unsigned long long x>
struct BitCount
{
    static const int result = (x == 0) ? 0 : ((x & 1) + BitCount<(x >> 1)>::result);
};

This gives errors.

Visual Studio 2013

error C2065: 'result' : undeclared identifier

ideone.com

error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating ‘BitCount<0ull>::result’

How can I fix this error properly?

Ok so I changed it to

#include <iostream>
using namespace std;

template<unsigned long long x>
struct BitCount
{
    static const int result;
};

template<unsigned long long x>
const int BitCount<x>::result = (x == 0) ? 0 : ((x & 1) + BitCount<(x >> 1)>::result);

template<unsigned long long x>
int bitcount()
{
    return BitCount<x>::result;
}

int main()
{
    cout << bitcount<5>() << endl;
    cout << bitcount<1>() << endl;
    cout << bitcount<3>() << endl;
    cout << bitcount<0>() << endl;
    return 0;
}

ideone.com correctly outputs: 2 1 2 0

Visual Studio 2013 incorrectly outputs: 1 1 2 0

Is this a bug in VS or is something in my code incorrect?

Thanks!

Upvotes: 1

Views: 859

Answers (3)

Deduplicator
Deduplicator

Reputation: 45674

You need to specialize for the base-case, or you get infinite compile-time recursion there (the definition of the base-case is dependent on the definition of the base-case).
Also, it looks better if you inline the initialization:

template<unsigned long long x>
struct PopCount
{
    static const int result = (x&1)+BitCount<(x>>1)>::result;
};
template<>
struct PopCount<0ULL>
{
    static const int result = 0;
}

BTW: Using constexpr for the result member instead of const static is better, even better a function instead (C++11):

constexpr int popCount(unsigned long long x) {
    return x ? int(x&1) + popCount(x>>1) : 0;
}

As a last step, make the function iterative for better performance when executing it at runtime (C++14).

constexpr int popCount(unsigned long long x) {
    int r = 0;
    for(; x; x &= x-1)
        ++r;
    return r;
}

This assignment x &= x-1; clears the lowest-order set bit, so fewer iterations neccessary.

Upvotes: 2

Jarod42
Jarod42

Reputation: 217810

You may use the following:

template<unsigned long long x>
struct BitCount
{
    static constexpr const int result = (x & 1) + BitCount<(x >> 1)>::result;
};

template<>
struct BitCount<0>
{
    static constexpr const int result = 0;
};

Live example

or simply a constexpr function

constexpr int bitCount(unsigned long long x)
{
    return (x == 0) ? 0 : int(x & 1ULL) + bitCount(x >> 1);
}

BTW, you may use the bit trick x & (x-1) to mask off the lowest set bit instead of doing x >> 1 as follow:

constexpr int bitCount(unsigned long long x)
{
    return (x == 0) ? 0 : 1 + bitCount(x & (x - 1));
}

Upvotes: 1

Oktalist
Oktalist

Reputation: 14714

You need a specialization for the terminating case of zero:

template<>
struct BitCount<0>
{
    static const int result = 0;
};

Otherwise, you simply rely on the primary template so that BitCount<0>::result is defined as true ? 0 : BitCount<0>::result which is an endlessly recursive template instantiation. It still needs to instantiate the else-clause even if it isn't evaluated.

Upvotes: 5

Related Questions