计数在.NET BitArray类设置位 [英] Counting bits set in a .Net BitArray Class

问题描述

我实现我在哪里广泛使用.net BitArray类，需要一个相当于爪哇BitSet.Cardinality（）方法，即它返回设定的位数的方法的库。我想实现它作为BitArray类的扩展方法。在简单的实现是迭代计数和设置（如下图所示）位，但我想更快速的实现，因为我将要执行数千组操作和计数答案。有没有更快的方式比下面的例子？

 计数= 0;

的for（int i = 0; I＆LT; mybitarray.Length;我++）
{

  如果（mybitarray [I]）
    算上++;
}
 

解决方案

这是基于从<一个最佳位计数法我的解决方案href="http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel">http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

 公共静态的Int32 GetCardinality（BitArray bitArray）
{

    的Int32 []整数=新的Int32 [（bitArray.Count＆GT;→5）+ 1];

    bitArray.CopyTo（整数，0）;

    INT32计数= 0;

    //为不截断位在最后一个整数可能已经被设置为true的SETALL修复（）
    整数[ints.Length  -  1]＆安培; =〜（的-1;≤（bitArray.Count％32））;

    对于（的Int32 I = 0; I＆LT; ints.Length;我++）
    {

        INT32 C =整数[I]

        //魔术（http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel）
        未选中
        {
        C = C  - （（c取代;→1）及0x55555555）;
        C =（C＆安培; 0x33333333）+（（c取代;→2）及0x33333333）;
        C =（（C +（c取代;→4）及0xF0F0F0F）* 0x1010101）GT;＆GT; 24;
        }

        数+ = C;

    }

    返回计数;

}
 

根据我的测试，这是绕比简单的foreach循环快60倍，比50％左右的位设置为true的BitArray 1000位Kernighan算法仍然快30倍。如果需要，我也有这样的VB版本。

I am implementing a library where I am extensively using the .Net BitArray class and need an equivalent to the Java BitSet.Cardinality() method, i.e. a method which returns the number of bits set. I was thinking of implementing it as an extension method for the BitArray class. The trivial implementation is to iterate and count the bits set (like below), but I wanted a faster implementation as I would be performing thousands of set operations and counting the answer. Is there a faster way than the example below?

count = 0;

for (int i = 0; i < mybitarray.Length; i++)
{

  if (mybitarray [i])
    count++;
}

解决方案

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.

这篇关于计数在.NET BitArray类设置位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！