c# Fast Bitcount for UInt64 needed

[SoftwareTester]

I need a fast bitcount for UInt64
My variables usually contain up to 8 bits set but regurlarly between 30 and 56.

At various places i found a fast one for UInt32 and on one site I even found a generalised version http://www.mathematik. uni-bielefeld.de/~sillke/PROBLEMS/bitcount (plus description).

The UInt32 version works fine but enhancing that by the line
w += w >> 32; simply doesn't work on my system (AMD-XP2700+ , windows XP). I don't know if this has something to do with 'wordorder' as I have a 32 bits system, or something else.

What I would like to know is how to extend that algorithm to get it working for UInt64 (using C#, Visual Studio Express 2008) or an alternative fast algorithm.

The code from that site:
******** Start code
int Count (unsigned int w)
{
// binary technique for 2**n bit words with n=5.
const unsigned int mask1h = (~0U) / 3 << 1;
const unsigned int mask2l = (~0U) / 5;
const unsigned int mask4l = (~0U) / 17;
// const unsigned int mask8l=(~0U)/(((1<<(128+8))-1)/255);
w -= (mask1h & w) >> 1;
w = (w & mask2l) + ((w>>2) & mask2l);
w += w >> 4; // 8 bit fold.
w &= mask4l; // set width=8.
w += w >> 8; // 16 bit fold.
w += w >> 16; // 32 bit fold.
// w += w >> 32; // 64 bit fold.
// w += w >> 64; // 128 bit fold.
// w &= mask8l; // set width=128.
// w += w >> 128; // 256 bit fold.
// w += w >> 256; // 512 bit fold.
// w += w >> 512; //1024 bit fold.
return w & 0xff; // select 8 bits. (4<=n<8)
// return w & 0xfffffffffffff fffffffffffffff ffff; //select 128 bits (n>=8)
}
*************** *** End code

(BTW I know about that improvement by AMD for UInt32 [making it faster indeed on my PC]
BitMask -= ((BitMask >> 1) & 0x55555555);
BitMask = (((BitMask >> 2) & 0x33333333) + (BitMask & 0x33333333));
BitMask = (((BitMask >> 4) + BitMask) & 0x0f0f0f0f);
return (ushort)((BitMa sk * 0x01010101) >> 24);
And it would be great if somebody could extend that for UInt64 s as well)

[Plater]

Maybe I am missing something but...what do you mean by "bitcount"?
Uint32 always has 32bits, just like a uint64 always has 64bits...
Did you mean count the number of 1s?

The BitArray class might be usefull?

I find it hard to believe that counting the 1s in any of these are "slow", being that they execute in less then a milisecond?

[SoftwareTester]

Maybe I am missing something but...what do you mean by "bitcount"?
Uint32 always has 32bits, just like a uint64 always has 64bits...
Did you mean count the number of 1s?

The BitArray class might be usefull?

I find it hard to believe that counting the 1s in any of these are "slow", being that they execute in less then a milisecond?

Indeed I mean 'the number of 1s in an UInt64 I'm after". (but I thought 'bitcount' has bene used quite often for this; sometimes 'populationcoun t' or something like that; sorry being inaccurate in this)

No I don't think BitArray will be useful to me.
I have to evaluate a few MILLION times a UInt64 against over 10 million UInt64 s.
This can take several days.
And worse : I have to do that more or less regurlarly.

So i really need a fast way of counting the number of bits set in a UInt64 (and some other things) and I can hardly believe BitArray class will be fast enough (as it does have overhead in calling of course)
Obviously I'm looking at 'grouping' the 10 million UInts and skipping parts of them, but a really fast bitcount function would be a great help.

[Plater]

.NET itself is huge overhead and not really good for doing things in "the most efficient way".
You could probably pinvoke a c/c++ dll, or use a fortran rutine if need be.

[SoftwareTester]

.NET itself is huge overhead and not really good for doing things in "the most efficient way".
You could probably pinvoke a c/c++ dll, or use a fortran rutine if need be.

Sure you're right about .NET having huge overload and quite funny you mention Fortran as I've been using that for several decades "but it is oldfashioned"pe ople say.

Anyway I managed to findout myself (of course after searching the internet as well [but NOT finding])
What I came up is as far as I know faster bitcount function around:

public static ushort Count64(UInt64 BitMask)
{ // UInt64 (uint) counting :
// Complexity : O(1) constant number of actions
// Algorithm : 64-bit recursive reduction using SWAR
const UInt64 MaskMult = 0x0101010101010 101;
const UInt64 mask1h = (~0UL) / 3 << 1;
const UInt64 mask2l = (~0UL) / 5;
const UInt64 mask4l = (~0UL) / 17;
BitMask -= (mask1h & BitMask) >> 1;
BitMask = (BitMask & mask2l) + ((BitMask >> 2) & mask2l);
BitMask += BitMask >> 4;
BitMask &= mask4l;
// BitMask += BitMask >> 8;
// BitMask += BitMask >> 16;
// BitMask += BitMask >> 32;
// return (ushort)(BitMas k & 0xff);
/ / Replacement for the >> 8 and >> 16 AND return (BitMask & 0xff)
return (ushort)((BitMa sk * MaskMult) >> 56);

// Timings 1 << 26 calculations AMD XP2700+ Windows XP
// BitsSet CountLoop Count SpeedUp public static ushort CountLoop(UInt6 4 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% {
// 40 16.44 2.60 532% BitMask &= (BitMask - 1);
// 48 19.51 2.59 653% Count++;
// 56 22.33 2.67 736% }
// 64 25.56 2.61 879% return Count;
// Average 15.03 2.62 473% }

}


If anybody finds a faster function or can improve the one above, please let me know.

Jack Renet