Comment obtenir lg2 d'un nombre qui est 2^k

Question

Quelle est la meilleure solution pour obtenir le logarithme de base 2 d'un nombre que je sais est une puissance de deux (2^k). (. Bien sûr, je sais que la valeur 2^k pas k lui-même)

Une façon dont je pensais de faire est en soustrayant 1, puis faire un Bitcount:

lg2(n) = bitcount(n - 1) = k, iff k is an integer 
0b10000 - 1 = 0b01111, bitcount(0b01111) = 4 

Mais est-il un moyen plus rapide de le faire (sans mise en cache)? Aussi quelque chose qui n'implique pas le bitcount à peu près aussi vite serait bon à savoir?

Une des applications est ce:

suppose you have bitmask 
0b0110111000 

and value 
0b0101010101 

and you are interested of 
(value & bitmask) >> number of zeros in front of bitmask 
(0b0101010101 & 0b0110111000) >> 3 = 0b100010 

this can be done with 

using bitcount 
value & bitmask >> bitcount((bitmask - 1) xor bitmask) - 1 

or using lg2 
value & bitmask >> lg2(((bitmask - 1) xor bitmask) + 1) - 2 

Pour qu'il soit plus rapide que bitcount sans mise en cache, il devrait être plus rapide que O(lg(k)) où k est le nombre de bits de stockage.

Answer 1

De nombreuses architectures ont une instruction «trouver le premier» (bsr, clz, bfffo, cntlzw, etc.) qui sera beaucoup plus rapide que les approches de comptage de bits.

Answer 2

Si vous connaissez le nombre est une puissance de 2, vous pouvez simplement le déplacer vers la droite (>>) jusqu'à ce qu'il soit égal à 0. Le nombre de fois que vous décalé à droite (moins 1) est votre k.

Édition: plus rapide que ceci est la méthode de table de recherche (bien que vous perdiez de l'espace, mais pas une tonne). Voir http://doctorinterview.com/index.html/algorithmscoding/find-the-integer-log-base-2-of-an-integer/.

Answer 3

Si cela ne vous dérange pas de gérer les flotteurs, vous pouvez utiliser log(x)/log(2).

Answer 4

Oui. Voici une façon de le faire sans Bitcount dans lg(n), si vous connaissez le nombre entier en question est une puissance de 2.

unsigned int x = ...; 
static const unsigned int arr[] = { 
    // Each element in this array alternates a number of 1s equal to 
    // consecutive powers of two with an equal number of 0s. 
    0xAAAAAAAA, // 0b10101010..   // one 1, then one 0, ... 
    0xCCCCCCCC, // 0b11001100..   // two 1s, then two 0s, ... 
    0xF0F0F0F0, // 0b11110000..   // four 1s, then four 0s, ... 
    0xFF00FF00, // 0b1111111100000000.. // [The sequence continues.] 
    0xFFFF0000 
} 

register unsigned int reg = (x & arr[0]) != 0; 
reg |= ((x & arr[4]) != 0) << 4; 
reg |= ((x & arr[3]) != 0) << 3; 
reg |= ((x & arr[2]) != 0) << 2; 
reg |= ((x & arr[1]) != 0) << 1; 

// reg now has the value of lg(x). 

Dans chacune des reg |= étapes, nous testons successivement pour voir si des bits de x sont partagés avec les bitmasques en alternance dans arr. Si elles le sont, cela signifie que lg(x) a des bits qui sont dans ce masque de bits, et nous ajoutons effectivement 2^k à reg, où k est le journal de la longueur du masque de bits alternatif. Par exemple, 0xFF00FF00 est une séquence alternée de 8 uns et de zéros, donc k est 3 (ou lg(8)) pour ce masque de bits.

Essentiellement, chaque étape reg |= ((x & arr[k]) ... (et l'affectation initiale) teste si lg(x) a le bit k. Si oui, nous l'ajoutons à reg; la somme de tous ces bits sera lg(x). Cela ressemble à beaucoup de magie, alors essayons un exemple. Supposons que nous voulons savoir quelle puissance de 2 la valeur est 2.048:

// x = 2048 
// = 1000 0000 0000 

register unsigned int reg = (x & arr[0]) != 0; 
// reg =  1000 0000 0000 
     & ... 1010 1010 1010 
     =  1000 0000 0000 != 0 
// reg = 0x1 (1)  // <-- Matched! Add 2^0 to reg. 

reg |= ((x & arr[4]) != 0) << 4; 
// reg =  0x .. 0800 
      & 0x .. 0000 
     =    0 != 0 
// reg = reg | (0 << 4) // <--- No match. 
// reg = 0x1 | 0 
// reg remains 0x1. 

reg |= ((x & arr[3]) != 0) << 3; 
// reg =  0x .. 0800 
      & 0x .. FF00 
     =   800 != 0 
// reg = reg | (1 << 3) // <--- Matched! Add 2^3 to reg. 
// reg = 0x1 | 0x8 
// reg is now 0x9.   

reg |= ((x & arr[2]) != 0) << 2; 
// reg =  0x .. 0800 
      & 0x .. F0F0 
     =    0 != 0 
// reg = reg | (0 << 2) // <--- No match. 
// reg = 0x9 | 0 
// reg remains 0x9.   

reg |= ((x & arr[1]) != 0) << 1; 
// reg =  0x .. 0800 
      & 0x .. CCCC 
     =   800 != 0 
// reg = reg | (1 << 1) // <--- Matched! Add 2^1 to reg. 
// reg = 0x9 | 0x2 
// reg is now 0xb (11). 

On voit que la valeur finale de reg est 2^0 + 2^1 + 2^3, qui est en effet 11.