Fast nearest power of 2 in JavaScript?

Question

Is there any faster alternative to the following expression:

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

That is, taking the closest (smaller) integer power of 2 of a double? I have such expression in a inner loop. I suspect it could be much faster, considering one could just take the mantissa from the IEEE 754 representation of the double.

Answer 1

Making use of ES6's Math.clz32(n) to count leading zeros of a 32-bit integer:

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

Here's another alternative, with benchmarks. While both seems to be comparable, I like being able to floor or ceil.

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

function pow2ceil(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 nearestPowerOf2(n) {
   return 1 << 31 - Math.clz32(n);
}

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

var then;
var source = 3000;

then = new Date().getTime();
var a = runner(pow2floor, source);
console.log("\n--- pow2floor ---");
console.log(" result: " + pow2floor(source));
console.log(" time: " + (new Date().getTime() - then) + " ms");

then = new Date().getTime();
var b = runner(MATHpow2, source);
console.log("\n--- MATHpow2 ---");
console.log(" result: " + MATHpow2(source));
console.log(" time: " + (new Date().getTime() - then) + " ms");

then = new Date().getTime();
var b = runner(nearestPowerOf2, source);
console.log("\n--- nearestPowerOf2 ---");
console.log(" result: " + nearestPowerOf2(source));
console.log(" time: " + (new Date().getTime() - then) + " ms");

// my results (results vary by system and browser)
//  pow2floor:       130 ms loser
//  MATHpow2:        147 ms loser
//  nearestPowerOf2: 47 ms clear winner!