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);
}
This can easily be modified and extended to work with 64 bits with
only one extra line of calculation
Martin
On 28 Nov 2005, at 16:02, Cameron Hayne wrote:
On 28-Nov-05, at 5:51 AM, Bruno Causse wrote:
I seek the fastest method to count the bits has 1 in a unsigned
long long
I use the following code for 32-bit unsigned int values - it is
easily modified for other value sizes. It makes use of a pre-
computed array 'BitsInChar' (which is independent of the data and
calculated at program initialization):
// This is derived from the 'precomputed_bitcount' routine
// on the web page "Counting Number of On Bits in an
Integer"
// by Gurmeet Singh Manku
// http://www-db.stanford.edu/~manku/bitcount/
bitcount.html
