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

Answer 2

Unfortunately, you would need an equivalent of the C function frexp. The best I've been able to find is in JSFiddle, and its code uses Math.pow.

There are a couple of alternatives you could benchmark, using real data, along with your current attempt:

1. Starting at 1.0, multiply repeatedly by 2.0 until it is greater than or equal to the input, then multiply by 0.5 until it is less than or equal to the input. You would need special handling for values at the ends of the double range.
2. Store an ascending value array of all the exact powers of two in the double range, and do a binary search.

The first one is likely to be fastest if your data is typically close to 1.0. The second one requires up to 11 conditional branches.

Answer 3

And another way (this one is slow but it's fun to code recursive ones):

function calc(n, c) {
  c = c || 0;
  n = n >> 1;
  return (n > 0) ? calc(n, c + 1) : 2 ** c;
}

console.log(calc(345367));
console.log(calc(34536));
console.log(calc(3453));
console.log(calc(345));
console.log(calc(34));

Answer 4

And this is another.

function nP2(n) {
  return 1 << Math.log2(n);
}

console.log(nP2(345367));
console.log(nP2(34536));
console.log(nP2(3453));
console.log(nP2(345));
console.log(nP2(34));

Answer 5

Without ES6...

x=Math.floor(Math.random()*500000); //for example
nearestpowerof2=2**(x.toString(2).length-1);
console.log(x,">>>",nearestpowerof2);

In other words: the result is 2 to the power of the length of the binary representation of the number subtracted by 1.

Answer 6

Oh and I forgot the one-liner:

a=3764537465
console.log(2**~~Math.log2(a))

In other words, here we raise 2 to the power of the rounded logarithm in base 2 of the number. But alas, this is 140 times slower than the winner: blpo2 https://stackoverflow.com/a/74916422/236062

Answer 7

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

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 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;
  var st = new Date().getTime()
  for (var i = 0; i < 100000000; i++) {
    fn(val);
  }
  return (new Date().getTime() - st)
}

var source = 300000;

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

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

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

var b = runner(blpo2, source);
console.log("\n--- blpo2 ---");
console.log(" result: " + blpo2(source));
console.log(" time: " + b + " ms");

// pow2floor: 1631 ms
// MATHpow2: 13942 ms
// nearestPowerOf2: 937 ms
// blpo2 : 919 ms   **WINNER**

Answer 8

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