TEKPOOL

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

Sol: Unset Bit (0's) Iterator

This is similar to the Set Bit Iterator method, expect that all bits are toggled before iteration, and uCount is decremented whenever a set bit (originally unset) is encountered.

int BitCount (unsigned int u)
{
        //number of bits in unsigned int
        unsigned int uCount= 8 * sizeof(unsigned int);

        // Toggle bits
        u ~= (unsigned int) -1 ;
        for(; u; u&=(u-1))
            uCount--;

        return uCount ;
}

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