什麼是計算32的冪對數的最快方法？

鑑於語言是JavaScript，並輸入是< 1073741824，有什麼獲得相當於最快的方法：什麼是計算32的冪對數的最快方法？

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

我已經試過了，如果：

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/）

來源

2017-04-19 BenG

[bit twiddling hack]（https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog）怎麼樣？ –

你認爲你的'if'級聯方法有什麼問題？我無法想象一種*更快的方式，或者更少的操作方式，即使它看起來很拙劣或數學上不雅。（根據你的初始假設，輸入總是小於1073741824，你甚至不需要最後的比較操作，如果有條件的話，只需要返回5;就可以了。） – jez

我會去非常有效的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的正確的值。

來源

2017-04-19 20:39:26 trincot

Nice + one;比log2（）更好。順便說一句，你可以用'* 0.2'替換'/ 5'，這通常更快。 – Matt

令人印象深刻的+1。如果我們交換Math.floor以獲得結果| 0，我們可以剃另一個頭發，然後測量比我的速度更快 – BenG

在FF中，我用'* 0.2'和'| 0'都沒有得到任何顯着的改善：任何一種解決方案在50％。 – trincot

什麼是計算32的冪對數的最快方法？

回答

相關問題