任何人都可以解釋這種按位函數來計算的log（n）

int howManyBits(int x) { 
    int concatenate; 
    int bias; 
    int sign = x >> 31; //get the sign 
    x = (sign & (~x)) | (~sign & x); 
    concatenate = (!!(x >> 16)) << 4; 
    concatenate |= (!!(x >> (concatenate + 8))) << 3; 
    concatenate |= (!!(x >> (concatenate + 4))) << 2; 
    concatenate |= (!!(x >> (concatenate + 2))) << 1; 
    concatenate |= x >> (concatenate + 1); 
    bias = !(x^0); 
    return concatenate + 2 + (~bias + 1); 

}

此代碼被呈現作爲一種方法來計算代表以2的補的整數n所需的比特的最小數量，並假設該int數據類型用32位表示。假設右移是算術運算。任何人都可以解釋這種按位函數來計算的log（n）

據我所知，基本的方法是取n的日誌庫2，四捨五入，然後添加1位來說明符號位。

我也明白，左移等同於2和向右移位等同於2

如此說來劃分倍增，沒有意見，我不能破譯這個代碼是做超越它獲得符號位的值的部分。我通過鉛筆和紙上的樣品int的值爲5 - 代碼工作，但我不明白爲什麼。

有人可以提供一些直觀的代碼是幹什麼的細分？

來源

2015-04-16 gallardoelise

此代碼可以使用一些註釋。

如果它是正值，或者如果爲負值，則使用補碼。這使得計算搜索最顯著一個無論正或負

x = (sign & (~x)) | (~sign & x);

我認爲下面會更清楚：

x = sign ? ~x : x;

接下來是最高的1位做了搜索與二進制搜索。首先搜索單詞的上半部分。

concatenate = (!!(x >> 16)) << 4;

如果上半部有一個1，則結果爲16。16後既作爲答案的一部分使用，也可以確定下一個要搜索。由於它在下面的班次中使用，它會導致下面的測試或者在板的上半部分或者下半部分完成。

下面的連接操作是在原始數字的逐漸減小的片段中搜索，看起來是高8位中的最高有效位或所選16位的低8位，然後高4位或所選8位的低4位，等等。

concatenate |= (!!(x >> (concatenate + 8))) << 3; // Check which 8 bits 
concatenate |= (!!(x >> (concatenate + 4))) << 2; // Check which 4 bits 
concatenate |= (!!(x >> (concatenate + 2))) << 1; // Check which 2 bits 
concatenate |= x >> (concatenate + 1);   // Check which 1 bit

偏差只是檢查數字是否爲0。只有當x是0時，它才爲1.我不瞭解XOR運算符的必要性。

最後將這些部分加在一起。

來源

2015-04-16 05:21:39

任何人都可以解釋這種按位函數來計算的log（n）

回答

相關問題