Counting set bits in binary representation of a positive integer for beginners (Brian Kernighan's algorithm )

 I will call it a post for beginners , prerequisites might be basic understanding of binary number system, how to convert fromm decimal to binary form for positive integers and basic binary operations

problem at hand:
Given a positive integer  N in base 10, we want to find how many 1's ( set bits ) are there in the binary representation of N


 First thought might be , we know how to convert a decimal to binary and in that process we can keep a note of how many 1's we have seen and that is our answer.

example
say we can convert 4 to (100)₂ or 7 to (111)₂ , so we directly get the number of 1's in the process and our problem is solved

but this post is aimed at introducing you to interesting uses of binary operations and one such use is solving our problem at hand and we have an algorithm for that called Brian Kernighan's algorithm 

 now lets see the binary representation of 256 its (100000000)₂
 as we see their is only one set bit , so can we do something which might help us solve at least this case with only one set bit without manually looking at each bit ?

CLAIM: any binary representation containing only one set bit is a power of 2
// try to convert some powers of 2 to binary representation and try to see why this claim is true


so now i will present what actually lies at the heart of  Brian Kernighan's algorithm
its this binary operation

n & (n-1)

whole magic trick we are trying to pull here lies in this expression , so lets see what it does

for the sake of not escalating too quickly we will first look at the case of numbers with only one bit set (or as i said powers of 2)

I claim that our binary operation ( n & (n-1)) will give 0 for every power of 2

n	n in base 2	n-1 in base 2	n & (n-1)
1	1	0	0
2	10	1	0
4	100	11	0
8	1000	111	0
16	10000	1111	0

it can be proved by using the fact that power of 2 have only one bit set but n-1 have all bits set but the bit which was set in n is not set in n-1 so when we take n & (n-1) which is bitwise, no set bit corresponds to set bit and so the result is zero
re- read the above statement and let it sink in

so now we have established that for n being power of 2   n & (n-1)  shall result in zero

let me restate that
performing n & (n-1)  unset the set bit from n
trivial to say that as there was only 1 bit which was set .. so yes that was unset

now we move to general case lets see what n&(n-1) does to any random value
 I will randomly generate a table   

n	n in base 2	n-1 in base 2	n & (n-1) in base 2
56	111000	110111	110000
60	111100	111011	111000
44	101100	101011	101000
68	1000100	1000011	1000000
60	111100	111011	111000

now we have something interesting to observe
observe  what is the difference between n and (n-1) in base 2 representation
first set bit from right (least significant bit which is set) is unset

Lets see how we can have some proof for this
Its actually not very hard to see
observe that first set bit from right and all zeroes on its right taken together will behave like a power of 2 as there is only one bit set and n-1 affects only those bits  and higher bits will remain same
now  x & x = x so higher bits remain unchanged even after (n & (n-1))

so we can claim that in general case n & (n-1)  unsets the least significant bit which was set
and if keep repeating this operation then eventually all set bits will be unset one by one
( note that repeating means value of  n&(n-1 ) becomes the new value of  n for next iteration)
and we will reach zero
as in one operation we remove one set bit
number of iterations will directly give us number of set bit

following is a simple javascript implementation:

 function count_set_bits( n ){  
  var count =0;  
  while(n>0){  
   n = (n & (n-1));  
   count++;
  }  
  return count;  
 }  

 alert(count_set_bits(7)); //alerts 3