对.Net BitArray类中设置的位数进行计数
对.Net BitArray类中设置的位数进行计数
提问于 2011-02-21 14:59:18
我正在实现一个库，在这个库中我广泛地使用了.Net BitArray类，并且需要一个与Java BitSet.Cardinality()方法等效的方法，即一个返回位数集的方法。我正在考虑将其实现为BitArray类的扩展方法。简单的实现是迭代和计算位集合(如下所示)，但我想要一个更快的实现，因为我将执行数千次集合操作并计算答案。有没有比下面的例子更快的方法？
count = 0;
for (int i = 0; i < mybitarray.Length; i++)
{
if (mybitarray [i])
count++;
}回答 9
Stack Overflow用户
发布于 2013-01-16 16:46:55
这是我基于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%的位设置为真。如果需要的话，我还有一个VB版本。
Stack Overflow用户
发布于 2011-02-21 15:08:36
使用Linq可以很容易地实现这一点
BitArray ba = new BitArray(new[] { true, false, true, false, false });
var numOnes = (from bool m in ba
where m
select m).Count();Stack Overflow用户
发布于 2011-12-15 22:14:19
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字节。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5063178
复制相关文章
相似问题
腾讯云开发者
