Jak zrobić integer log2 () w C++?

Jeśli korzystasz z najnowszej platformy x86 lub x86-64 (i prawdopodobnie tak jest), użyj instrukcji bsr, która zwróci pozycję najwyższego ustawionego bitu w niepodpisanej liczbie całkowitej. Okazuje się, że jest to dokładnie to samo co log2 (). Oto krótka funkcja C lub C++, która wywołuje bsr używając wbudowanego 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;
}

Jeśli chcesz mieć szybki log liczbowy₂ działanie, następująca Funkcja mylog2() zrobi to bez konieczności martwienia się o dokładność zmiennoprzecinkową:

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

Powyższy kod ma również małą uprząż testową, dzięki której możesz sprawdzić zachowanie:

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

Zwróci UINT_MAX dla wartości wejściowej 0 jako wskazanie niezdefiniowanego wyniku, więc to jest coś, co należy sprawdzić (żadna ważna unsigned integer nie będzie miała logarytmu tak wysokiego).

Przy okazji, są pewne niezwykle szybkie hacki, aby to zrobić (znaleźć najwyższy bit w liczbie dopełniacza 2) dostępne z tutaj . Nie sugerowałbym ich używania, chyba że szybkość jest najważniejsza (sam wolę czytelność), ale powinieneś być świadomy, że istnieją.

Base-2 Integer Logarytm

Oto, co robię dla 64-bitowych niepodpisanych liczb całkowitych. To oblicza podłogę logarytmu Bazy - 2, który jest odpowiednikiem indeksu najbardziej znaczącego bitu. Metoda ta jest smokingly fast dla dużych liczb, ponieważ używa rozwiniętej pętli, która wykonuje się zawsze w log₂64 = 6 krokach.

Zasadniczo odejmuje stopniowo mniejsze kwadraty w sekwencji { 0 ≤ K ≤ 5: 2^(2^k) } = { 232, 21⁶, 2⁸, 2⁴, 22, 21 } = { 4294967296, 65536, 256, 16, 4, 2, 1 } i sumuje wykładniki k odejmowanych wartości.

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
}

Zauważ, że zwraca -1, jeśli podano nieprawidłowe dane wejściowe 0 (które jest sprawdzane przez początkowy -(n == 0)). Jeśli nigdy nie spodziewasz się wywołać go za pomocą n == 0, możesz zastąpić int i = 0; inicjalizatorem i dodać assert(n != 0); przy wejściu do funkcji.

Base-10 Integer Logarytm

Baza-10 logarytmów całkowitych może być obliczona analogicznie - przy czym największy kwadrat do badania jest 101⁶ bo 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
}

Zostało to zaproponowane w komentarzach powyżej. Używanie wbudowanych 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);
}

Nigdy nie miałem problemu z dokładnością zmiennoprzecinkową na formula_1 (i szybkim sprawdzaniem liczb od 1 do 2³¹ - 1 nie znaleziono błędów), ale jeśli się martwisz, możesz użyć tej funkcji, która zwraca te same wyniki i jest o 66% szybsza w moich testach: {]}

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));

To nie jest standardowe lub koniecznie przenośne, ale ogólnie będzie działać. Nie wiem, czy to skuteczne.

Przelicz indeks całkowity na liczbę zmiennoprzecinkową o wystarczającej precyzji. Reprezentacja będzie dokładna, zakładając, że dokładność jest wystarczająca.

Wyszukaj reprezentację liczb zmiennoprzecinkowych IEEE, wyodrębnij wykładnik i dokonaj niezbędnej korekty, aby znaleźć log Bazy 2.

Ta funkcja określa, ile bitów jest wymaganych do reprezentowania interwału liczbowego: [0..maxvalue].

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

Odejmując 1 od wyniku otrzymujemy floor(log2(x)), która jest dokładną reprezentacją log2(x), Gdy x jest potęgą 2.

xyy-1
00-1
110
221
321
432
532
632
732
843

Jeśli używasz C++11 możesz zrobić z tego funkcję constexpr:

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

Są podobne odpowiedzi powyżej. Ta odpowiedź

1. działa z numerami 64-bitowymi
2. pozwala wybrać rodzaj zaokrąglenia i
3. zawiera kod testu / próbki

Funkcje:

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

Kod Badania:

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

Jak głęboko projektujesz swoje drzewo? Możesz ustawić zakres głosu... + / - 0.00000001 do liczby, aby wymusić jej wartość całkowitą.

Nie jestem pewien, czy trafisz taką liczbę, jak 1.99999999, ponieważ twój log2 nie powinien tracić dokładności przy obliczaniu wartości 2^n (ponieważ rundy zmiennoprzecinkowe do najbliższej potęgi 2).

Tę funkcję napisałem Tutaj

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

To jest stary post, ale dzielę się algorytmem jednej linii:

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

Przepisywanie odpowiedź Todda Lehmana będzie bardziej ogólna:

#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 z-O3 rozwiń pętlę:

0000000100000f50    pushq   %rbp
0000000100000f51    movq    %rsp, %rbp
0000000100000f54    xorl    %eax, %eax
0000000100000f56    cmpl    $0xffff, %edi
0000000100000f5c    setg    %al
0000000100000f5f    shll    $0x4, %eax
0000000100000f62    movl    %eax, %ecx
0000000100000f64    sarl    %cl, %edi
0000000100000f66    xorl    %edx, %edx
0000000100000f68    cmpl    $0xff, %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    $0xf, %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    $0x3, %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    $0x1, %edi
0000000100000fa6    setg    %al
0000000100000fa9    orl %ecx, %eax
0000000100000fab    popq    %rbp

Gdy n jest stała, wynik jest obliczany w czasie kompilacji.