JavaScript中最接近2的幂是否快?

xxhby3vn  于 2022-12-28  发布在  Java
关注(0)|答案(7)|浏览(173)

有没有更快的方法来代替下面的表达式:

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

也就是说,取一个double的最近(较小)的2的整数幂?我在一个内部循环中有这样的表达式。考虑到可以从double的IEEE 754表示中取尾数,我怀疑它可能会快得多。

8xiog9wr

8xiog9wr1#

使用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
wkftcu5l

wkftcu5l2#

这里有另一个选择,基准。虽然两者似乎是可比的,我喜欢能够下限或上限。

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**
zzlelutf

zzlelutf3#

这也是一个无分支的32位版本,它是目前为止最快的(9倍)(在手机上甚至更快!),它也可以扩展到64位或128位,增加1或2行:

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

crcmnpdw4#

不幸的是,您需要一个等效于C函数frexp的函数,我能找到的最好的是JSFiddle,它的代码使用Math.pow
沿着当前的尝试,您还可以使用真实的数据对以下几种替代方法进行基准测试:
1.从1.0开始,重复乘以2.0,直到它大于或等于输入值,然后乘以0.5,直到它小于或等于输入值。对于双精度范围末尾的值,需要进行特殊处理。
1.存储double范围中所有2的精确幂的升序值数组,并执行二进制搜索。
如果您的数据通常接近1.0,则第一种方法可能最快。第二种方法最多需要11个条件分支。

ovfsdjhp

ovfsdjhp5#

没有ES6 ...

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

换句话说:结果是2的数字的二进制表示的长度的幂减1。

wswtfjt7

wswtfjt76#

这是另一个。

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

pxq42qpu7#

还有另一种方法(这种方法比较慢,但是编写递归代码很有趣):

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

相关问题