How to get last set bit in BitArray?

Question

What is effective(fast) way to get last set bit in BitArray. (LINQ or simple backward for loop isn't very fast for large bitmaps. And I need fast) BitArray I see next algorithm: go back through BitArray internal int array data and use some compiler Intrinsic Like C++ _BitScanReverse( don't know analog in C#).

Answer 1

The "normal" solution:

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

        return -1;
    }

The reflection solution (note - relies on implementation of 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;
    }

The reflection solution is 50-100x faster for me on large BitArrays (on very small ones the overhead of reflection will start to appear). It takes about 0.2 ms per megabyte on my machine.

The main thing is that if (b != 0) checks 32 bits at once. The inner loop which checks specific bits only runs once, when the correct word is found.

Edited: unsafe code removed because I realized almost nothing is gained by it, it only avoids the array boundary check and as the code is so fast already it doesn't matter that much. For the record, unsafe solution (~30% faster for me):

    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

If you want the index of that last set bit you can do this in C# 6.

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

Otherwise you have to do something like this

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

Either way the index will be null if all the bits are zero.

Answer 3

I don't believe there is anything it can be done, other than iterate from last to first bit, and ask for each one if it is set. It could be done with something like:

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

That should return the last bit set, or -1 if none is. Haven't tested it myself, so it may need some adjustment.

Hope it helps.