Métaprogrammes pour le comptage de bits

J'ai besoin d'un utilitaire de compteur de bits en C++ capable de compter le nombre du bit le plus significatif dans une valeur constante numérique et de présenter ce nombre comme une constante de temps de compilation.Métaprogrammes pour le comptage de bits

Juste pour faire tout clair - nombre de bit le plus significatif pour un ensemble de valeurs numériques:

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

Je suis nouveau à la programmation du modèle, mais je pense que ce chemin.

S'il vous plaît fournir quelques exemples de code, toute aide serait appréciée.

Source

2010-10-12 Keynslug

En d'autres termes, vous devez 'étage (lg (n)) + 1', où' lg' est le logarithme en base 2. – outis

Quelle serait la valeur correcte pour 0? –

Oui, j'ai juste besoin de floor (lg (n)) + 1'. '0 'signifie qu'aucun bit n'est requis pour stocker ce nombre, donc le résultat est égal à 0 également. – Keynslug

Modifier: J'ai totalement mal lu ce que vous vouliez.

Voici ce que vous voulez:

Le nombre de bits significatifs dans 0 est 0.

Le nombre de bits significatifs dans x est le nombre de bits significatifs dans x/2 plus un.

Ainsi, vous obtenez:

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; 
};

Source

2010-10-12 10:14:34 sepp2k

C++ détient toujours des profondeurs plus profondes pour moi. Impressionnant. –

OK! excellente solution, mais je présume que je devrais éditer la question un peu. – Keynslug

Ce modèle donne le nombre de '1' bits, mais pas le nombre minimum de bits nécessaires pour stocker la valeur. Pour cela, vous devez remplacer le '(x% 2)' par '1'. –

Voilà ma mise en œuvre; moins élégant que celui de @ sepp2k, il suit une approche différente, en comptant les bits et en fournissant à la fois la position du MSB et le nombre de bits significatifs.

#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; 
}

Exemple de sortie:

[email protected]:~/cpp$ g++ tpl_bitcount.cpp -Wall -Wextra -ansi -pedantic -O3 -o tpl_bitcount.x && ./tpl_bitcount.x 
8 3 11 5 1 0

Source

2010-10-12 10:43:31

Métaprogrammes pour le comptage de bits

Répondre

Questions connexes