瞭解使用二進制操作數來計算二進制數中1的個數的函數

Question

最近我遇到了這個問題，要求您返回二進制字符串中的連續數字，從左到右（如此11101001 = 3,011111 = 0,111101 = 4等）。問題在於只使用二元操作數來完成，而沒有任何循環。

在網上看了一下（感謝谷歌）後，我發現有人想出了這個解決方案，並希望更好地幫助理解它。

int leftBitCount(int x) { 
    int v = x; 
    int r; // store our result here 
    int shift; 
    int full = !(~x); // we must add one if we have 0xffffffff 

    // Check the top 16 bits and add them to our result if they exist 
    r  = !(~(v>>16)) << 4; 
    v <<= r; 
    // check the remaining 8 bits 
    shift = !(~(v >> 24)) << 3; 
    v <<= shift; 
    r |= shift; 
    // remaining 4 bits 
    shift = !(~(v>>28)) << 2; 
    v <<= shift; 
    r |= shift; 
    // remaining 2 bits 
    shift = !(~(v >> 30)) << 1; 
    v <<= shift; 
    r |= shift; 
    // remaining 1 bits 
    r ^= 1&((v>>31)); 

    // remember to add one if we have 32 on bits 
    return r + full; 
} 

從我所知道的，功能顯然檢查的32位整數的第16位，然後進入下一個8取決於他們是否是全1，那麼接下來的4取決於這些是否是全1 ，然後是2，然後是1等。

不幸的是，我很遺憾代碼是如何完成這個操作的，並且希望能幫助理解。

例如，在這裏：

r  = !(~(v>>16)) << 4; 
v <<= r; 

我可以看到v被移出和否定，而是很茫然，如何這有助於解決任何問題。

Answer 1

r = !(~(v>>16)) << 4; 

這裏是發生了什麼事在這條​​線：

1. v >> 16轉移的v的值（此時是x值）16個地方的權利。該表達式的底部16位是v的前16位，有趣的是，該表達式的前16位是實現定義的。與我一起工作的C編譯器已經作爲算術轉換執行了一個有符號值的右移，並且您發佈的代碼似乎在計算這一事實，但事實並非如此。有關詳細信息，請參閱this question的答案。

2. ~運算符執行步驟1中生成的值的按位補數。此處重要的觀察是，當且僅當（a）v的前16位均爲1時，以及（b）C編譯器被使用執行算術移位，則全部步驟1中表達式的位將爲1s，這意味着~(v>>16)將爲零。

3. 的!操作者執行在步驟2中所產生的值，這意味着!(~(v>>16))將是1，當且僅當在步驟2中的值是零（也就是說的v頂部16位是全1的邏輯非）。否則，該值將爲零。

4. 最後，<< 4僅僅是一個由16所以r乘法的值指定爲16如果x頂端16位被設置爲1，或零值，如果任何高16位的分別爲0（或如果正在使用的C編譯器執行邏輯右移）。

接下來，這條線：

v <<= r; 

如果v頂部16位全部爲1，這意味着的r值是16，那麼我們就不需要任何審查這些位此外，這條線將v左移16位，這基本上丟棄了我們已經檢查過的那些前16位，並將最後八位置於最上面的位置，這樣我們就可以檢查下一個。

如果，在另一方面，v頂部16位是不全1-也就是說的r的值是0，那麼v的底部 16位變得無關緊要，因爲任何數量在v中的前1位是，我們知道它必須小於16.所以在這種情況下，v <<= r保持v的值不變，我們繼續檢查v中的8個原始最高位。

算法的其餘部分基本上重複這些步驟，除了在每一步中被檢查的位數減半。所以這個代碼位檢查頂部8位：

shift = !(~(v >> 24)) << 3; 
v <<= shift; 
r |= shift; 

唯一不同這裏的事情是，r被增加了一個邏輯或而不是被直接分配，因爲它是在16位的步驟。這在功能上等同於在這種情況下的加法，因爲我們知道r的值先前爲0或16，並且shift的值同樣爲0或8，並且這些值的1位中沒有一個出現在對應位置中。然後這個代碼位做同樣與頂部4位：

shift = !(~(v>>28)) << 2; 
v <<= shift; 
r |= shift; 

然後頂端2：

shift = !(~(v >> 30)) << 1; 
v <<= shift; 
r |= shift; 

最後，頂部1：

r ^= 1&((v>>31)); 

數這樣測試的比特是16 + 8 + 4 + 2 + 1 = 31，這顯然是原始值中總比特數的一個比特，因此在全部32比特都是1的情況下是不夠的。假設所有32位均爲1，以下是如何的x原始值將在每個步驟中被移位：

16-bit step: 123456789ABCDEFGHIJKLMNOPQRSTUVW 
8-bit step: HIJKLMNOPQRSTUVW---------------- 
4-bit step: PQRSTUVW------------------------ 
2-bit step: TUVW---------------------------- 
1-bit step: VW------------------------------ 

即從未由迄今爲止觀察到的代碼中考慮的一個W位，的至少顯著位原始值。該位是結果的一部分，當且僅當它的左邊的所有位都是1時，這意味着該值中的所有位均爲1，這是在代碼頂部執行檢查的目的：

int full = !(~x); 

這是我們前面看到的按位補碼和邏輯否定的相同組合;當且僅當x中的所有位均爲1時，~x將爲零，因此!(~x)在該情況下將爲1，並且在任何其他情況下爲0。

Answer 2

好吧，

int full = !(~x); // we must add one if we have 0xffffffff 

按位反運算符（~）翻轉在其操作所有的坑。如果操作數中的所有位均置位，則結果爲零，其中邏輯否定運算符（!）將轉換爲值1（true）。否則，邏輯否定將其操作數轉換爲0（false）。

// Check the top 16 bits and add them to our result if they exist 
    r  = !(~(v>>16)) << 4; 

操作數v，假定爲32個位寬，是右移位，使得其位的上半部分都在結果的低16位結束。看起來，如果符號位被設置（即算術移位），代碼假設（不安全地）空出的位將被填滿，以便如果原始數字的前16位全部被設置，則位位否定產生0，邏輯否定轉換爲1.左移1（== 2^0）四位產生16（== 2^4），這是所討論的位數。如果不是所有的前16位都是1（或者一些，但並非所有這些位都被設置，並且右移位移到零而不是1），那麼最後會得到0 << 4，這當然是0.

v <<= r; 

我們剛剛計算的位數（16或0）向左移動。我們現在考慮原始頂部位的一小部分，或者其他位的較小部分，現在移動到頂部位置。

shift = !(~(v >> 24)) << 3; 
    v <<= shift; 

和以前一樣，但現在我們只考慮一個8位塊。

r |= shift; 

將剛剛測量的位數（8或0）添加到結果中。

的其餘部分繼續在相同的模式，在這裏：

r ^= 1&((v>>31)); 

如果v最高位被設定，它簡單地翻轉結果的底部位;由於此時代碼已保留該位未設置，所以^=可以很容易地爲+=或|=。然後我們有：

return r + full; 

記住full了值爲1，如果該參數已經設置所有位，否則爲零。上述代碼已經用盡了所有可以一次設置r一位的技巧，因爲它剛剛完成了最低位。如果輸入值確實還有一位被設置，那麼您需要使用+運算符將結果加1或模擬一個6位加法器。

請注意：此代碼似乎依賴於某些實現定義的行爲來完成其工作。您將通過使用無符號整數而不是簽名整數來避免實現定義。你仍然需要修改表達式，但是我留給你解決。