What is the fastest way to count set bits in UInt32

by

The bit-twiddling hacks page has a number of options.

Of course, you could argue that iterating over all 32 possible bits is O(N) in that it’s the same cost every time 🙂

For simplicity, I’d consider the lookup-table-per-byte approach, or Brian Kernighan’s neat idea which iterates as many times as there are bits set, which I’d write as:

public static int CountBits(uint value)
{
    int count = 0;
    while (value != 0)
    {
        count++;
        value &= value - 1;
    }
    return count;
}

If you don’t like the idea of populating a 256-entry lookup table, a lookup-per-nybble would still be pretty fast. Mind you, it’s possible that 8 array lookups might be slower than 32 simple bit operations.

Of course, it’s worth testing your app’s real performance before going to particularly esoteric approaches… is this really a bottleneck for you?

More Related Contents:

  1. Can’t use Count() in C#
  2. How to find all partitions of a set
  3. A method to count occurrences in a list
  4. C# Set collection?
  5. Count the number of times a string appears within a string [duplicate]
  6. c# – How to iterate through classes fields and set properties
  7. Iterating through the Alphabet – C# a-caz
  8. Count property vs Count() method?
  9. How to count the number of elements that match a condition with LINQ
  10. Byte to Binary String C# – Display all 8 digits
  11. Return max repeated item in list
  12. How to use LINQ to find all combinations of n items from a set of numbers?
  13. What is the binary representation of a boolean value in c#
  14. Throttling asynchronous tasks
  15. Object cannot be cast from DBNull to other types
  16. Gradient Circles for Map Generator
  17. DateTime “null” value
  18. C# Export Private/Public RSA key from RSACryptoServiceProvider to PEM string
  19. C# ‘is’ operator performance
  20. Web API 2: how to return JSON with camelCased property names, on objects and their sub-objects
  21. What are the benefits to marking a field as `readonly` in C#?
  22. How do I use the LINQPad Dump() extension method in Visual Studio? [closed]
  23. Get Substring – everything before certain char
  24. How to get the logon SID in C#
  25. Will the base class constructor be automatically called?
  26. Can you explain Liskov Substitution Principle with a good C# example? [closed]
  27. MemoryStream.Close() or MemoryStream.Dispose()
  28. How to add custom Http Header for C# Web Service Client consuming Axis 1.4 Web service
  29. How to use int.TryParse with nullable int? [duplicate]
  30. Converting a csv file to json using C#

Leave a Comment