Binaryworld - Counting Bits ... [ VB -> Math ]

It seems that the only way to count the number of 1's or 0's in a binary value is creating a loop that iterates on all the 16 or 32 bits of the number. There is, however, a faster algorithm:

Click here to copy the following block

Function BitCount (ByVal number As Long) As Integer
Dim bits As Integer, temp As Long
temp = number
Do While temp
temp = temp And (temp - 1)
bits = bits + 1
Loop
BitCount = bits
End Function

While this code apparently makes little sense, it can be explained knowing that the expression n And (n - 1) actually drops the least significant (i.e. the rightmost) bit that is set in n. If you repeat this operation until the number becomes zero, you can indirectly evaluate how many 1's were in the number. On the average this requires half of the iterations needed by the standard method.