Metaprogram for bit counting

Question

I need bit counter utility in C++ that is capable of counting number of the most significant bit in a numeric constant value and present this number as compile-time constant.

Just to make everything clear - number of the most significant bit for a set of numeric values:

 255 => 8   (11111111b)
   7 => 3   (111b)
1024 => 11  (10000000000b)
  26 => 5   (11010b)

I'm new to the template programming but i think that's the way.

Please provide some code samples, any help would be appreciated.

Answer 1

Edit: I totally misread what you wanted.

Here's what you want:

The number of significant bits in 0 is 0.

The number of significant bits in x is the number of significant bits in x/2 plus one.

So you get:

template <unsigned int x>
struct SignificantBits {
    static const unsigned int n = SignificantBits<x/2>::n + 1;
};

template <>
struct SignificantBits<0> {
    static const unsigned int n = 0;
};

Answer 2

Here's my implementation; less elegant than @sepp2k's one, it follows a different approach, actually counting the bits and providing both the position of the MSB and the number of significant bits.

#include <iostream>
#include <limits>

// Number: the number to be examined; Bit: parameter used internally to specify the bit to
// examine (the work starts from the leftmost bit)
template<unsigned int Number, unsigned int Bit=std::numeric_limits<unsigned int>::digits-1>
class BitCounter
{
public:
    // Most Significant Bit number; if it's the current, fine, otherwise
    // delegate the work to another template that will examine the next bit
    static const int MSB=(Number&(1<<Bit))?Bit:BitCounter<Number,Bit-1>::MSB;
    // Count of significant bits - actually, MSB+1
    static const int Count=MSB+1;
};

// Corner case: we reached the first bit
template<unsigned int Number>
class BitCounter<Number,0>
{
public:
    // If it's 1, the MSB is the bit 0 (the rightmost), while if it's 0 it's "one before";
    // this is somewhat arbitrary to make Count get 0 for 0 and 1 for 1, you may want to
    // change it just to 0
    static const int MSB=Number==0?-1:0;
    static const int Count=MSB+1;
};

int main()
{
    std::cout<<BitCounter<255>::Count<<" "
             <<BitCounter<7>::Count<<" "
             <<BitCounter<1024>::Count<<" "
             <<BitCounter<26>::Count<<" "
             <<BitCounter<1>::Count<<" "
             <<BitCounter<0>::Count<<std::endl;
    return 0;
}

Sample output:

matteo@teoubuntu:~/cpp$ g++ tpl_bitcount.cpp -Wall -Wextra -ansi -pedantic -O3 -o tpl_bitcount.x && ./tpl_bitcount.x 
8 3 11 5 1 0