注意:自从V8实现以来,Math.log2并没有实际更改。也许你记错了,或者你包含了一个shim,在Chrome包含其自己的Math.log2实现之前恰好得到了这些特殊情况的正确结果。
此外,似乎你应该使用Math.ceil(x)而不是Math.floor(x)+1。
如何解决这个问题?
为了避免依赖于JavaScript的不同实现中Math.log或Math.log2的准确性(所使用的算法是实现定义的),如果您的二叉树元素少于2^32个,可以使用位运算符。显然,这不是最快的方法(只有O(n)),但这是一个相对简单的例子。
function log2floor(x) {
if (x === 0) return -Infinity;
for (var i = 0; i < 32; ++i) {
if (x >>> i === 1) return i;
}
}
console.log(log2floor(36) + 1);
Math.log2
在不同浏览器中是如何实现的?
目前Chrome的实现存在精度问题,因为它们依赖于将Math.log(x)
的值乘以Math.LOG2E
,使其容易受到舍入误差的影响(source):
// ES6 draft 09-27-13, section 20.2.2.22.
function MathLog2(x) {
return MathLog(x) * 1.442695040888963407; // log2(x) = log(x)/log(2).
}
如果你正在使用Firefox,它会使用本地的
log2
函数(如果存在),否则(例如
在Windows上),将使用类似Chrome的实现(
来源)。
唯一的区别是,它们不是乘以
log(2)
,而是除以
log(2)
:
double log2(double x)
{
return log(x) / M_LN2;
}
乘法或除法:有多大的差别?
为了测试通过除以Math.LN2
和乘以Math.LOG2E
之间的差异,我们可以使用以下测试:
function log2d(x) { return Math.log(x) / Math.LN2; }
function log2m(x) { return Math.log(x) * Math.LOG2E; }
for (var i = 0; i < 1024; ++i) {
var resultD = log2d(Math.pow(2, i));
var resultM = log2m(Math.pow(2, i));
if (resultD !== i) console.log('log2d: expected ' + i + ', actual ' + resultD);
if (resultM !== i) console.log('log2m: expected ' + i + ', actual ' + resultM);
}
请注意,无论使用哪个函数,它们仍然会在某些值上存在浮点误差
1。恰好发生的是,
log(2)
的浮点表示小于实际值,导致一个比实际值
更高的值(而
log2(e)
则更低)。这意味着对于这些特殊情况,使用
log(2)
将向下舍入到正确的值。
1: log(pow(2, 29)) / log(2) === 29.000000000000004
Math.log2 = function(x) { return Math.log(x) / Math.LN2 };)
在 Chrome 中实际上为精确的幂返回了正确的结果。 - raina77owMath.round
而不是Math.floor
呢? - soktinpk