首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >对.Net BitArray类中设置的位数进行计数

对.Net BitArray类中设置的位数进行计数
EN

Stack Overflow用户
提问于 2011-02-21 14:59:18
回答 9查看 10K关注 0票数 25

我正在实现一个库,在这个库中我广泛地使用了.Net BitArray类,并且需要一个与Java BitSet.Cardinality()方法等效的方法,即一个返回位数集的方法。我正在考虑将其实现为BitArray类的扩展方法。简单的实现是迭代和计算位集合(如下所示),但我想要一个更快的实现,因为我将执行数千次集合操作并计算答案。有没有比下面的例子更快的方法?

代码语言:javascript
复制
count = 0;

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

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

回答 9

Stack Overflow用户

发布于 2013-01-16 16:46:55

这是我基于http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel的“最佳比特计数法”的解决方案。

代码语言:javascript
复制
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%的位设置为真。如果需要的话,我还有一个VB版本。

票数 36
EN

Stack Overflow用户

发布于 2011-02-21 15:08:36

使用Linq可以很容易地实现这一点

代码语言:javascript
复制
BitArray ba = new BitArray(new[] { true, false, true, false, false });
var numOnes = (from bool m in ba
           where m
           select m).Count();
票数 4
EN

Stack Overflow用户

发布于 2011-12-15 22:14:19

代码语言:javascript
复制
BitArray myBitArray = new BitArray(...

int
    bits = myBitArray.Count,
    size = ((bits - 1) >> 3) + 1,
    counter = 0,
    x,
    c;

    byte[] buffer = new byte[size];
    myBitArray.CopyTo(buffer, 0);

    for (x = 0; x < size; x++)
        for (c = 0; buffer[x] > 0; buffer[x] >>= 1)
            counter += buffer[x] & 1;

取自"Counting bits set, Brian Kernighan's way“,适用于字节。我将它用于1000个000+位的位数组,它非常棒。

如果你的位数不是n*8,那么你可以手动计算mod字节。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/5063178

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档