算法的強大——快速計算一個正二進制整數中包含多少個1

　　原題：一個正整數，轉成二進制後，這個二進制數包含多少個1？

　　這個問題在網上看過多次，幾番思考，也沒有什麼好的辦法。采用最基本的辦法，逐位判斷，是1的統計加1，最後将統計數傳回。

　　以下是這個思路的VB2008代碼，不失一般性，将正整數的範圍控制在（1~231-1）

　　Private Function GetCount1OfValue(ByVal Value As Integer) As Integer

　　　　Dim i As Integer, Count As Integer = 0

　　　　For i = 0 To 30

　　　　　　If (Value And 2 ^ i) = 2 ^ i Then Count += 1

　　　　Next

　　　　Return Count

　　End Function

　　但是近日，在網上發現一個很巧妙的算法，能夠快速實作上述的計算功能。代碼貼于下方

　　Private Function GetCount1OfValue(ByVal Value As Integer) As Integer　　

　　　　Dim Count As Integer = 0

　　　　Do While Value > 0

　　　　　　Value = Value And (Value - 1)

　　　　　　Count +=1

　　　　Loop

　　這段代碼的精髓就是在這一句：Value = Value And (Value - 1)

　　那麼這句語句到底起到什麼作用呢？看下面的分析

　　假設Value=X1X2……Xn-1Xn，其中Xi(1≤i≤n)為1或0

　　不妨設Xi是最右邊的1，那麼Value就可以寫成如下的形式

　　Value=X1X2……Xi-1Xi0……0，其中(1≤i≤n)，Xi後面有n-i個0

　　因為Xi=1，是以Value=X1X2……Xi-110……0，其中(1≤i≤n)，1後面有n-i個0

　　則Value-1=X1X2……Xi-101……1，其中(1≤i≤n)，0後面有n-i個1

　　則Value And (Value-1)=X1X2……Xi-100……0，其中(1≤i≤n)，Xi-1後面有n-i+1個0

　　

　　是以，Value And (Value-1)的效果把最右邊的1變成0

　　在上面的代碼中，每把最右邊的1變成0，則統計數加1，直到所有的1變成0為止。

　　這兩個算法，第一個算法的循環次數是固定的，是31次，無論數值是多少（必須在範圍之内）。而第二個算法和Value中的1的個數有關，循環的次數就是1的個數，可見該算法之妙。