c# bitarray index of positive bits

If you can swap out the BitArray from the BCL in favour of a "roll your own", you can do better than that. Here's a few things you can do:

1. Skip chunks of 64 that have no bits set
2. For chunks of 64 that do have bits, only enumerate the 1-bits instead of all bits using x & (x - 1) and your favourite fast 2log found here (using the naive 64-step method won't give any kind of speedup)
3. Keep an extra bitarray which stores, for each 64bit chunk, whether it is nonzero. Apply the technique from bullet 2 to that bitarray to skip whole ranges of zero's in one go.
4. Apply bullet 3 recursively for gigantic bitarrays

All four of these only help if the bitarray is expected to be sparse, and the worst case is still O(n) if it isn't sparse. If bullet 3 is applied until the top is a single ulong then it can in O(1) determine whether the entire bitarray is empty or not.

If you are able to get a int array underlying the BitArray, this should provide much better performance:

Assuming you don't know the number of bits that are set:

public static int[] GetIndexesForPositives()
{
    var idIndexes = new List<int>();
    System.Reflection.FieldInfo field = data.GetType().GetField("m_array", System.Reflection.BindingFlags.NonPublic | System.Reflection.BindingFlags.Instance);
    int[] values = field.GetValue(data) as int[];

    for (var i = 0; i < values.Length; i++)
    {
        int _i = values[i];
        if (_i != 0)
        {
            for (var j = 0; j < 32; j++)
            {
                if ((_i & (1 << j)) != 0)
                {
                    idIndexes.Add(i * 32 + j);
                }
            }
        }
    }
    return idIndexes.ToArray();
}

If you do know the number of bits that are set you can do this instead:

public static int[] GetIndexesForPositives(int length)
{
    var idIndexes = new int[length];
    var idx = 0;
    System.Reflection.FieldInfo field = data.GetType().GetField("m_array", System.Reflection.BindingFlags.NonPublic | System.Reflection.BindingFlags.Instance);
    int[] values = field.GetValue(data) as int[];

    for (var i = 0; i < values.Length; i++)
    {
        int _i = values[i];
        if (_i != 0)
        {
            for (var j = 0; j < 32; j++)
            {
                if ((_i & (1 << j)) != 0)
                {
                    idIndexes[idx++] = i * 32 + j;
                }
            }
        }
}

My tests have these two working faster than your method, even the one that doesn't know how large the return array will be in the first place.

My results tested using a random BitArray of 50million records:

1) 25001063 records found in 50000000, took 1415.5752ms
2) 25001063 records found in 50000000, took 1099.67ms
3) 25001063 records found in 50000000, took 1045.6862ms
4) 25001063 records found in 50000000, took 745.7762ms"

1) is your code but using an arraylist instead of using some `GetPositiveCount` to get the output length.
2) is your code
3) is my (revised) first example
4) is my (revised) second example

edit: furthermore it is worth pointing out that this is a problem that could really benefit from being made multi-threaded. Break the ByteArray up into 4 parts and there you have 4 threads that could run checking the data at once.

Edit: I know this is already accepted but here's another bit you can do to improve performance if you know that most of the time your list will be very sparse:

for (var j = 0; j < 32; j++)
{
     if (_i == 0)
         break;
     if ((_i & (1)) != 0)
     {
         idIndexes.Add(i * 32 + j);
     }
     _i = _i >> 1;
 }

it is slightly slower when the list is >40% or more populated however if you know the list is always going to be 10% 1s and 90% 0s then this will run even faster for you.

I would do something like this:

public int[] GetIndexesForPositives()
{
    var idIndexes = new LinkedList<int>();

    for (var i = 0; i < Length; i++)
        {
            if (Get(i))
            {
                idIndexes.Add(i);
            }
        }
    return idIndexes.ToArray();
}

If this is still not acceptable (because you walk the indizes again while doing ToArray) just use the same size for your result array and return the length of found indizes:

public int GetIndexesForPositives(out int[] indizes)
{
    indizes = new int[Length];
    var idI = 0;

    for (var i = 0; i < Length; i++)
        {
            if (Get(i))
            {
                indizes[idI++] = i;
            }
        }
    return idI;
}

Depending on if you really need all the indizes or only parts you might even consider something like this (but it will be less performant if you need every part - do some profiling yourself please):

public IEnumerable<int> GetIndexesForPositives()
{
    for (var i = 0; i < Length; i++)
        {
            if (Get(i))
            {
                yield return i;
            }
        }
}

this is assuming that your Get(i) is doing it's job and that your array is immutable.