Counting "Ones"...

Finding the number of  '1' in a binary sequence is useful. Many operations require you to create a sequence within a structure to indicate an event. For example, if the application is receiving event requests from multiple places which is getting collected in a 32 bit vector(a[32]) and at any point, it is to be determined that how many such events have occurred. The crude way of doing so is to loop through the complete vector and count the number of '1'

for(i=0;i<=32;i=i+1)

{

 if(a[i]==1)

   count= count+1;

}

This takes as much as the size of the array(32 in this case) to complete the calculations but is a nice and simple method.

If number of iterations is of importance, then there ought to be methods which only takes as many iterations as there are actual number of '1's in the number. I came across one such method and how it works amaze me because i didn't know there exist a correlation between a binary number and its successor or predecessor in binary. I need to find the proof of this method. The method simply goes like the following.

x=a;

for(count=0;x!=0;x=x&(x-1))

count = count +1;

Find proof of this?

I found this is a very famous "Brian Kernighan Algorithm"