计算.Net BitArray类中设置的位

Question

我正在实现一个库,我广泛使用.Net BitArray类,需要等效的Java BitSet.Cardinality()方法,即返回设置的位数的方法.我正在考虑将其实现为BitArray类的扩展方法.平凡的实现是迭代和计数位集(如下所示),但我希望更快的实现,因为我将执行数千个集合操作并计算答案.有比下面的例子更快的方法吗？

count = 0;

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

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

Answer 1

这是我的解决方案基于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;

}

根据我的测试,这比简单的foreach循环快大约60倍,并且仍然比Kernighan方法快30倍,在具有1000位的BitArray中将大约50%的位设置为true.如果需要,我也有VB版本.

Answer 2

您可以使用 Linq 轻松完成此任务

BitArray ba = new BitArray(new[] { true, false, true, false, false });
var numOnes = (from bool m in ba
           where m
           select m).Count();