logo标签列表

JavaScript中快速找到最接近的2的幂次方？

javascriptdoublebit-manipulationieee-754
16

有没有比下面这个表达式更快的替代方案：

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

也就是说，取一个double类型的最近（较小的）整数次幂？我在内部循环中使用这样的表达式。我怀疑它可能会更快，因为可以从IEEE 754表示法的double值中直接取得尾数。

为什么不硬编码log 2的值？或者这个值太多变了？ - BatScream
啊，我当然可以做到。但是我仍然需要取对数，然后除以，再向下取整，然后再取2的幂次方。这已经太多了，因为所有信息都已经在双精度浮点数本身上了！如果我能强制转换一下就好了... - MaiaVictor
https://dev59.com/vHRB5IYBdhLWcg3w7reV - BatScream
我已经阅读了整个线程...大多数答案都处理整数，并且大多依赖于在JS上不可用的C黑客技巧... - MaiaVictor
最快的是这个：https://dev59.com/418d5IYBdhLWcg3wVQwU#74916422。 - Zibri
显示剩余2条评论
8个回答
21

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

理论上应该非常快，但我还没有测试过。 - MaiaVictor
但要注意在MDN上的polyfill。它说clz32(8)是29，而实际上应该是28，因此如果在nearestPowerOf2实现中使用它，你将得到nearestPowerOf2(8) = 4。 - Don Hatch
2
最快的是这个：https://dev59.com/418d5IYBdhLWcg3wVQwU#74916422 在电脑上快了8倍，在我的手机上快了6倍 :D - Zibri
7

这里提供另一种选择，附带基准测试。虽然两者似乎相当，但我喜欢能够向下取整或向上取整。

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

我重写了运行程序，并使用更大的数字。现在差异更加明显。 - Zibri
但是最快的答案是我的回答：https://dev59.com/418d5IYBdhLWcg3wVQwU#74916422 - Zibri
3

这里还有一个无分支的32位版本，目前是最快的（9倍）（在手机上甚至更快！）。它也可以扩展到64位或128位，只需添加1或两行代码：

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

如果JS在函数内将输入转换为整数，那么对于一些“直接按位表示”的（23位）双精度整数值来说，它实际上可能会更快。 - huseyin tugrul buyukisik
@huseyintugrulbuyukisik 第一个 ">>" 会自动将其转换为整数，从此以后它始终是一个整数。 - Zibri
0

很遗憾，你需要一个类似于 C 函数 frexp 的等效函数。我找到的最好的是在 JSFiddle，它的代码使用了 Math.pow。

有几个替代方案可以与您当前的尝试一起使用真实数据进行基准测试：

  1. 从 1.0 开始，重复乘以 2.0 直到大于或等于输入，然后乘以 0.5 直到小于或等于输入。对于处于双精度范围两端的值，您需要特殊处理。
  2. 存储双精度范围内所有精确的二次幂的升序值数组，并进行二分查找。

如果您的数据通常接近于 1.0，则第一个方法可能是最快的。第二个方法需要多达 11 个条件分支。

非常错误...我找到了最快的 :D https://dev59.com/418d5IYBdhLWcg3wVQwU#74916422 - Zibri
0

没有 ES6...

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

换句话说：结果是数字的二进制表示长度减1的幂次方为2。
0
另一种方法（这个比较慢，但编写递归函数很有趣）： 

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

0

这是另一个。

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

0

哦，我忘记了这个一行代码：

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

换句话说，这里我们将数字的以2为底的对数四舍五入后再求2的幂次方。但遗憾的是，这比获胜者blpo2 https://dev59.com/418d5IYBdhLWcg3wVQwU#74916422 慢了140倍。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接