Fast nearest power of 2 in JavaScript?

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.


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

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!

Tags:

Javascript

Double

Bit Manipulation

Ieee 754

Recent Posts