Comment faire un entier log2() en C++?

si vous êtes sur une plate-forme récente-ish x86 ou x86-64 (et vous l'êtes probablement), utilisez l'instruction bsr qui renverra la position du bit de set le plus élevé dans un entier non signé. Il s'avère que c'est exactement le même que log2(). Voici une fonction C ou c++ courte qui invoque bsr en utilisant inline ASM:

#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;
}

si vous voulez juste un journal entier Rapide ₂ opération, la fonction suivante mylog2() le fera sans avoir à se soucier de la précision de la virgule flottante:

#include <limits.h>

static unsigned int mylog2 (unsigned int val) {
    if (val == 0) return UINT_MAX;
    if (val == 1) return 0;
    unsigned int ret = 0;
    while (val > 1) {
        val >>= 1;
        ret++;
    }
    return ret;
}

#include <stdio.h>

int main (void) {
    for (unsigned int i = 0; i < 20; i++)
        printf ("%u -> %u\n", i, mylog2(i));
    putchar ('\n');
    for (unsigned int i = 0; i < 10; i++)
        printf ("%u -> %u\n", i+UINT_MAX-9, mylog2(i+UINT_MAX-9));
    return 0;
}

le code ci-dessus a également un petit harnais d'essai afin que vous puissiez vérifier le comportement:

0 -> 4294967295
1 -> 0
2 -> 1
3 -> 1
4 -> 2
5 -> 2
6 -> 2
7 -> 2
8 -> 3
9 -> 3
10 -> 3
11 -> 3
12 -> 3
13 -> 3
14 -> 3
15 -> 3
16 -> 4
17 -> 4
18 -> 4
19 -> 4

4294967286 -> 31
4294967287 -> 31
4294967288 -> 31
4294967289 -> 31
4294967290 -> 31
4294967291 -> 31
4294967292 -> 31
4294967293 -> 31
4294967294 -> 31
4294967295 -> 31

il retournera UINT_MAX pour une valeur d'entrée de 0 comme indication d'un résultat non défini, de sorte que c'est quelque chose que vous devriez vérifier pour (pas valide entier non signé sera un logarithme que haute).

d'ailleurs, il y a des hacks incroyablement rapides pour faire exactement cela (trouver le bit le plus haut placé dans le numéro de complément d'un 2) disponible à partir de ici . Je ne suggérerais pas de les utiliser à moins que la vitesse soit essentielle (je préfère la lisibilité moi-même) mais vous devriez être mis au courant qu'ils existent.

Base-2 Entier Logarithme

voici ce que je fais pour les entiers 64 bits non signés. Ceci calcule le plancher du logarithme de base-2, qui est équivalent à l'indice du bit le plus significatif. Cette méthode est smokingly fast pour les grands nombres parce qu'il utilise une boucle non-déroulante qui exécute toujours dans le log փ 64 = 6 étapes.

essentiellement, ce qu'il fait est de soustraire progressivement les carrés plus petits dans la séquence { 0 ≤ k ≤ 5: 2^(2^k)} = {232, 21, 22, 21 } = { 4294967296, 65536, 256, 16, 4, 2, 1 } et additionne les exposants k des valeurs soustraites.

int uint64_log2(uint64_t n)
{
  #define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; }

  int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i;

  #undef S
}

notez que cela retourne -1 si on lui donne l'entrée invalide de 0 (ce qui est ce que le -(n == 0) initial vérifie). Si vous ne vous attendez jamais à l'invoquer avec n == 0 , vous pouvez substituer int i = 0; à l'initialiseur et ajouter assert(n != 0); à l'entrée de la fonction.

Base-10 Entier Logarithme

en Base 10 entier logarithmes peuvent être calculés en utilisant le même avec la plus grande place de test en cours de 101⁶ parce que log₁₀2⁶⁴ ≅ 19.2659...

int uint64_log10(uint64_t n)
{
  #define S(k, m) if (n >= UINT64_C(m)) { i += k; n /= UINT64_C(m); }

  int i = -(n == 0);
  S(16,10000000000000000); S(8,100000000); S(4,10000); S(2,100); S(1,10);
  return i;

  #undef S
}

cela a été proposé dans les observations ci-dessus. Utilisation des builtins gcc:

static inline int log2i(int x) {
    assert(x > 0);

    return sizeof(int) * 8 - __builtin_clz(x) - 1;
}

static void test_log2i(void) {
    assert_se(log2i(1) == 0);
    assert_se(log2i(2) == 1);
    assert_se(log2i(3) == 1);
    assert_se(log2i(4) == 2);
    assert_se(log2i(32) == 5);
    assert_se(log2i(33) == 5);
    assert_se(log2i(63) == 5);
    assert_se(log2i(INT_MAX) == sizeof(int)*8-2);
}

Je n'ai jamais eu de problème avec la précision flottante sur la formule que vous utilisez (et une vérification rapide des nombres de 1 à 2 ³¹ - 1 trouvé aucune erreur), mais si vous êtes inquiet, vous pouvez utiliser cette fonction à la place, qui renvoie les mêmes résultats et est d'environ 66% plus rapide dans mes tests:

int HighestBit(int i){
    if(i == 0)
        return -1;

    int bit = 31;
    if((i & 0xFFFFFF00) == 0){
        i <<= 24;
        bit = 7;
    }else if((i & 0xFFFF0000) == 0){
        i <<= 16;
        bit = 15;
    }else if((i & 0xFF000000) == 0){
        i <<= 8;
        bit = 23;
    }

    if((i & 0xF0000000) == 0){
        i <<= 4;
        bit -= 4;
    }

    while((i & 0x80000000) == 0){
        i <<= 1;
        bit--;
    }

    return bit; 
}

