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

Comments

• Anonymous
  April 29, 2005
  Or you can point to the following collection of games played ob bits.
  
  http://graphics.stanford.edu/~seander/bithacks.html
• Anonymous
  April 29, 2005
  I used to use bitcount as an interview question.
  
  The best answer I'e ever heard for this took a constant 33 clock cycles for each block of 32bits on a 386/16 processor.
  
  Another algorithm (that assumes a 2s complement architecture):
  
  while (x)
  {
  ....x=x&(x-1);
  ....uCount +=1;
  }
  
  This takes O(number of bits on in the word). That's because x&(x-1) reduces the number bits in x by 1.
  
  Let's see, what other ways can you do this.
  
  There's the 16/256 entry lookup table - that takes 4 or 8 passes through the table.
  
  There's the version you mentioned above.
  
  There's the "count the number of enabled bits" instruction on some processor architectures (yes, there are processors that have a bitcount instruction).
  
  But my all time favorite is the constant time one.
  
  Two points for what that one is :) It does NOT involve any memory accesses (otherwise it would take more than 33 clock cycles).
• Anonymous
  April 29, 2005
  I recommend this book if you are interested in bit manipulation : Hacker's Delight by Henry Warren.
  
  http://www.amazon.com/exec/obidos/tg/detail/-/0201914654/qid=1114844633/sr=8-1/ref=pd_csp_1/104-2164595-2575901?v=glance&s=books&n=507846
• Anonymous
  June 13, 2009
  話題の小向美奈子ストリップを隠し撮り！入念なボディチェックをすり抜けて超小型カメラで撮影した神動画がアップ中！期間限定配信の衝撃的映像を見逃すな