Brian Kernighan's algorithm
·
We generally use this algorithm
to find the number of set bits present in binary numbers.
·
If we subtract a number by 1 and do it bitwise & with itself (n & (n-1)), we unset the rightmost set
bit. If we do n & (n-1) in a loop and count the number of times the loop
executes, we get the set bit count.
·
The beauty of this solution is the number of times it loops is equal to
the number of set bits in a given integer.
0 Comments