时间戳

首页 > 解决方案 > 如何比较两个 BitArray 并返回第二个数组的差异索引

c# - 如何比较两个 BitArray 并返回第二个数组的差异索引

问题描述

我有两个BitArray对象。并想检查值是否与第一个相比发生变化，BitArray然后返回第二个数组的索引。我试过循环每一位，但它需要太多时间，即：我有以下两个对象：

BitArray a = new BitArray{true,false,true};
BitArray b = new BitArray{false,false,false};

并希望返回结果 0,2，因为 BitArray b 与 BitArray a 相比有两个变化。

标签： c#asp.net

解决方案

如果性能是您的主要目标，那么您将不会使用BitArray; 这种抽象根本不是最优的。您可能想要放入自己的超大整数缓冲区，在每个缓冲区上使用“xor”来计算增量，然后对增量使用位运算（xor 结果）。

但是，在 .NET Core 3 上，您可以直接访问 x86 指令集，同时为我们提供 SIMD 和 popcnt；我们可以在这里很好地结合这些东西，使用 SIMD XOR，然后在增量上使用 popcnt（没有 SIMD popcnt AFAIK，但我们可以手动展开）：

        // make sure these are multiples of 128-bit, so: 4; otherwise
        // you'll have to deal with the leftover bits manually
        uint[] left = new uint[16], right = new uint[16];
        Random rand = new Random(12345);
        for (int i = 0; i < left.Length; i++)
            left[i] = (uint)rand.Next();
        for (int i = 0; i < right.Length; i++)
            right[i] = (uint)rand.Next();

        // real(ish) code starts here

        // loop over our `uint[]` as spans of Vector128<uint>
        var lspan = MemoryMarshal.Cast<uint, Vector128<uint>>(left);
        var rspan = MemoryMarshal.Cast<uint, Vector128<uint>>(right);
        uint count = 0;
        for(int i = 0; i < lspan.Length; i++)
        {
            // compute the bit delta
            var delta = Popcnt.Xor(lspan[i], rspan[i]);
            // Vector128 is 4xUInt32, so: unroll
            count += Popcnt.PopCount(delta.GetElement(0))
                + Popcnt.PopCount(delta.GetElement(1))
                + Popcnt.PopCount(delta.GetElement(2))
                + Popcnt.PopCount(delta.GetElement(3));
        }
        Console.WriteLine(count);

您还可以对 xor 使用更通用Vector<T>的（它也适用于 .NET Framework，并且可以处理比 128 更宽的大小），但是：没有直接的 popcount；例子：

        // loop over our `uint[]` as spans of Vector<uint>
        var lspan = MemoryMarshal.Cast<uint, Vector<uint>>(left);
        var rspan = MemoryMarshal.Cast<uint, Vector<uint>>(right);
        for(int i = 0; i < lspan.Length; i++)
        {
            // compute the bit delta
            var delta = lspan[i] ^ rspan[i];

            // work with delta...
        }

这个 ( Vector<T>) 通常会给你 256 甚至 512 的 SIMD 宽度。

推荐阅读