Elaborazione rapida di log2 per interi a 64 bit

Una grande risorsa di programmazione, Bit Twiddling Hacks, propone ( qui ) il seguente metodo per calcolare log2 di un intero a 32 bit:

#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n static const char LogTable256[256] = { -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7) }; unsigned int v; // 32-bit word to find the log of unsigned r; // r will be lg(v) register unsigned int t, tt; // temporaries if (tt = v >> 16) { r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt]; } else { r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v]; } 

e lo dice

Il metodo della tabella di ricerca richiede solo circa 7 operazioni per trovare il registro di un valore a 32 bit. Se esteso per quantità a 64 bit, sarebbero necessarie circa 9 operazioni.

ma, ahimè, non fornisce alcuna informazione aggiuntiva su quale modo si dovrebbe effettivamente andare ad estendere l’algoritmo a interi a 64 bit.

Qualche suggerimento su come sarebbe un algoritmo di questo tipo a 64 bit?

Le funzioni intrinseche sono molto veloci ma non sono ancora sufficienti per un’implementazione di Log2 indipendente da compilatore e multipiattaforma. Quindi, nel caso in cui qualcuno fosse interessato, ecco l’algoritmo DeBruijn simile alla CPU, più veloce, privo di diramazioni e ramificato, al quale sono giunto mentre cercavo l’argomento da solo.

 const int tab64[64] = { 63, 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56, 45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5}; int log2_64 (uint64_t value) { value |= value >> 1; value |= value >> 2; value |= value >> 4; value |= value >> 8; value |= value >> 16; value |= value >> 32; return tab64[((uint64_t)((value - (value >> 1))*0x07EDD5E59A4E28C2)) >> 58]; } 

La parte di arrotondamento alla potenza inferiore successiva di 2 è stata presa da Power-of-2 Boundaries e la parte di ottenere il numero di zeri finali è stata presa da BitScan (il codice (bb & -bb) che è necessario per individuare il il bit più a destra che è impostato su 1, che non è necessario dopo aver arrotondato il valore alla potenza successiva di 2).

E l’implementazione a 32 bit, a proposito, lo è

 const int tab32[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31}; int log2_32 (uint32_t value) { value |= value >> 1; value |= value >> 2; value |= value >> 4; value |= value >> 8; value |= value >> 16; return tab32[(uint32_t)(value*0x07C4ACDD) >> 27]; } 

Come con qualsiasi altro metodo di calcolo, log2 richiede che il valore di input sia maggiore di zero.

Se si utilizza GCC, una tabella di ricerca non è necessaria in questo caso.

GCC fornisce una funzione incorporata per determinare la quantità di zeri iniziali:

Funzione built-in: int __builtin_clz (unsigned int x)
Restituisce il numero di 0 bit iniziali in x, iniziando dalla posizione di bit più significativa. Se x è 0, il risultato non è definito.

Quindi puoi definire:

 #define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1)) 

e funzionerà per qualsiasi int long lungo non firmato. Il risultato è arrotondato per difetto.

Per x86 e AMD64 GCC lo compila in un’istruzione bsr , quindi la soluzione è molto veloce (molto più veloce delle tabelle di ricerca).

Esempio di lavoro :

 #include  #define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1)) int main(void) { unsigned long long input; while (scanf("%llu", &input) == 1) { printf("log(%llu) = %u\n", input, LOG2(input)); } return 0; } 

Stavo cercando di convertire Trova la base di log 2 di un intero N-bit in operazioni O (lg (N)) con moltiplica e cerca a 64-bit di forzare il numero magico. Inutile dire che ci volle un po ‘.

Ho quindi trovato la risposta di Desmond e ho deciso di provare il suo numero magico come punto di partenza. Dal momento che ho un processore 6 core l’ho eseguito in parallelo a partire da 0x07EDD5E59A4E28C2 / 6 multipli. Sono stato sorpreso di aver trovato qualcosa immediatamente. Risulta funzionante 0x07EDD5E59A4E28C2 / 2.

Quindi, ecco il codice per 0x07EDD5E59A4E28C2 che ti risparmia uno spostamento e sottrarre:

 int LogBase2(uint64_t n) { static const int table[64] = { 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56, 45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5, 63 }; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; n |= n >> 32; return table[(n * 0x03f6eaf2cd271461) >> 58]; } 

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 … (Nota: questo non è il modo più veloce per eseguire un logaritmo intero di base 10, perché usa la divisione integer, che è intrinsecamente lento: un’implementazione più rapida sarebbe quella di utilizzare un accumulatore con valori che crescono esponenzialmente e confrontarsi con l’accumulatore, in effetti facendo una sorta di ricerca binaria).

 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 } 

Ecco un’estensione piuttosto compatta e veloce, senza l’uso di altri temporaries:

 r = 0; /* If its wider than 32 bits, then we already know that log >= 32. So store it in R. */ if (v >> 32) { r = 32; v >>= 32; } /* Now do the exact same thing as the 32 bit algorithm, except we ADD to R this time. */ if (tt = v >> 16) { r += (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt]; } else { r += (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v]; } 

Qui if n’è uno costruito con una catena di if s, ancora senza usare temporary aggiuntivi. Potrebbe non essere il più veloce però.

  if (tt = v >> 48) { r = (t = tt >> 8) ? 56 + LogTable256[t] : 48 + LogTable256[tt]; } else if (tt = v >> 32) { r = (t = tt >> 8) ? 40 + LogTable256[t] : 32 + LogTable256[tt]; } else if (tt = v >> 16) { r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt]; } else { r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v]; } 

L’algoritmo rileva fondamentalmente quale byte contiene il bit più significativo, quindi cerca quel byte nella ricerca per trovare il log del byte, quindi lo aggiunge alla posizione del byte.

Ecco una versione un po ‘semplificata dell’algoritmo a 32 bit:

 if (tt = v >> 16) { if (t = tt >> 8) { r = 24 + LogTable256[t]; } else { r = 16 + LogTable256[tt]; } } else { if (t = v >> 8) { r = 8 + LogTable256[t]; } else { r = LogTable256[v]; } } 

Questo è l’algoritmo a 64 bit equivalente:

 if (ttt = v >> 32) { if (tt = ttt >> 16) { if (t = tt >> 8) { r = 56 + LogTable256[t]; } else { r = 48 + LogTable256[tt]; } } else { if (t = ttt >> 8) { r = 40 + LogTable256[t]; } else { r = 32 + LogTable256[ttt]; } } } else { if (tt = v >> 16) { if (t = tt >> 8) { r = 24 + LogTable256[t]; } else { r = 16 + LogTable256[tt]; } } else { if (t = v >> 8) { r = 8 + LogTable256[t]; } else { r = LogTable256[v]; } } } 

Ho trovato un algoritmo per tutti i tipi di dimensioni che ritengo sia più bello dell’originale.

 unsigned int v = 42; unsigned int r = 0; unsigned int b; for (b = sizeof(v) < < 2; b; b = b >> 1) { if (v >> b) { v = v >> b; r += b; } } 

Nota: b = sizeof(v) < < 2 imposta b a metà del numero di bit in v. Ho usato lo spostamento invece della moltiplicazione qui (solo perché mi sembrava).

È ansible aggiungere una tabella di ricerca all'algoritmo per velocizzarlo, ma è più una prova di concetto.