int targetIndex = floor(log(i + 0.5)/log(2.0));

ce n'est pas standard ou nécessairement portable, mais il fonctionne en général. Je ne sais pas comment elle est efficace.

Convertissez l'indice entier en un nombre flottant de précision suffisante. La représentation sera exacte, si la précision est suffisante.

chercher la représentation des nombres IEEE à virgule flottante, extraire l'exposant, et faire le réglage nécessaire pour trouver le log de base 2.

cette fonction détermine le nombre de bits nécessaires pour représenter l'intervalle numérique: [0..maxvalue].

unsigned binary_depth( unsigned maxvalue )
   {
   int depth=0;
   while ( maxvalue ) maxvalue>>=1, depth++;
   return depth;
   }

en soustrayant 1 du résultat, vous obtenez floor(log2(x)) , qui est une exacte représentation de log2(x) quand x est une puissance de 2.

x o y-1

0 0 -1

1 1 0

2 2 1

3 2 1

4 3 2

5 3 2

6 3 2

7 3 2

8 4 3

si vous utilisez C++11, Vous pouvez en faire une fonction constexpr:

constexpr std::uint32_t log2(std::uint32_t n)
{
    return (n > 1) ? 1 + log2(n >> 1) : 0;
}

il y a des réponses similaires ci-dessus. Cette réponse

1. Fonctionne avec la version 64 bits des nombres
2. vous permet de choisir le type d'arrondissement et
3. comprend le code d'essai/d'échantillon

fonctions:

    static int floorLog2(int64_t x)
    { 
      assert(x > 0);
      return 63 - __builtin_clzl(x);
    }

    static int ceilLog2(int64_t x)
    {
      if (x == 1)
        // On my system __builtin_clzl(0) returns 63.  64 would make more sense   
        // and would be more consistent.  According to stackoverflow this result  
        // can get even stranger and you should just avoid __builtin_clzl(0).     
        return 0;
      else
        return floorLog2(x-1) + 1;
    }

Code D'Essai:

for (int i = 1; i < 35; i++)
  std::cout<<"floorLog2("<<i<<") = "<<floorLog2(i)
           <<", ceilLog2("<<i<<") = "<<ceilLog2(i)<<std::endl;

à quelle profondeur projetez-vous votre arbre? Vous pouvez définir une plage de dire... +/- 0.00000001 le nombre de forcer une valeur entière.

en fait, je ne suis pas certain que vous atteindrez un nombre comme 1.99999999 parce que votre log2 ne devrait pas perdre de précision lors du calcul des valeurs 2^n (Puisque les ronds à virgule flottante à la puissance la plus proche de 2).

cette fonction j'ai écrit ici

// The 'i' is for int, there is a log2 for double in stdclib
inline unsigned int log2i( unsigned int x )
{
  unsigned int log2Val = 0 ;
  // Count push off bits to right until 0
  // 101 => 10 => 1 => 0
  // which means hibit was 3rd bit, its value is 2^3
  while( x>>=1 ) log2Val++;  // div by 2 until find log2.  log_2(63)=5.97, so
  // take that as 5, (this is a traditional integer function!)
  // eg x=63 (111111), log2Val=5 (last one isn't counted by the while loop)
  return log2Val ;
}

C'est un vieux post, mais je partage mon un ligne de l'algorithme:

unsigned uintlog2(unsigned x)
{
   unsigned l;
   for(l=0; x>1; x>>=1, l++);
   return l;
} 

Réécriture Todd Lehman 's réponse pour être plus générique:

#include <climits>

template<typename N>
constexpr N ilog2(N n) {
    N i = 0;
    for (N k = sizeof(N) * CHAR_BIT; 0 < (k /= 2);) {
        if (n >= static_cast<N>(1) << k) { i += k; n >>= k; }
    }
    return i;
}

Clang avec -O3 se déroule à la boucle:

0000000100000f50    pushq   %rbp
0000000100000f51    movq    %rsp, %rbp
0000000100000f54    xorl    %eax, %eax
0000000100000f56    cmpl    "151910920"xffff, %edi
0000000100000f5c    setg    %al
0000000100000f5f    shll    "151910920"x4, %eax
0000000100000f62    movl    %eax, %ecx
0000000100000f64    sarl    %cl, %edi
0000000100000f66    xorl    %edx, %edx
0000000100000f68    cmpl    "151910920"xff, %edi
0000000100000f6e    setg    %dl
0000000100000f71    leal    (,%rdx,8), %ecx
0000000100000f78    sarl    %cl, %edi
0000000100000f7a    leal    (%rax,%rdx,8), %eax
0000000100000f7d    xorl    %edx, %edx
0000000100000f7f    cmpl    "151910920"xf, %edi
0000000100000f82    setg    %dl
0000000100000f85    leal    (,%rdx,4), %ecx
0000000100000f8c    sarl    %cl, %edi
0000000100000f8e    leal    (%rax,%rdx,4), %eax
0000000100000f91    xorl    %edx, %edx
0000000100000f93    cmpl    "151910920"x3, %edi
0000000100000f96    setg    %dl
0000000100000f99    leal    (%rdx,%rdx), %ecx
0000000100000f9c    sarl    %cl, %edi
0000000100000f9e    leal    (%rax,%rdx,2), %ecx
0000000100000fa1    xorl    %eax, %eax
0000000100000fa3    cmpl    "151910920"x1, %edi
0000000100000fa6    setg    %al
0000000100000fa9    orl %ecx, %eax
0000000100000fab    popq    %rbp

lorsque n est constant, le résultat est calculé en temps de compilation.