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

Here is also a branchless 32 bit version which is the fastest (9x) (on cellphones even more!) as of now. It can also be scaled to 64 or 128 bits adding 1 or two lines:

x = x | (x >> 64);
x = x | (x >> 128);

on my computer:

2097152,blpo2: 118 ms **FASTEST**
2097152,nearestPowerOf2: 973 ms
2097152,pow2floor: 2033 ms

on my phone:

2097152,blpo2: 216 ms **FASTEST**
2097152,nearestPowerOf2: 1259 ms
2097152,pow2floor: 2904 ms

function blpo2(x) {
  x = x | (x >> 1);
  x = x | (x >> 2);
  x = x | (x >> 4);
  x = x | (x >> 8);
  x = x | (x >> 16);
  x = x | (x >> 32);
  return x - (x >> 1);
}

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

function nearestPowerOf2(n) {
  return 1 << 31 - Math.clz32(n);
}

function runner(fn, val) {
  var res;
  var st = new Date().getTime()
  for (var i = 0; i < 100000000; i++) {
    res = fn(val);
  }
  dt = new Date().getTime() - st;
  return res + "," + fn.name + ": " + dt + " ms"
}

var source = 3000000;

console.log(runner(blpo2, source), "**FASTEST**")
console.log(runner(nearestPowerOf2, source))
console.log(runner(pow2floor, source))