Come fare un intero log2 () in C ++?

Nelle librerie standard C ++ ho trovato solo un metodo di log a virgola mobile. Ora utilizzo log per trovare il livello di un indice in un albero binario ( floor(2log(index)) ).

Codice (C ++):

 int targetlevel = int(log(index)/log(2)); 

Temo che per alcuni degli elementi del bordo (gli elementi con valore 2 ^ n) il registro restituisca n-1.999999999999 anziché n.0. Questa paura è corretta? Come posso modificare la mia dichiarazione in modo che restituisca sempre una risposta corretta?

Puoi utilizzare questo metodo invece:

 int targetlevel = 0; while (index >>= 1) ++targetlevel; 

Nota: questo modificherà l’indice. Se ne hai bisogno invariato, crea un altro int temporaneo.

Il caso d’angolo è quando l’indice è 0. Probabilmente dovresti controllarlo separatamente e lanciare un’eccezione o restituire un errore se index == 0.

Se ci si trova su una piattaforma recente x86 o x86-64 (e probabilmente lo siete), usate l’istruzione bsr che restituirà la posizione del bit più alto in un numero intero senza segno. Si scopre che questo è esattamente lo stesso di log2 (). Ecco una breve funzione C o C ++ che richiama bsr usando l’ASM in linea:

 #include  static inline uint32_t log2(const uint32_t x) { uint32_t y; asm ( "\tbsr %1, %0\n" : "=r"(y) : "r" (x) ); return y; } 

Se si desidera solo un’operazione di registro log intero veloce, la seguente funzione mylog2() eseguirà senza doversi preoccupare dell’accuratezza a virgola mobile:

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

Il codice sopra ha anche una piccola bardatura di test in modo da poter controllare il comportamento:

 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 

Restituirà UINT_MAX per un valore di input pari a 0 come indicazione di un risultato indefinito, quindi è qualcosa che dovresti controllare (nessun numero intero senza segno valido avrà un logaritmo così alto).

A proposito, ci sono alcuni hack incredibilmente veloci per fare esattamente questo (trova il bit più alto impostato in un numero di complemento a 2) disponibile da qui . Non suggerirei di usarli a meno che la velocità non sia essenziale (preferisco leggere me stesso) ma dovresti essere reso consapevole che esistono.

Logaritmo intero base 2

Ecco cosa faccio per interi senza segno a 64 bit. Questo calcola il floor del logaritmo in base 2, che è equivalente all’indice del bit più significativo. Questo metodo è fumantemente veloce per grandi numeri perché utilizza un ciclo srotolato che viene eseguito sempre in log₂64 = 6 passaggi.

In sostanza, ciò che fa è sottrarre progressivamente quadrati più piccoli nella sequenza {0 ≤ k ≤ 5: 2 ^ (2 ^ k)} = {2 ³, 2¹ ⁶, 2⁸, 2⁴, 2 ², 2¹} = {4294967296, 65536, 256 , 16, 4, 2, 1} e sum gli esponenti k dei valori sottratti.

 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 } 

Notare che questo restituisce -1 se viene dato l’input non valido di 0 (che è ciò che l’iniziale -(n == 0) sta verificando). Se non ti aspetti mai di invocarlo con n == 0 , potresti sostituire int i = 0; per l’inizializzatore e aggiungi assert(n != 0); all’ingresso della funzione.

Logaritmo intero in base 10

I logaritmi interi Base 10 possono essere calcolati usando in modo simile – con il quadrato più grande da testare 10¹⁶ perché 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 } 

Questo è stato proposto nei commenti sopra. Usando i builtin 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); } 

Non ho mai avuto problemi con la precisione in virgola mobile della formula che stai utilizzando (e una rapida verifica dei numeri da 1 a 2 31 – 1 non ha rilevato errori), ma se sei preoccupato, puoi usare questa funzione invece, che restituisce gli stessi risultati ed è circa il 66% più veloce nei miei test:

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

Questo non è standard o necessariamente portatile, ma funzionerà in generale. Non so quanto sia efficiente.

Convertire l’indice intero in un numero in virgola mobile di precisione sufficiente. La rappresentazione sarà esatta, assumendo che la precisione sia sufficiente.

Cerca la rappresentazione dei numeri a virgola mobile IEEE, estrai l’esponente e apporta le modifiche necessarie per trovare il registro di base 2.

Questa funzione determina quanti bit sono necessari per rappresentare l’intervallo numerico: [0..maxvalue].

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

Sottraendo 1 dal risultato, si ottiene floor(log2(x)) , che è una rappresentazione esatta di log2(x) quando x è una potenza di 2.

x y 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

Se stai usando C ++ 11 puoi renderlo una funzione di constexpr:

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

Ci sono risposte simili sopra. Questa risposta

  1. Funziona con numeri a 64 bit
  2. Ti consente di scegliere il tipo di arrotondamento e
  3. Include codice di prova / campione

funzioni:

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

Codice di prova:

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

Quanto profondi proietti il ​​tuo albero? È ansible impostare un intervallo di dire … +/- 0,00000001 al numero per forzarlo su un valore intero.

In realtà non sono sicuro di aver raggiunto un numero come 1.99999999 perché il tuo log2 non dovrebbe perdere precisione nel calcolo dei valori 2 ^ n (dal round in virgola mobile alla potenza più vicina di 2).

Questa funzione ho scritto qui

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

Questo è un vecchio post ma condivido il mio algoritmo a una riga:

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

Riscrivere la risposta di Todd Lehman ad essere più generica:

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

Clang con -O3 srotola il ciclo:

 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 

Quando n è costante, il risultato viene calcolato in fase di compilazione.