// 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**
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))
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));
7条答案
按热度按时间8xiog9wr1#
使用ES6的Math.clz32(n)来计算32位整数的前导零:
wkftcu5l2#
这里有另一个选择,基准。虽然两者似乎是可比的,我喜欢能够下限或上限。
zzlelutf3#
这也是一个无分支的32位版本,它是目前为止最快的(9倍)(在手机上甚至更快!),它也可以扩展到64位或128位,增加1或2行:
在我的计算机上:
在我的手机上:
crcmnpdw4#
不幸的是,您需要一个等效于C函数
frexp
的函数,我能找到的最好的是JSFiddle,它的代码使用Math.pow
。沿着当前的尝试,您还可以使用真实的数据对以下几种替代方法进行基准测试:
1.从1.0开始,重复乘以2.0,直到它大于或等于输入值,然后乘以0.5,直到它小于或等于输入值。对于双精度范围末尾的值,需要进行特殊处理。
1.存储double范围中所有2的精确幂的升序值数组,并执行二进制搜索。
如果您的数据通常接近1.0,则第一种方法可能最快。第二种方法最多需要11个条件分支。
ovfsdjhp5#
没有ES6 ...
换句话说:结果是2的数字的二进制表示的长度的幂减1。
wswtfjt76#
这是另一个。
pxq42qpu7#
还有另一种方法(这种方法比较慢,但是编写递归代码很有趣):