Bit twiddling en C: comment convertir 2^N en N?

Question

Quelle est une bonne routine de bit-twiddling pour convertir un nombre dans la gamme [2^N, 2^(N-1) -1] en N?

Quelques exemples:

• f (1) -> 0
• f ([2-3]) -> 1
• f ([4-7]) -> 2
• f ([8-15]) -> 3

Voici une mise en œuvre:

uint f(uint num) 
{ 
    for (uint shifts = 0; num; shifts++) 
     num >>= 1; 
    return (shifts - 1); 
} 

Answer 1

Selon la largeur de votre type de données et la quantité de mémoire disponible, une table de consultation est une possibilité. C'est presque certainement l'approche la plus rapide. Pour d'autres approches, voir http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious et les sections suivantes.

Answer 2

Jetez un oeil à hacks pour la base 2 logarithme calcul (ou premier compte zéro, ils sont les mêmes) sur cette page: http://www-graphics.stanford.edu/~seander/bithacks.html

Vous pouvez aussi trouver utile la fonction __builtin_clz (ou _BitScanReverse pour VS) pour x86 .

Answer 3

Comme approche la plus générale, la recherche binaire peut aider. Pour les valeurs 0..31, il suffit de 5 étapes.

y = 0; 
if(x >= 0x10000<<y) y += 0x10; 
if(x >= 0x100<<y) y += 0x08; 
if(x >= 0x10<<y) y += 0x04; 
if(x >= 0x4<<y) y += 0x02; 
if(x >= 0x2<<y) y += 0x01;