我正在实现一个库，其中广泛使用了 .Net 中的 BitArray 类，并需要一个类似于 Java 的 BitSet.Cardinality() 方法的等效方法，即返回设置的位数的方法。我考虑将其实现为 BitArray 类的扩展方法。迭代和计算已设置的位（如下所示）是一种微不足道的实现，但是我想要更快的实现，因为我将执行成千上万次设置操作并计算答案。是否有比下面的示例更快的方法？
count = 0;
for (int i = 0; i < mybitarray.Length; i++)
{
if (mybitarray [i])
count++;
}
这是我的解决方案，基于来自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个比特位且大约50％位设置为true的BitArray中也是如此。如果需要，我还有VB版本。
BitArray ba = new BitArray(new[] { true, false, true, false, false });
var numOnes = (from bool m in ba
where m
select m).Count();
ba.Cast<bool>().Count(l => l)。最终，这只是一个伪装成foreach循环的语句。 - Adam L. S.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;
System.Numerics.BitOperations.PopCount，因此比已接受答案更快且更简单。Int32[] ints = new Int32[(bitArray.Count >> 5) + 1];
bitArray.CopyTo(ints, 0);
Int32 count = 0;
for (Int32 i = 0; i < ints.Length; i++) {
count += BitOperations.PopCount(ints[i]);
}
Console.WriteLine(count);
F#
let ints = Array.create ((bitArray.Count >>> 5) + 1) 0u
bitArray.CopyTo(ints, 0)
ints
|> Array.sumBy BitOperations.PopCount
|> printfn "%d"
UInt32 而不是 Int32。只需将第一行更改为 UInt32，它就可以正常工作了。 - NYCdotNetvar sum = mybitarray.OfType<bool>().Count(p => p);
使用 BitArray 没有更快的方法 - 最终你还需要数它们 - 你可以使用 LINQ 来完成这个操作，或者编写自己的循环，但是 BitArray 并没有提供任何方法，底层数据结构是一个 int[] 数组 (通过 Reflector 可以看到) - 因此这将始终是 O(n)，其中 n 是数组中的位数。
我能想到唯一让它变得更快的方法是使用反射来获取底层的 m_array 字段，然后你可以绕开每次调用时 Get() 进行的边界检查 (参见下文) - 但这有点不太规范，只有在非常大的数组上才值得这样做，因为反射是昂贵的。
public bool Get(int index)
{
if ((index < 0) || (index >= this.Length))
{
throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
}
return ((this.m_array[index / 0x20] & (((int) 1) << (index % 0x20))) != 0);
}
BitArray，但会跟踪设置的位数并提供适当的方法（大多数委托给BitArray，但添加方法以获取当前设置的位数）- 然后当然这将是O(1)。如果您真的想要最大化速度，可以预先计算一个查找表，其中给定一个字节值，您就有了基数，但是BitArray不是最理想的结构，因为您需要使用反射将其底层存储提取出来并操作整数类型 - 请参见this question以获得更好的解释。
另一种可能更有用的技术是使用类似Kernighan trick的东西，对于基数为m的n位值，它的时间复杂度为O(m)。
static readonly ZERO = new BitArray (0);
static readonly NOT_ONE = new BitArray (1).Not ();
public static int GetCardinality (this BitArray bits)
{
int c = 0;
var tmp = new BitArray (myBitArray);
for (c; tmp != ZERO; c++)
tmp = tmp.And (tmp.And (NOT_ONE));
return c;
}
这比在C语言中要麻烦一些，因为在整数类型和BitArrays之间没有定义操作（例如，用tmp&= tmp-1来清除最低有效位已被翻译为tmp&=（tmp&~0x1））。
对于BCL BitArray的情况，我不知道这是否比朴素迭代更快，但从算法上讲，它应该是更优秀的。
编辑：引用我发现 Kernighan 技巧的地方，并提供更深入的解释
tmp = tmp.And (tmp.And (NOT_ONE)); 似乎无法正常工作。在 tmp 和 NOT_ONE 之间执行 And 运算将导致 tmp 的最低有效位设置为 0，而其他所有位都保持不变。在 tmp 和 tmp0（其中 tmp0 的最低位设置为 0）之间执行 And 运算将导致 tmp0，因为 1 and 1 是 1 and 0，任何数和 0 都是 0。这将导致第一次迭代将最低有效位设置为 0，但所有其他迭代都不会做任何事情（除非我误解了什么）。 - Trisped如果您不介意将 System.Collections.BitArray 的代码复制到您的项目中并进行编辑，您可以按照以下方式编写：
（我认为这是最快的方法。我已经尝试使用 BitVector32[] 实现我的 BitArray，但速度仍然很慢。） public void Set(int index, bool value)
{
if ((index < 0) || (index >= this.m_length))
{
throw new ArgumentOutOfRangeException("index", "Index Out Of Range");
}
SetWithOutAuth(index,value);
}
//When in batch setting values,we need one method that won't auth the index range
private void SetWithOutAuth(int index, bool value)
{
int v = ((int)1) << (index % 0x20);
index = index / 0x20;
bool NotSet = (this.m_array[index] & v) == 0;
if (value && NotSet)
{
CountOfTrue++;//Count the True values
this.m_array[index] |= v;
}
else if (!value && !NotSet)
{
CountOfTrue--;//Count the True values
this.m_array[index] &= ~v;
}
else
return;
this._version++;
}
public int CountOfTrue { get; internal set; }
public void BatchSet(int start, int length, bool value)
{
if (start < 0 || start >= this.m_length || length <= 0)
return;
for (int i = start; i < length && i < this.m_length; i++)
{
SetWithOutAuth(i,value);
}
}
在找不到使用查找表的版本后，我写了自己的after函数。
private int[] _bitCountLookup;
private void InitLookupTable()
{
_bitCountLookup = new int[256];
for (var byteValue = 0; byteValue < 256; byteValue++)
{
var count = 0;
for (var bitIndex = 0; bitIndex < 8; bitIndex++)
{
count += (byteValue >> bitIndex) & 1;
}
_bitCountLookup[byteValue] = count;
}
}
private int CountSetBits(BitArray bitArray)
{
var result = 0;
var numberOfFullBytes = bitArray.Length / 8;
var numberOfTailBits = bitArray.Length % 8;
var tailByte = numberOfTailBits > 0 ? 1 : 0;
var bitArrayInBytes = new byte[numberOfFullBytes + tailByte];
bitArray.CopyTo(bitArrayInBytes, 0);
for (var i = 0; i < numberOfFullBytes; i++)
{
result += _bitCountLookup[bitArrayInBytes[i]];
}
for (var i = (numberOfFullBytes * 8); i < bitArray.Length; i++)
{
if (bitArray[i])
{
result++;
}
}
return result;
}