Fonction récursive au moment de la compilation pour calculer la puissance suivante de deux d’un entier?

Sur le site Web de Bit Twiddling Hacks, l’algorithme suivant est fourni pour arrondir un entier à la puissance suivante:

unsigned int v; // compute the next highest power of 2 of 32-bit v v--; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; v++; 

Je voudrais coder une fonction de métaprogrammation qui calculera la même opération:

  • récursivement (pour une exécution à la compilation)
  • pour tout type d’entier (cela devrait même fonctionner pour des entiers peu standards gênants de n’importe quelle taille comme 15 bits, 65 bits …)

et voici la forme de la fonction attendue:

 template <typename Type, // Something here (like a recursion index) class = typename std::enable_if<std::is_integral::value>::type, class = typename std::enable_if<std::is_unsigned::value>::type> constexpr Type function(const Type value) { // Something here } 

Comment faire ça ?

Exemple: pour value = 42 il devrait retourner 64

Cela devrait implémenter l’algorithme que vous donnez:

 template constexpr T roundup_helper( T value, unsigned maxb, unsigned curb ) { return maxb<=curb ? value : roundup_helper( ((value-1) | ((value-1)>>curb))+1, maxb, curb << 1 ) ; } template::value>::type, typename = typename enable_if::value>::type> constexpr T roundup( T value ) { return roundup_helper( value, sizeof(T)*CHAR_BIT, 1 ); } 

Au moins, cela semble bien fonctionner dans mon programme de test.

Alternativement, vous pouvez déplacer les v-1 et v+1 hors de la fonction d’assistance comme ceci:

 template constexpr T roundup_helper( T value, unsigned maxb, unsigned curb ) { return maxb<=curb ? value : roundup_helper( value | (value>>curb), maxb, curb << 1 ) ; } template::value>::type, typename = typename enable_if::value>::type> constexpr T roundup( T value ) { return roundup_helper( value-1, sizeof(T)*CHAR_BIT, 1 )+1; } 

Une autre possibilité est de tirer parti des arguments par défaut et de tout mettre dans une seule fonction:

 template::value>::type, typename = typename enable_if::value>::type> constexpr T roundup( T value, unsigned maxb = sizeof(T)*CHAR_BIT, unsigned curb = 1 ) { return maxb<=curb ? value : roundup( ((value-1) | ((value-1)>>curb))+1, maxb, curb << 1 ) ; } 

Ce n’est peut-être pas ce que vous pouvez faire malheureusement. Mais si par hasard vous avez un nombre de constexpr menant insortingnsèquement au compilateur constexpr , ce qui suit est très efficace à la fois au moment de la compilation et au moment de l’exécution, si vous lui donnez des arguments à l’exécution:

 #include  template  inline constexpr Int clp2(Int v) { return v > 1 ? 1 << (sizeof(Int)*CHAR_BIT - __builtin_clz(v-1)) : v; } int main() { static_assert(clp2(0) == 0, ""); static_assert(clp2(1) == 1, ""); static_assert(clp2(2) == 2, ""); static_assert(clp2(3) == 4, ""); static_assert(clp2(4) == 4, ""); static_assert(clp2(5) == 8, ""); static_assert(clp2(6) == 8, ""); static_assert(clp2(7) == 8, ""); static_assert(clp2(8) == 8, ""); static_assert(clp2(42) == 64, ""); } 

J'ai compilé ce qui précède avec une résonance de bout du tronc. Ce n'est pas sans ses problèmes. Vous devez décider ce que vous voulez faire avec des arguments négatifs. Mais beaucoup d'architectures et de compilateurs ont un élément insortingnsèque comme celui-ci (dommage que ce ne soit pas la norme C / C ++ à l'heure actuelle). Et certains d'entre eux peuvent faire le constexpr insortingnsèque.

Sans un tel élément insortingnsèque, je reviendrais à quelque chose du type de l'algorithme d'Adam H. Peterson. Mais la bonne chose à propos de celui-ci est sa simplicité et son efficacité.