如何在位数组中获取最后一个设置位

Question

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

Answer 1

"正常"解决方案：

    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;
    }

反射解决方案对我来说在大BitArray上快 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;
    }

Answer 2

如果你想要最后一个设置位的索引，你可以在 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 3

我不相信它能做任何事情，除了从最后一位迭代到第一位，并在设置时询问每一个。它可以通过以下方式完成：

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

这应该返回最后一个位集，如果没有，则返回 -1。我自己还没有测试过，所以可能需要一些调整。

希望对您有所帮助。