Bitwise - bitCount的公式含義？

這裏是Integer.bitCount（int i）的代碼的副本Bitwise - bitCount的公式含義？

我明白所有的操作符，但不明白這些神奇的數字是如何找出計數的！任何人都可以向我解釋？我可以看到模式（1,2,4,8,16 & 0x5,0x3,0x0f）。

 public static int bitCount(int i) { 
      // HD, Figure 5-2 
      i = i - ((i >>> 1) & 0x55555555); 
      i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); 
      i = (i + (i >>> 4)) & 0x0f0f0f0f; 
      i = i + (i >>> 8); 
      i = i + (i >>> 16); 
      return i & 0x3f; 
     }

來源

2014-10-01 Jaxox

[複雜的c代碼，我需要任何一個解釋它是如何工作的]可能的重複？（http://stackoverflow.com/questions/14841995/complex-c-code-i-need-any-one-解釋它是如何工作的） – 2014-10-01 16:02:28

@PaulR你真的看過其他文章嗎？它究竟在哪裏解釋公式/算法？加上其他職位是在C和不同的公式呢！這怎麼可能重複？ – Jaxox 2014-10-01 21:31:53

答案鏈接到[here]（http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel），它解釋了這一點以及其他平行位計數方法。這種語言幾乎無關緊要，因爲Java和更廣泛的基於C語言的系列都共享相同/相似的按位運算符和語法。還要注意，這個問題還有很多其他的重複 - 很難挑選一個，我可能沒有選擇最好的一個。這裏還有一個非常好的答案：http://stackoverflow.com/a/109025/253056 – 2014-10-01 21:33:46

OK，你的代碼是32位整數，但讓我們找出16位的第一個步驟，因爲字母不具備32個字母。假設你輸入的二進制形式（含空格表示字節邊界）是

i     = ABCDEFGH IJKLMNOP 
i >>> 1   = 0ABCDEFG HIJKLMNO 
(i >>> 1) & 0x5555 = 0A0C0E0G 0I0K0M0O

所以在第一次分配右手邊的前兩位是(AB - 0A)。嘗試組合：

A B AB-0A 
0 0 00-00 = 00 
1 0 10-01 = 01 
0 1 01-00 = 01 
1 1 11-01 = 10

這樣結果的前兩位給你的比特計數輸入的前兩位。對於所有其他兩位組也是如此。

現在你又做了同樣的事情。這次我們將考慮以4爲底的輸入，所以兩位構成了下面的符號的一個數字，我們可以使用完整的32位。

i      = ABCD EFGH IJKL MNOP 
i & 0x33333333   = 0B0D 0F0H 0J0L 0N0P 
i >>> 2    = 0ABC DEFG HIJK LMNO 
(i >>> 2) & 0x33333333 = 0A0C 0E0G 0I0K 0M0O

所以結果的前四位是(0A + 0B) = A + B，並且同樣適用於任何其他組的四個比特。所以在這一點上，每組四位包含原始輸入中這四位的位數。

使用基座16時，下一個步驟是

i       = AB CD EF GH 
i >>> 4      = 0A BC DE FG 
i + (i >>> 4)    = A(A+B) (B+C)(C+D) (D+E)(E+F) (F+G)(G+H) 
(i + (i >>> 4)) & 0x0f0f0f0f = 0(A+B) 0(C+D) 0(E+F) 0(G+H)

此操作，因爲每個四比特組中的比特數將總是少於四個，因此添加兩個這樣的計數可在四個比特來表示沒有溢出。因此，加法不會從一個四位基數到另一個16位數字溢出。此時，每個字節都包含輸入字節的位數。 Other algorithms可能會從那裏使用巧妙的乘法，但您引用的代碼還會附加到下一步。

i       = A B C D 
i >>> 8      = 0 A B C 
i2 = i + (i >>> 8)   = A (A+B) (B+C) (C+D) 
i2 >>> 16     = 0 0 A (A+B) 
i3 = i2 + (i2 >>> 1   = A (A+B) (A+B+C) (A+B+C+D) 
i3 & 0x3f     = 0 0 0 (A+B+C+D)

這又利用了數字之間沒有溢出這一事實。

來源

2014-10-02 09:50:08 MvG

Bitwise - bitCount的公式含義？

回答

相關問題