25

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

count = 0;

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

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

11 回答 11

36

这是我基于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 版本。

于 2013-01-16T08:46:55.313 回答
4

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

BitArray ba = new BitArray(new[] { true, false, true, false, false });
var numOnes = (from bool m in ba
           where m
           select m).Count();
于 2011-02-21T07:08:36.210 回答
2

我有同样的问题，但不仅仅是一种基数方法来转换。所以，我选择移植整个 BitSet 类。幸好它是独立的。

这是C# 端口的要点。

如果有人报告发现的任何错误，我将不胜感激——我不是 Java 开发人员，并且对位逻辑的经验有限，所以我可能翻译了一些错误。

于 2014-12-03T05:07:20.033 回答
2 
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 ”并适用于字节。我将它用于 1 000 000+ 位的位数组，它非常棒。
如果您的位不是 n*8，那么您可以手动计算 mod 字节。

于 2011-12-15T14:14:19.030 回答
2

由于使用了比公认的答案更快、更简单的版本System.Numerics.BitOperations.PopCount

C＃

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"

请参阅BitOperations.PopCount 是在 .NET 中计算 BitArray 基数的最佳方法吗？

于 2021-04-24T23:34:41.413 回答
1

您可以使用 Linq，但它会无用且速度较慢：

var sum = mybitarray.OfType<bool>().Count(p => p);
于 2011-02-21T07:08:40.933 回答
1

在没有找到使用查找表的版本之后，我编写了我的版本：

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;
}
于 2014-09-16T13:41:15.457 回答
1

使用没有更快的方法BitArray-归结为您必须对它们进行计数-您可以使用 LINQ 来执行此操作或执行自己的循环，但是没有提供方法，BitArray并且基础数据结构是int[]数组（如反射器所示） - 所以这将始终是 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)。

于 2011-02-21T07:14:01.313 回答
1

如果您不介意将 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);
        }
    }
于 2011-11-04T03:10:00.253 回答
1

如果您真的想最大化速度，您可以预先计算一个查找表，其中给定一个字节值您有基数，但 BitArray 不是最理想的结构，因为您需要使用反射来拉对其进行底层存储并对整数类型进行操作 - 请参阅此问题以更好地解释该技术。

另一种可能更有用的技术是使用类似Kernighan 技巧的东西，对于基数 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 技巧的地方，并提供了更深入的解释

于 2011-02-21T07:37:33.887 回答
0

问题自然是 O(n)，因此您的解决方案可能是最有效的。

由于您试图计算位的任意子集，因此您无法在设置位时对其进行计数（如果您不经常设置位，将提供速度提升）。

您可以检查您正在使用的处理器是否有一个将返回设置位数的命令。例如，根据这篇文章，具有 SSE4 的处理器可以使用 POPCNT 。这可能对您不起作用，因为.Net 不允许组装（因为它与平台无关）。此外，ARM 处理器可能没有等效的。

可能最好的解决方案是查找表（或者如果您可以保证开关将编译为单次跳转到 currentLocation + byteValue，则进行开关）。这将为您提供整个字节的计数。当然，BitArray 不提供对底层数据类型的访问权限，因此您必须制作自己的 BitArray。您还必须保证字节中的所有位始终是听起来不太可能的交集的一部分。

另一种选择是使用布尔数组而不是 BitArray。这具有不需要从字节中的其他位中提取位的优点。缺点是该数组将占用 8 倍的内存空间，这意味着不仅浪费空间，而且在您遍历数组以执行计数时还会推送更多数据。

标准数组查找和 BitArray 查找之间的区别如下：
数组：

  1. 偏移量 = 索引 * 索引大小
  2. 在位置+偏移处获取内存并保存到值

位数组：

  1. 索引 = 索引/索引大小
  2. 偏移量 = 索引 * 索引大小
  3. 在位置+偏移处获取内存并保存到值
  4. 位置 = 索引%indexSize
  5. 移位值位置位
  6. 价值 = 价值和 1

除了#2 for Arrays 和#3 之外，这些命令中的大多数都需要 1 个处理器周期才能完成。一些命令可以使用 x86/x64 处理器组合成 1 个命令，但可能不适用于 ARM，因为它使用的指令集减少了。
两者中哪一个（阵列或位阵列）性能更好取决于您的平台（处理器速度、处理器指令、处理器缓存大小、处理器缓存速度、系统内存量 (Ram)、系统内存速度 (CAS)、处理器和 RAM 之间的连接）以及要计算的索引的分布（是最常聚集的交叉点还是随机分布的）。

总而言之：您可能会找到一种使其更快的方法，但您的解决方案是使用 .NET 中的每个布尔模型为您的数据集获得的最快解决方案。

编辑：确保您正在访问要按顺序计算的索引。如果您按顺序访问索引 200、5、150、151、311、6，那么您将增加缓存未命中的数量，从而导致花费更多时间等待从 RAM 中检索值。

于 2012-04-11T22:22:05.397 回答