Метапрограмма для подсчета битов - PullRequest
Новая
       4

Метапрограмма для подсчета битов

5 голосов
/ 12 октября 2010

Мне нужна утилита счетчика битов в C ++, которая способна подсчитывать количество старших значащих бит в числовом постоянном значении и представлять это число как постоянную времени компиляции.

Просто чтобы все было понятно - номер старшего значащего бита для набора числовых значений: 

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

Я новичок в программировании шаблонов, но я думаю, что так.

Пожалуйста, предоставьте несколько примеров кода, любая помощь будет оценена.

Ответы [ 2 ]

12 голосов
/ 12 октября 2010

Редактировать: Я совершенно неправильно понял, что вы хотели.

Вот что вы хотите:

Число значащих битов в 0 равно 0.

Количество значащих бит в x - это число значащих бит в x/2 плюс один.

Итак, вы получите: 

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;
};
1 голос
/ 12 октября 2010

Вот моя реализация;менее элегантный, чем у @ 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'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;
}

Пример вывода: 

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
...