Comment calculer le logarithme en base 2 en utilisant des opérateurs bit à bit?

Question

Je dois calculer le logarithme en base 2 d'un nombre en C mais je ne peux pas utiliser la bibliothèque mathématique. La réponse n'a pas besoin d'être exacte, juste au nombre entier le plus proche. J'ai réfléchi et je sais que je pourrais simplement utiliser une boucle while et diviser le nombre par 2 jusqu'à ce qu'il soit < 2, et garder le compte des itérations, mais est-ce possible en utilisant des opérateurs de bits ?

Answer 1

Déjà répondu par abamert mais juste pour être plus concret voici comment vous le coderiez :

Log2(x) = résultat
while (x >>= 1) résultat++;

Answer 2

Si vous comptez le décalage comme un opérateur bit à bit, c'est facile.

Vous savez déjà comment le faire en effectuant des divisions successives par 2.

x >> 1 est équivalent à x / 2 pour tout entier non signé en C.

Si vous avez besoin d'aller plus vite, vous pouvez faire une "diviser pour régner" - décaler, par exemple, de 4 bits à la fois jusqu'à ce que vous atteigniez 0, puis revenir en arrière et regarder les 4 derniers bits. Cela signifie au maximum 16 décalages et 19 comparaisons au lieu de 63 de chaque. Que ce soit effectivement plus rapide sur un processeur moderne, je ne pourrais le dire sans tester. Et vous pouvez aller encore plus loin en effectuant d'abord des groupes de 16, puis 4, puis 1. Probablement pas utile ici, mais si vous aviez des entiers de 1024 bits, cela pourrait être intéressant à prendre en considération.

Answer 3

__builtin_clz(x) : Cette fonction est utilisée pour compter les zéros de tête de l'entier. Remarque : clz = compter les zéros de tête (En C/C++). En considérant un entier de 32 bits,

log_2_x = 32 - __builtin_clz(x) - 1;

Answer 4

Si vous pouvez compiler avec un compilateur C++ à jour à la place, vous pouvez utiliser

  #include 
  int log2(auto i) { return 8*sizeof(i) - std::countl_zero(i) - 1; }

de manière portable.

Avec g++ ou clang, cela se ferait en utilisant "-std=c++20", ou ultérieur. Cela utilisera l'instruction "bsr" sur x86, beaucoup plus rapide qu'une boucle.