Come ottenere lg2 di un numero 2^k

Question

Qual è la soluzione migliore per ottenere il logaritmo di base 2 di un numero che conosco è una potenza di due (2^k). (. Naturalmente so solo il non valore 2^kk stesso)

Un modo ho pensato di fare è sottraendo 1 e poi facendo un bitcount:

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

Ma c'è un modo più veloce per farlo (senza cache)? Inoltre, qualcosa che non coinvolge più velocemente il bitcount sarebbe bello saperlo?

Una delle applicazioni questo è:

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 

Per essere più veloce di bitcount senza caching che dovrebbe essere più veloce di O(lg(k)) dove k è il conteggio dei bit di archiviazione.

Answer 1

Molte architetture hanno un'istruzione "trova prima una" (bsr, clz, bfffo, cntlzw, ecc.) Che sarà molto più veloce degli approcci di conteggio bit.

Answer 2

Se si conosce che il numero è una potenza di 2, è possibile spostarlo a destra (>>) finché non è uguale a 0. Il numero di volte che si è spostato a destra (meno 1) è il k.

Modifica: più veloce di questo è il metodo della tabella di ricerca (sebbene si sacrifichi un po 'di spazio, ma non una tonnellata). Vedi http://doctorinterview.com/index.html/algorithmscoding/find-the-integer-log-base-2-of-an-integer/.

Answer 3

Se non ti dispiace trattare con i float puoi usare log(x)/log(2).

Answer 4

Sì. Ecco un modo per farlo senza il bitcount in lg(n), se si conosce il numero intero in questione è una potenza di 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). 

In ciascuna delle reg |= passi, successivamente test per vedere se uno qualsiasi dei bit di x sono condivisi con maschere di bit alternate in arr. Se lo sono, ciò significa che lg(x) ha bit che si trovano in quella maschera di bit e aggiungiamo efficacemente 2^k a reg, dove k è il registro della lunghezza della maschera di bit alternata. Ad esempio, 0xFF00FF00 è una sequenza alternata di 8 e zero, quindi k è 3 (o lg(8)) per questa maschera di bit.

In sostanza, ogni passaggio reg |= ((x & arr[k]) ... (e l'assegnazione iniziale) verifica se lg(x) ha impostato il bit k. Se è così, lo aggiungiamo a reg; la somma di tutti quei bit sarà lg(x).

Questo sembra un sacco di magia, quindi proviamo con un esempio. Supponiamo di voler sapere quale potenza di 2 il valore di 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). 

Vediamo che il valore finale di reg è 2^0 + 2^1 + 2^3, che è davvero 11.