有没有比下面这个表达式更快的替代方案:
Math.pow(2,Math.floor(Math.log(x)/Math.log(2)))
也就是说,取一个double类型的最近(较小的)整数次幂?我在内部循环中使用这样的表达式。我怀疑它可能会更快,因为可以从IEEE 754表示法的double值中直接取得尾数。
有没有比下面这个表达式更快的替代方案:
Math.pow(2,Math.floor(Math.log(x)/Math.log(2)))
也就是说,取一个double类型的最近(较小的)整数次幂?我在内部循环中使用这样的表达式。我怀疑它可能会更快,因为可以从IEEE 754表示法的double值中直接取得尾数。
使用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
这里提供另一种选择,附带基准测试。虽然两者似乎相当,但我喜欢能够向下取整或向上取整。
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**
这里还有一个无分支的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))
很遗憾,你需要一个类似于 C 函数 frexp
的等效函数。我找到的最好的是在 JSFiddle,它的代码使用了 Math.pow
。
有几个替代方案可以与您当前的尝试一起使用真实数据进行基准测试:
如果您的数据通常接近于 1.0,则第一个方法可能是最快的。第二个方法需要多达 11 个条件分支。
没有 ES6...
x=Math.floor(Math.random()*500000); //for example
nearestpowerof2=2**(x.toString(2).length-1);
console.log(x,">>>",nearestpowerof2);
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));
这是另一个。
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));
哦,我忘记了这个一行代码:
a=3764537465
console.log(2**~~Math.log2(a))