Welcome, %1$s. Please login or register.

December 12, 2017, 12:30:45 AM
: 1
: Counting bits in an integer.  ( 3964 )
« : May 12, 2007, 12:22:16 AM From Shrinidhi»



Counting bits in an integer.




Write an efficient C program to count the number of bits set in an unsigned integer.




 
Liked It? Share it!

              


« #1 : May 12, 2007, 12:23:13 AM From Shrinidhi»


if(n==1)
    num_of_set_bits = 1;
else
    while( n = n&(n-1) )
         num_of_set_bits ++;

return (num_of_set_bits);


« #2 : May 19, 2007, 11:40:32 AM From Ria»

I was asked this in Network General Interview.
Can this be done in just one step?
« #3 : January 10, 2008, 02:05:40 PM From thequark»

_If_ memory is not a huge problem then declare an array of 256 numbers [to be indexed by an 8 bit index]. ith element will contain number of bits set in the number i.


assume int is 4 bytes.

num_bit_set = arr[x & 0xFF] + arr [(x>>8) & 0xFF] + arr [x>>16 & 0xFF] + arr [x>>24 & 0xFF]

-----
a small test can be added. If the number is a power of 2 then this is not needed answer will be 1. The logic to check whether a number is power of 2 or not is:

(x != 0) && !(x & (x - 1)

------

If there are other solutions using bit masking hacks please share
« #4 : January 15, 2008, 01:52:41 AM From thequark»

I found a similar question in a separate forum :

http://www.tekpool.com/?cat=9

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


     uCount = u
              - ((u >> 1) & 033333333333)
              - ((u >> 2) & 011111111111);
     return
       ((uCount + (uCount >> 3))
        & 030707070707) % 63;



}

The logic right now went overhead, I would take a pen and paper and with some examples to understand it better. This again confirmed that such bit masking stuff can be done without loops
« #5 : January 16, 2008, 10:33:23 PM From Poonam»

Great logic quark.  :)
: 1
« previous next »

 

Best RatedList All>>



Latest
Random



SMF 2.0.10 | SMF © 2015, Simple Machines | Contact Webmaster | OnlineFunDb.com © 2009/10 | Legal Disclaimer