Number of set bits in an integer (Hamming weight)

Example:

Input: 00000000000000000000000000000101
Output: 2
Explanation: The input binary string 00000000000000000000000000000101 has a total of two '1' or set bits.

Approach: Using Brian Kernighan algorithm. Basically this algorithm relies on the fact that subtracting '1' from a number flips all the bits after the rightmost set bit including the rightmost set bit so if we do n & (n - 1), it will unset the rightmost set bit. 

Now we can have a loop until n becomes 0 by doing n = n & (n - 1) that means 1 by 1 all the (rightmost) set bits will be unset and n will become 0. Obviously the number of times loop will run will be our answer.

Implementation in C#:

        public int NumOfSetBits(uint n)

        {

            int count = 0;

            while(n > 0)

            {

                n = n & (n - 1);

                ++count;

            }

            return count;

        }

Complexity: O(logn)