Counting bits set in a .Net BitArray Class

by

This is my solution based on the “best bit counting method” from http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

public static Int32 GetCardinality(BitArray bitArray)
{

    Int32[] ints = new Int32[(bitArray.Count >> 5) + 1];

    bitArray.CopyTo(ints, 0);

    Int32 count = 0;

    // fix for not truncated bits in last integer that may have been set to true with SetAll()
    ints[ints.Length - 1] &= ~(-1 << (bitArray.Count % 32));

    for (Int32 i = 0; i < ints.Length; i++)
    {

        Int32 c = ints[i];

        // magic (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel)
        unchecked
        {
        c = c - ((c >> 1) & 0x55555555);
        c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
        c = ((c + (c >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
        }

        count += c;

    }

    return count;

}

According to my tests, this is around 60 times faster than the simple foreach loop and still 30 times faster than the Kernighan approach with around 50% bits set to true in a BitArray with 1000 bits. I also have a VB version of this if needed.

More Related Contents:

  1. What is the best algorithm for overriding GetHashCode?
  2. .NET – How can you split a “caps” delimited string into an array?
  3. Create a hashcode of two numbers
  4. .NET Date Compare: Count the amount of working days since a date?
  5. Binding ItemsSource of a ComboBoxColumn in WPF DataGrid
  6. How do I determine the dependencies of a .NET application?
  7. How to specify the port an ASP.NET Core application is hosted on?
  8. A reference to the dll could not be added
  9. Using .NET objects within a Powershell (V5) class
  10. Encoding.UTF8.GetString doesn’t take into account the Preamble/BOM
  11. What’s the difference between ContentControl and ContentPresenter?
  12. Is there a way to call a stored procedure with Dapper?
  13. Making a WinForms TextBox behave like your browser’s address bar
  14. How to use WinDBG to track down .net out of memory exceptions?
  15. Mixed mode assembly is built against version ‘v2.0.50727′ of the runtime
  16. Find all child processes of my own .NET process / find out if a given process is a child of my own?
  17. What is the correct format to use for Date/Time in an XML file
  18. How to convert json into datatable?
  19. Does .NET 4 have a built-in JSON serializer/deserializer?
  20. System.Runtime.InteropServices.COMException (0x800A03EC)
  21. .NET MVC Call method on different controller
  22. .NET Console TextWriter that Understands Indent/Unindent/IndentLevel
  23. How do I find the .NET version?
  24. What does Error-code 0xc0000135 (or -1073741515 Exit-code) mean when starting a Windows app?
  25. Adding line breaks to c# comments for Intellisense [duplicate]
  26. What are the most valuable .Net Compact Framework Tips, Tricks, and Gotcha-Avoiders? [closed]
  27. Do you think it’s advantageous to switch to Entity Framework? [closed]
  28. .NET DataTable skips rows on Load(DataReader)
  29. Advanced Console IO in .NET
  30. When using PresentationFramework.Aero, do I need to set “Copy Local” to true (and include it in my setup project)?

Leave a Comment