Bit Fiddling - 1

 Bits and Pieces

 

Over the years, I have come across interesting approaches and problems involving bit manipulations. Over this series, I will post a wide range of related solutions and algorithms.

 

Counting Number of Set Bits

 

1. The Trivial Straightforward approach

 

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.

 

 

2. Set Bit 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

 

3. UnSet Bit Iterator

 

This is similar to the above 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) 

{ 

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

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

        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

 

 

In the next post we will discuss, fastest ways to solve this problem, and after that we will look into some tricky, nifty and brilliant solutions some of which are constant time, the ones Larry was referring