TEKPOOL

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

Sol: Looping through all the bits

In this approach, the number is looped through all its bits one by one using a right shift, and checking if the low bit is set, in every iteration by AND’ing with 0x1u

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

           for(; u; u>>=1)
                uCount += u & 0x1u;

           return uCount;
}

This algorithm will iterate through every bit, until there are not more set bits. Worst case performance occurs when the high bits is set.