Geek Answers Handbook

Metaprogram for counting bits

I need a bit counter utility in C ++ that can count the number of the most significant bits in a numeric constant value and represent that number as a compile time constant.

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

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

I am new to template programming, but I think so.

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

+5
source share
2 answers

Edit: I completely misunderstood what you wanted.

Here is what you want:

The number of significant bits at 0 is 0.

The number of significant bits in xis the number of significant bits in x/2plus 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;
};
+12

; , @sepp2k, , MSB, .

#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 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 1, the MSB is the bit 0 (the rightmost), while if it 0 it "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;
}

:

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
+1

More articles:


All Articles