如何获取 BitArray 中的最后一个设置位？

Question

在 BitArray 中获取最后设置位的有效（快速）方法是什么。（LINQ 或简单的后向 for 循环对于大位图来说不是很快。我需要快）BitArray 我看到下一个算法：通过 BitArray 内部 int 数组数据返回并使用一些编译器 Intrinsic Like C++ _BitScanReverse（不知道 C# 中的模拟）。

Answer 1

如果您想要最后设置位的索引，您可以在 C# 6 中执行此操作。

int? index = array.Select((b,i)=>{Index = i, Value = b})
                  .LastOrDefault(x => x.Value)
                  ?.Index;

否则你必须做这样的事情

var last = array.Select((b,i)=>{Index = i, Value = b})
                  .LastOrDefault(x => x.Value);
int? index = last == null ? (int?)null : last.Index;

无论哪种方式，如果所有位都为零，index 将是 null。

Answer 2

除了从最后一位迭代到第一位，并询问是否已设置，我不相信它可以做任何事情。它可以通过类似的方式完成：

BitArray bits = ...;
int lastSet = Enumerable.Range(1, bits.Length)
                  .Select(i => bits.Length - i)
                  .Where(i => bits[i])
                  .DefaultIfEmpty(-1)
                  .First();

那应该 return 最后一位设置，或者如果 none 是 -1。还没有亲自测试过，所以可能需要一些调整。

希望对您有所帮助。

Answer 3

"normal"解决方案：

    static long FindLastSetBit(BitArray array)
    {
        for (int i = array.Length - 1; i >= 0; i--)
        {
            if (array[i])
            {
                return i;
            }
        }

        return -1;
    }

反射解决方案（注意-依赖于BitArray的实现）：

    static long FindLastSetBitReflection(BitArray array)
    {
        int[] intArray = (int[])array.GetType().GetField("m_array", System.Reflection.BindingFlags.Instance | System.Reflection.BindingFlags.NonPublic).GetValue(array);

        for (var i = intArray.Length - 1; i >= 0; i--)
        {
            var b = intArray[i];
            if (b != 0)
            {
                var pos = (i << 5) + 31;
                for (int bit = 31; bit >= 0; bit--)
                {
                    if ((b & (1 << bit)) != 0)
                        return pos;

                    pos--;
                }

                return pos;
            }
        }

        return -1;
    }

反射解决方案对我来说在大型 BitArrays 上快 50-100 倍（在非常小的情况下，反射的开销将开始出现）。在我的机器上每兆字节大约需要 0.2 毫秒。

主要是if (b != 0)一次检查32位。当找到正确的单词时，检查特定位的内部循环只运行一次。

已编辑：删除了不安全的代码，因为我意识到它几乎没有任何好处，它只是避免了数组边界检查，而且由于代码已经如此之快，所以这无关紧要。作为记录，不安全的解决方案（对我来说快约 30%）：

    static unsafe long FindLastSetBitUnsafe(BitArray array)
    {
        int[] intArray = (int[])array.GetType().GetField("m_array", System.Reflection.BindingFlags.Instance | System.Reflection.BindingFlags.NonPublic).GetValue(array);

        fixed (int* buffer = intArray)
        {
            for (var i = intArray.Length - 1; i >= 0; i--)
            {
                var b = buffer[i];
                if (b != 0)
                {
                    var pos = (i << 5) + 31;
                    for (int bit = 31; bit >= 0; bit--)
                    {
                        if ((b & (1 << bit)) != 0)
                            return pos;

                        pos--;
                    }

                    return pos;
                }
            }
        }

        return -1;
    }

如何获取 BitArray 中的最后一个设置位？

How to get last set bit in BitArray?

.net

c#

bit-manipulation