On Monday, November 28, 2005, at 05:21 pm, Cameron Hayne wrote:
On 28-Nov-05, at 11:41 AM, Martin Taylor wrote:
inline int countBits (int i)
{
i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);
i = (i & 0x00FF00FF) + ((i >> 8) & 0x00FF00FF);
return (i & 0x0000FFFF) + ((i >> 16) & 0x0000FFFF);
}
That looks quite similar to the "Nifty Parallel Count" method on the
page by Gurmeet Singh Manku that I referred to earlier. In his tests,
this method came out a lot slower than the pre-computed array method I
mentioned.
this is quite a fast way i think:
int bitcount(unsigned x)
{
int b = 0;
if(x > 1)
b = 1;
while(x &= x - 1)
b++;
return b;
}
don't know how it compares to the other way above, but i do believe
using a look up table is the fastest way, especially if doing a lot of
counts (because of loading up or generating the look up table to start
with takes a bit of time so if less than a certain number of counts
it's quicker not to use a look up table method).
