JavaScript中最快的2次幂？

Question

是否有更快的替代以下表达式:

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

也就是说,取最接近(较小)的2的整数倍？我在内循环中有这样的表达.我怀疑它可能会快得多,考虑到可以从双尾的IEEE 754表示中获取尾数.

Answer 1

利用ES6的Math.clz32(n)来计算32位整数的前导零:

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

这是另一种带有基准的替代方案。虽然两者似乎具有可比性，但我喜欢能够使用地板或天花板。

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 3

这也是一个无分支 32 位版本，是目前最快的(9x)（在手机上速度更快！）。它还可以通过添加 1 行或两行扩展到 64 或 128 位：

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

在我的电脑上：

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

在我的手机上：

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

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