計算log_2（n）的最快方法，其中n的形式爲2^k？

Question

說我給了n = 32。我想知道log_2（n）是什麼。 在這種情況下，log_2（32）= 5。

通常計算2^k數的對數的最快方法是什麼？

I.e. 給定n = 2^k。 log_2（n）= b。 找到b。

允許按位操作。

Answer 1

此頁面提供了六種不同的方式來做到這一點在C;將它們改爲C＃應該是微不足道的。嘗試一切，看看哪個是最快的。

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

然而，我注意到，這些技術被設計用於爲所有 32位整數的工作。如果你可以保證輸入是總是在1和2^31之間的兩個冪，那麼你可以用查找表做得更好。我提交以下內容;我沒有性能測試，但我不明白爲什麼它不該是相當快：

static int[] powers = new[] {0, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 
         30, 28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 
         31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 
         20, 8, 19, 18}; 

static int Log2OfAPower(int x) 
{ 
    return powers[((uint)x) % 37] 
} 

該解決方案依賴於以下事實：當除以二的前32個大國各自有不同的餘數37.

如果你需要它長時間工作，然後使用67作爲模數;我讓你爲數組計算正確的值。

評論者LukeH正確地指出，擁有一個據稱取負數的日誌的函數是奇怪的（1<<31是一個負號的有符號整數）。該方法可以修改爲採用uint，或者可以進行修改如果給出的數字不符合該方法的要求，則拋出異常或斷言。沒有給出哪個是正確的做法;這個問題對於這裏正在處理的確切數據類型有些模糊。

CHALLENGE：

假說：在由p，其中p是最小質數是大於n除以2的第一n權力分別具有不同的彈性模量。

如果假設是真的，那麼證明它。如果假設是錯誤的，那麼提供一個反例證明它的虛假性。

Answer 2

我認爲，如果你保證n將是2，快速路電源找到b將通過轉換n爲二進制字符串，找到的1.特殊考慮指數的情況下，當n = 0

using System.Linq; 
... 
var binaryStringReversed = Convert.ToString(value, 2).Reverse(); 
var b = binaryStringReversed.IndexOf("1"); 

編輯：

var b = Convert.ToString(value, 2).Length - 1;