Is there a generic (type-safe) BitArray in .NET?

Question

Is there a generic BitArray in .NET? I only found the non-generic one.

Can there be a generic BitArray? (i.e. would it be reasonable?)

---

Edit:

Maybe I should have said type-safe not generic.

Basically when you enumerate the type as object, should it not be int or bool? Or one of them provided in another member enumerator?

---

Example:

foreach (bool bit in myBitArray)
{

}

---

Edit:

I just checked the enumerator of the BitArray class, but everything returns an object except .Current property:

public virtual object Current

Answer 1

What would be an example of a generic type argument that you would pass to BitArray<T> if it existed?

BitArray is defined as:

Manages a compact array of bit values, which are represented as Booleans, where true indicates that the bit is on (1) and false indicates the bit is off (0).

This type is an optimized array of bits, nothing else. There is no value to making it generic as there are no members that could be factored out of the type. Any specialized collection like this one can be though of as a closed constructed type of some parent generic collection. In other words, BitArray is kind of like List<Boolean> (with many useful methods added of course).

Edit: Yes, this type implements IEnumerable and does not implement IEnumerable<T> - this is most likely due to the fact that it is an older type and was not updated. Remember that you can use Enumerable.Cast<TResult> to work around this very problem:

yourBitArray.Cast<bool>();

Answer 2

What possible reason would you have for a generic version? What type could a BitArray possibly use beside bits, or booleans which are turned into bits as the the case is?

Updated: It is type safe. If you are doing a foreach(var bit in bitArray) then bit will appear as an object, but you can just as easily do foreach(bool bit in bitArray), this happens for all collections that implement IEnumerable and not IEnumerable<T>.

Answer 3

BitArray is a specialized collection class from the NET 1.x era. It is quite type-safe as long as you use ba.Set(int, bool) and the indexer property.

What is 'not typesafe' is the enumeration, BitArray implements IEnumerable but not IEnumerable< bool>. So Joan is right, using foreach() involves casting from object to bool.

But is that a real problem? The elements in a BitArray are booleans, and only meaningful when combined with their position. Note that BitArray does not have an Add() method, just a Set(i, true).

So the simple answer is: don't use foreach(), or anything else based on IEnumerable. It only produces a stream of true/false values that can hardly be useful.

In the following snippet the BitArray is perfectly type-safe and efficient:

BitArray isEven = ...;
for(int i = 0; i < isEven.Count; i++) 
{
   isEven.Set(i, i % 2 == 0);
}

Answer 4

You can iterate BitArray without boxing or converting it to List<bool>:

public static IEnumerable<bool> GetTypeSafeEnumerator(this BitArray ba) {
    for (int i = 0; i < ba.Length; i++)
        yield return ba[i];
}

This should be faster than converting to list and certainly take much less memory.

Of course, it is still going to be slower than a plain old for loop, and if you really need performance, you should use

for (int i = 0; i < ba.Length; i++) {
    bool b = ba[i];
    ...
}

Benchmark using MiniBench:

public static class Class1 {
    private const int N = 10000;
    private const int M = 100;

    public static void Main() {
        var bitArray = new BitArray(N);

        var results1 = new TestSuite<BitArray, int>(
            "Different looping methods")
            .Plus(PlainFor, "Plain for loop")
            .Plus(ForEachBool, "foreach(bool bit in bitArray)")
            .Plus(CastBool, "foreach(bool bit in bitArray.Cast<bool>)")
            .Plus(TypeSafeEnumerator, "foreach(bool bit in bitArray.GetTypeSafeEnumerator())")
            .Plus(UseToList, "foreach(bool bit in bitArray.ToList())")
            .RunTests(bitArray, 0);

        results1.Display(ResultColumns.All, results1.FindBest());

        var results2 = new TestSuite<BitArray, int>(
            "Avoiding repeated conversions")
            .Plus(PlainFor1, "Plain for loop")
            .Plus(CastBool1, "foreach(bool bit in bitArray.Cast<bool>)")
            .Plus(TypeSafeEnumerator1, "foreach(bool bit in bitArray.GetTypeSafeEnumerator())")
            .Plus(UseToList1, "foreach(bool bit in bitArray.ToList())")
            .RunTests(bitArray, 0);

        results2.Display(ResultColumns.All, results2.FindBest());
    }

    private static int PlainFor1(BitArray arg) {
        int j = 0;
        for (int k = 0; k < M; k++) {
            for (int i = 0; i < arg.Length; i++) {
                j += arg[i] ? 1 : 0;
            }
        }
        return j;
    }

    private static int CastBool1(BitArray arg) {
        int j = 0;
        var ba = arg.Cast<bool>();
        for (int k = 0; k < M; k++) {
            foreach (bool b in ba) {
                j += b ? 1 : 0;
            }
        }
        return j;
    }

    private static int TypeSafeEnumerator1(BitArray arg) {
        int j = 0;
        var ba = arg.GetTypeSafeEnumerator();
        for (int k = 0; k < M; k++) {
            foreach (bool b in ba) {
                j += b ? 1 : 0;
            }
        }
        return j;
    }

    private static int UseToList1(BitArray arg) {
        int j = 0;
        var ba = arg.ToList();
        for (int k = 0; k < M; k++) {
            foreach (bool b in ba) {
                j += b ? 1 : 0;
            }
        }
        return j;
    }

    private static int PlainFor(BitArray arg) {
        int j = 0;
        for (int i = 0; i < arg.Length; i++) {
            j += arg[i] ? 1 : 0;
        }
        return j;
    }

    private static int ForEachBool(BitArray arg) {
        int j = 0;
        foreach (bool b in arg) {
            j += b ? 1 : 0;                
        }
        return j;
    }

    private static int CastBool(BitArray arg) {
        int j = 0;
        foreach (bool b in arg.Cast<bool>()) {
            j += b ? 1 : 0;
        }
        return j;
    }

    private static int TypeSafeEnumerator(BitArray arg) {
        int j = 0;
        foreach (bool b in arg.GetTypeSafeEnumerator()) {
            j += b ? 1 : 0;
        }
        return j;
    }

    private static int UseToList(BitArray arg) {
        int j = 0;
        foreach (bool b in arg.ToList()) {
            j += b ? 1 : 0;
        }
        return j;
    }

    public static List<bool> ToList(this BitArray ba) {
        List<bool> l = new List<bool>(ba.Count);
        for (int i = 0; i < ba.Count; i++) {
            l.Add(ba[i]);
        }
        return l;
    }

    public static IEnumerable<bool> GetTypeSafeEnumerator(this BitArray ba) {
        for (int i = 0; i < ba.Length; i++)
            yield return ba[i];
    }
}

Results (name, number of iterations, total duration, score (high score is bad)):

============ Different looping methods ============
Plain for loop                                        456899 0:28.087 1,00
foreach(bool bit in bitArray)                         135799 0:29.188 3,50
foreach(bool bit in bitArray.Cast<bool>)               81948 0:33.183 6,59
foreach(bool bit in bitArray.GetTypeSafeEnumerator()) 179956 0:27.508 2,49
foreach(bool bit in bitArray.ToList())                161883 0:27.793 2,79

============ Avoiding repeated conversions ============
Plain for loop                                        5381 0:33.247 1,00
foreach(bool bit in bitArray.Cast<bool>)               745 0:28.273 6,14
foreach(bool bit in bitArray.GetTypeSafeEnumerator()) 2304 0:27.457 1,93
foreach(bool bit in bitArray.ToList())                4603 0:30.583 1,08