Veloce potenza più vicina a 2 in JavaScript?

Question

C'è qualche veloce alternativa al seguente espressione:

Math.pow(2,Math.floor(Math.log(x)/Math.log(2))) 

Cioè, prendendo il più vicino (più piccola) potenza intera di 2 di un doppio? Ho una tale espressione in un anello interno. Sospetto che potrebbe essere molto più veloce, considerando che si potrebbe semplicemente prendere la mantissa dalla rappresentazione IEEE 754 del doppio.

Answer 1

Facendo uso di ES6 di Math.clz32(n) a contare gli zeri di un intero a 32 bit:

// Compute nearest lower power of 2 for n in [1, 2**31-1]: 
 
function nearestPowerOf2(n) { 
 
    return 1 << 31 - Math.clz32(n); 
 
} 
 

 
// Examples: 
 
console.log(nearestPowerOf2(9)); // 8 
 
console.log(nearestPowerOf2(33)); // 32

Answer 2

Sfortunatamente, è necessario un equivalente della funzione C frexp. Il meglio che ho trovato è JSFiddle e il suo codice utilizza Math.pow.

Ci sono un paio di alternative si potrebbe punto di riferimento, utilizzando dati reali, insieme con il tentativo in corso:

1. A partire da 1.0, moltiplicare più volte da 2,0 fino a quando è maggiore o uguale all'ingresso, poi moltiplicare per 0,5 finché non è inferiore o uguale all'input. Avresti bisogno di una gestione speciale per i valori alle estremità del doppio intervallo.
2. Memorizza un array di valori crescente di tutti i poteri esatti di due nel doppio intervallo e effettua una ricerca binaria.

Il primo è probabilmente il più veloce se i dati sono in genere vicini a 1.0. Il secondo richiede fino a 11 rami condizionali.

Answer 3

Ecco un'altra alternativa, con parametri di riferimento. Mentre entrambi sembrano essere comparabili, mi piace essere in grado di floor o ceil.

function pow2floor(v){ 
 
    v++; 
 
    var p = 1; 
 
    while (v >>= 1) {p <<= 1;} 
 
    return p; 
 
} 
 
function pow2ceil(v){ 
 
    v--; 
 
    var p = 2; 
 
    while (v >>= 1) {p <<= 1;} 
 
    return p; 
 
} 
 

 
function MATHpow2(v){ 
 
    return Math.pow(2,Math.floor(Math.log(v)/Math.log(2))) 
 
} 
 

 
function runner(fn, val){ 
 
    for(var i=0; i<10000000; i++){ 
 
     fn(val); 
 
    } 
 
} 
 

 
var then; 
 
var source = 123456789; 
 

 
then = new Date().getTime(); 
 
runner(pow2floor, source); 
 
console.log(" pow2floor: " + (new Date().getTime() - then)); 
 

 
then = new Date().getTime(); 
 
runner(pow2floor, source); 
 
console.log(" MATHpow2: " + (new Date().getTime() - then));

Attempting to post the results into the HTML here is altering the results. Look in your browsers console fore results.