16

Is there a method similar to Java's Integer.bitCount(int) or Long.bitCount(long) anywhere in the .NET Framework?

(For those unfamiliar with these Java methods) this is also known as:

  • Hamming Weight
  • Population Count (often called POPCNT when implemented in hardware.)

Although there are plenty of implementations to be found on the web, I was wondering if there was a standard library implementation.

I know this is not in BitArray, UInt32 or BitConverter, but maybe there's a version hidden somewhere, e.g. in a crypto function.

Community
  • 1
  • 1
finnw
  • 47,861
  • 24
  • 143
  • 221

4 Answers4

5

This functionality is not in .NET Framework nor .NET Standard but it is in .NET Core 3.0 and newer, thus including .NET 5.0 and newer, under the System.Numerics.BitOperations static class, in particular the methods

both of which return System.Int32 aka int in C#.

There are also other useful operations: count leading or trailing zeros, compute integer base-2 logarithm, and perform bit rotation aka circular shift.

Possibly the biggest benefit of/reason for doing this in the core libraries is that you can get hardware acceleration without linking to unmanaged code, and the class docs confirm this:

Provides utility methods for intrinsic bit-twiddling operations. The methods use hardware intrinsics when available on the underlying platform; otherwise, they use optimized software fallbacks.

kbolino
  • 1,441
  • 2
  • 18
  • 24
5

I know it's a very old question but it might be helpful for someone like me to have at least a workaround for this:

public static int BitCount(int n)
{
    var count = 0;
    while (n != 0)
    {
        count++;
        n &= (n - 1); //walking through all the bits which are set to one
    }

    return count;
}
Daniel B
  • 3,109
  • 2
  • 33
  • 42
4

Neither the BitVector32 nor the BitArray classes have such a method either so I believe that this method is indeed missing from the framework.

Personally, I think these classes aren’t really useful anyway since they miss many natural bit operations. I’m not sure what they are really intended for. As it is, their usefulness very limited.

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
  • 2
    Useful for efficient implementation of Hash array mapped trie: http://en.wikipedia.org/wiki/Hash_array_mapped_trie – David Grenier Jul 02 '13 at 18:17
  • @David My gripe was that the two classes have poorly designed interfaces. Of course you can use them to develop certain things but you can also use a plain bit vector (`int`) almost as well. A proper interface would make the types way more useful. – Konrad Rudolph Jul 02 '13 at 18:27
  • @gjsduarte you might change your mind if you meet a problem that can be easily solved with bitCount() in a job interview....(Apparently the interview himself thought this method exist in .NET) – Kevman May 11 '17 at 01:02
  • 2
    @Kevman I think the agreement was over the fact that the .NET classes are useless, not that a bit count method would be. – Konrad Rudolph May 11 '17 at 06:50
0

These methods are based on algorithms from Hacker's Delight. You can download C code for them here.

Nathan Ryan
  • 12,893
  • 4
  • 26
  • 37
  • As mentioned in the question, there is no shortage of methods I could download to do the job. The question is specifically about standard library methods. Java has them, I don't think .NET does (but I hope to be proved wrong.) – finnw May 06 '11 at 10:49
  • Yeah, I know there are tons of implementations. This is as close to a library that I know of, though, given the source. – Nathan Ryan May 06 '11 at 10:50