什么是计算32的幂的对数的最快方法？

Question

考虑到语言是javascript，并且输入为< 1073741824，最快的方法是获得等同于以下内容：

Math.floor(Math.log(len) / Math.log(32))

我尝试使用if条件语句：

if (len < 1024) return 1;
if (len < 32768) return 2;
if (len < 1048576) return 3;
if (len < 33554432) return 4;
if (len < 1073741824) return 5;

使用位运算符：

// 0000000000000000000000000100000 // 32
// 0000000000000000000010000000000 // 1024
// 0000000000000001000000000000000 // 32768
// 0000000000100000000000000000000 // 1048576
// 0000010000000000000000000000000 // 33554432
// 1000000000000000000000000000000 // 1073741824
function log32(len) {
    return (
        0 + 
        !!(len >>> 30) + 
        !!(len >>> 25) + 
        !!(len >>> 20) + 
        !!(len >>> 15) + 
        !!(len >>> 10) +
        !!(len >>> 5
    )
}

有没有更简洁或操作较少的方法来完成这个任务呢？ （性能测试使用：https://jsperf.com/log32-perf/）

- BenG

---

位操作技巧怎么样呢？ - Gonras Karols

你认为用if级联方式有什么问题？我无法想象出更快的方法，或者更少操作的方法，即使它看起来有些狡猾或在数学上不够优雅。（顺便说一下，鉴于你最初的假设是输入始终小于1073741824，你甚至不需要最后的比较操作和if条件语句，只需返回5就可以了。） - jez

Answer 1

我建议使用非常高效的Math.clz32方法，该方法返回一个数在32位二进制表示中前导零的个数。

const log32 = x => Math.floor((31 - Math.clz32(x))/5);

console.log(log32(1023)); // 1
console.log(log32(1024)); // 2

这将返回 32 位范围内任何 x > 0 的正确值。

- trincot

---

不错 +1；比log2()更好。顺便说一下，你可以用*0.2代替/5，这样通常会更快。 - Matt

令人印象深刻的 +1。如果我们将 Math.floor 替换为 result | 0，我们可以再节省一点时间。这样测量速度比我的 if 语句更快。 - BenG

在火狐浏览器中，无论是使用*0.2还是|0，都没有获得任何显著的改善：这两种解决方案有大约50%的时间表现最快。 - trincot