是否有任何非常快速的方法來找到一個整數的二進制對數？例如，給定一個號碼 X = 52656145834278593348959013841835216159447547700274555627155488768這樣的算法必須找到定義Y = Log（X，2），它是215 x爲總是2如何快速找到二進制對數？ （O（1）充其量）
功率的問題似乎是非常簡單的。所有需要的是找到最重要的1位的位置。有一個衆所周知的方法FloorLog，但它不是很快，特別是對於很長的多詞整數。
什麼是最快的方法？
是Bit Twiddling Hacks你在找什麼？
謝謝！非常有用的信息。 – psihodelia 2010-04-19 14:45:48
哇，我見過的一個問題解決方案的最驚人的收藏，這真是令人印象深刻的考慮的詳細程度... – 2010-04-20 07:35:47
-1：位擺弄黑客是偉大的，但它是如何幫助找到的日誌2^215？ – 2011-03-15 12:33:20
如果整數存儲在uint32_t a[]，然後我明顯的解決辦法如下：
碾過a[]線性搜索找到a[]的最高估值的非零uint32_t值a[i]（測試使用uint64_t因爲如果你的機器有原生uint64_t支持，搜索）
應用bit twiddling hacks找到uint32_t val的二進制日誌b您在步驟1中找到了您的。
評估32*i+b。
我不相信一個二進制搜索將在這裏工作，因爲一個'[]'沒有排序 - 將有0字前後都包含一個1位的一個字後。 – 2010-04-21 07:18:35
嚴。當然。我在想什麼？線性搜索將是唯一在那裏工作的東西。我已經相應地更新了答案。 – ndim 2010-04-21 13:06:36
注意：如果該整數的段被存儲在數組中，則該數據結構保持所述整數（其中所述陣列是一個組件）*應該*已經保持在手在所有時間的即時訪問的基-2對數。也就是說，一個總是知道一個巨型整數的二進制對數的庫在加法，乘法等方面要比一個必須對其進行掃描的算法效率高得多。 – 2014-07-14 22:30:14
答案是執行或語言相關。任何實現都可以將有效位的數量與數據一起存儲，因爲它通常很有用。如果必須進行計算，那麼找到該單詞中最重要的單詞/肢體和最重要的位。
快速入門：大多數浮點數表示自動對值進行標準化，這意味着它們有效地執行硬件中的循環Christoffer Hammarström mentioned。所以簡單地將一個整數轉換爲FP並提取指數應該可以實現，只要這些數字在FP表示的指數範圍內！ （在你的情況下，你的整數輸入需要多個機器字，因此需要在轉換中執行多個「移位」。）
在我頭上的最佳選擇是O（log（logn））方法，通過使用二進制搜索。下面是一個64位（<= 2^63 - 1）號碼的示例（在C++）：
int log2(int64_t num) {
int res = 0, pw = 0;
for(int i = 32; i > 0; i --) {
res += i;
if(((1LL << res) - 1) & num)
res -= i;
}
return res;
}
該算法將基本profide我具有最高編號RES如(2^res - 1 & num) == 0。當然，對於任何號碼，就可以做出來的同樣的事情：
int log2_better(int64_t num) {
var res = 0;
for(i = 32; i > 0; i >>= 1) {
if((1LL << (res + i)) <= num)
res += i;
}
return res;
}
注意，這種方法依賴於一個事實，即「位位移」操作或多或少是O（1）。如果不是這種情況，則必須預先計算2的所有冪數或形式2^2^i（2^1,2^2,2^4,2^8等）的數字並進行一些乘法運算（在這種情況下不再是O（1））。
您可以預先創建一個對數陣列。這將發現對數值高達log（N）：
#define N 100000
int naj[N];
naj[2] = 1;
for (int i = 3; i <= N; i++)
{
naj[i] = naj[i-1];
if ((1 << (naj[i]+1)) <= i)
naj[i]++;
}
數組naj是您的對數值。其中naj [k] = log（k）。 日誌是基於兩個。
這樣如何能夠快速找到2的[多詞]冪的二進制對數？ – greybeard 2016-10-22 02:44:55
@greybeard，它是小數目不計算每次調用數從CMATH的log 2，因爲它是昂貴的。這種技術通常用於創建稀疏表格。 – 2016-10-22 03:52:49
ü不能做O（1）bcuz你長了閱讀O（n）的數量 – Timmy 2010-04-19 15:08:24
^從技術上講，這是O（log₁₀N），但我明白你的意思。 – 2011-03-15 05:58:22
對於'多字[？s]的integer'以二進制表示，它似乎_identify最顯著（非零）字（和該單個1位的位置）_ - O（log n）的，或O（#words）。現在，如果需要的表示不具有「前導零」（？有人想政治家/上司/教派），這將是O（1） - 減法之後找到一個有效的表示將至少需要特別注意。 – greybeard 2016-10-22 02:45:56