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.

Why dont you hardcode the value of log 2?, or is that too variable? — BatScream, Nov 17 '14 at 03:47
Ah, I can do that, of course. But I'm still taking a log, then dividing, then taking a floor, then taking a power of 2. That is too much already, when the information is all there already on the double itself! If I just could cast... — MaiaVictor, Nov 17 '14 at 03:49
http://stackoverflow.com/questions/466204/rounding-off-to-nearest-power-of-2 — BatScream, Nov 17 '14 at 03:56
I've read the whole thread already actually... most of its answers treats integers and mostly depends on C hacks which aren't available on JS... — MaiaVictor, Nov 17 '14 at 03:59
That expression will not always work for doubles near powers of two. For example, try x=35184372088831.9 (just below 2^45). Your expression returns 2^45, not 2^44. — Rick Regan, Nov 17 '14 at 13:46
You can access mantissa & exponent of a JavaScript number using ArrayBuffer and typed arrays, see http://stackoverflow.com/a/17156580/1647737 - however it might not be fast enough for your purpose. — le_m, Mar 15 '17 at 19:59

score 18 · Accepted Answer · answered Mar 15 '17 at 00:32

18

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

answered Mar 15 '17 at 00:32

le_m

17,771
9
60
73

Should be very fast in theory, but I didn't test yet. – MaiaVictor Mar 15 '17 at 23:28
But beware the polyfill at [MDN](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/clz32) . It says clz32(8) is 29 when it should be 28, so if used in this nearestPowerOf2 implementation, you'll get nearestPowerOf2(8) = 4. – Don Hatch Apr 08 '17 at 01:54

bob · Answer 2 · 2020-09-20T05:09:29.520

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!

Patricia Shanahan · Answer 3 · 2014-11-17T18:45:36.080

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:

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

Fast nearest power of 2 in JavaScript?

3 Answers3