Comment calculer avec précision Log2 pour les valeurs entières en C ?

Méthode correcte de calculer Log2 en C pour les valeurs entières

Dans les bibliothèques standard C, il n'y a que la méthode de journalisation pour la virgule flottante. Cependant, la méthode log est souvent utilisée pour trouver le niveau d'un index dans un arbre binaire à l'aide de la formule floor(2log(index)).

Une approche courante consiste à utiliser int targetlevel = int(log(index)/log(2)). Mais cette approche peut conduire à des erreurs d'arrondi pour les éléments de bord (éléments de valeur 2^n), ce qui entraîne le renvoi de n-1,999999999999 au lieu du n.0 attendu.

Solution pour un calcul Log2 précis

Solution pour un calcul Log2 précis

Pour résoudre ce problème et garantir un calcul log2 précis pour les valeurs entières, une meilleure approche consiste à utiliser le Instruction bsr (analyse de bits inversée). bsr est disponible sur les plates-formes x86 et x86-64 et renvoie la position du bit le plus élevé dans un entier non signé. Ceci équivaut à log2() pour les entiers positifs.

#include <stdint.h>

static inline uint32_t log2(const uint32_t x) {
  uint32_t y;
  asm ( "\tbsr %1, %0\n"
      : "=r"(y)
      : "r" (x)
  );
  return y;
}

Voici un extrait de code C optimisé qui exploite l'instruction bsr :

Ce code utilise l'ASM en ligne pour appeler efficacement l'instruction bsr et fournit des calculs log2 précis pour les entiers.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!