Bit Count: Set Bit Iterator

Wed, 09/28/2005 - 07:14 — tekpool

Q: Find the number of set bits in a given integer

Sol: Set Bit (1's) Iterator

Here, the line u &= u-1 flips the highest set bit in each iteration, until there are no more set bits.


int BitCount (unsigned int u)
{
         unsigned int uCount=0 ;

         for(; u; u&=(u-1))
            uCount++;

         return uCount ;
}

Running time is proportional to the number set bits, Useful when there are less number of set bits in the number

TEKPOOL