1. ## Bitcounting

I'm looking for a very fast (hopefully 'fastest') function counting bits in a UIn64 (using C#). I read about a routine called 'Hackman 169' but can't find it.

What I do have is the routine for a UInt32 :
{ // Counting bits set for UInt32
uCount = (uCount & 0x55555555) + (uCount >> 1 & 0x55555555);
uCount = (uCount & 0x33333333) + (uCount >> 2 & 0x33333333);
uCount = (uCount + (uCount >> 4)) & 0x0F0F0F0F;
uCount = uCount + (uCount >> 8);
uCount = (uCount + (uCount >> 16)) & 0x0000003F;
return (ushort) uCount;
}

I prefer a similar one for UInt64 .

Currently fastest rountine I found is:
{
ushort Count = 0;
{
Count++;
}
return Count;
}

The number of bits set in my UInt64 values vary from 0 to 8 so the function above will loop 1-9 times.

2. ## Solution for fast bitcounting UInt64

Eventually I found the solution myself and as far as i know (I didn't find anything alike on the internet) this now is fastest bitcount routine for UInt64

{ // UInt64 (uint) counting :
// Complexity : O(1) constant number of actions
// Algorithm : 64-bit recursive reduction using SWAR
const UInt64 mask1h = (~0UL) / 3 << 1;
const UInt64 mask2l = (~0UL) / 5;
const UInt64 mask4l = (~0UL) / 17;

// Replacement for the >> 8 and >> 16 AND return (BitMask & 0xff)

// Timings 1 << 26 calculations AMD XP2700+ Windows XP
// BitsSet CountLoop Count SpeedUp public static ushort CountLoop(UInt64 BitMask)
// 8 4.75 2.62 81% {
// 16 7.48 2.65 182% ushort Count = 0;
// 24 10.78 2.56 321% while (BitMask != 0)
// 32 13.42 2.68 401% {