[API Proposal]: Add a BitArray.Contains method

[eiriktsarpalis]

Background and motivation

The BitArray class has been optimized to take advantage of hardware vectorization but it doesn't appear to have an efficient way to check if all flags within the array are either set or unset. The only suggested workaround I could find is to use Linq, i.e.

input.Cast<bool>().Contains(true);

which is far from optimal. The type could really benefit from a dedicated Contains implementation that uses vectorization.

API Proposal

namespace System.Collections;

public class BitArray
{
    public bool Contains(bool value);
}

API Usage

BitArray value;
BitArray mask;

value.And(mask).Contains(true);

Alternative Designs

No response

Risks

No response

[ghost]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and motivation

The BitArray class has been optimized to take advantage of hardware vectorization but it doesn't appear to have an efficient way to check if all flags within the array are set or unset. The only suggested workaround I could find is to use Linq, i.e.

input.Cast<bool>().Contains(true);

which is far from optimal. The type could really benefit from a dedicated Contains implementation that uses vectorization.

API Proposal

namespace System.Collections;

public class BitArray
{
    public bool Contains(bool value);
}

API Usage

BitArray value;
BitArray mask;

value.And(mask).Contains(true);

Alternative Designs

No response

Risks

No response

Author:	eiriktsarpalis
Assignees:	-
Labels:	api-suggestion, area-System.Collections
Milestone:	-

[eiriktsarpalis]

cc @krwq @stephentoub

[krwq]

I'd only recommend renaming Contains into AllBitsEqual, otherwise LGTM

[eiriktsarpalis]

Exposing an All method is equivalent to an Any/Contains method, since you can express it as

public AllBitsEqual(bool value) => !Contains(!value);

and vice versa. I feel Contains is more appropriate since this is a collection type but we could expose both variants.

[danmoseley]

I had the same expectation as @krwq. (not that means much)

What do other platforms/implementations name it?

Also, if I was translating an algorithm would I generally be thinking in terms of "are any bits set" (in which case Contains might be what I look for) or "are all bits false"?

[Tornhoof]

What do other platforms/implementations name it?

Java only implements IsEmpty() -> https://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html#isEmpty()

The other way round is not implemented, there is a discussion around that here: https://stackoverflow.com/questions/36308666/check-if-all-bits-in-bitset-are-set-to-true

[EgorBo]

Alternatives:

bool AllBitsSet { get; }
bool AllBitsUnset => !AllBitsSet;

[tannergooding]

Alternatives:

We wouldn't want this as a property. Properties are typically used for things that are "as cheap as a field read" and not for some potentially expensive algorithm that needs to check every element in the collection.

since you can express it as

While you can express it as this, I personally find comparing against a negative much harder to read/understand.

Not only can ! in if (!value.Contains(...)) get easily missed or misread, but you have to remember to read this as "if value does not contain" which while still not difficult, it is much clearer to me when it is if (value.DoesNotContain(...)) or if (value.AllBitsEqual(false)) (I've seen a good number of cases where dev's actually prefer if (cond == false) over if (!cond) due to the increased legibility, particularly for devs with reading troubles).

There are several other cases where I really wish we had both positive and negative APIs for binary cases (e.g. rather than IsLittleEndian and !IsLittleEndian it should've been IsLittleEndian and IsBigEndian) and since this is strictly a binary case (and always will be), I think it might be beneficial to expose it as such.

[eiriktsarpalis]

bool AllBitsUnset => !AllBitsSet;

There are several other cases where I really wish we had both positive and negative APIs for binary cases

FWIW AllBitsEqual is not a direct negation of Contains, one is expressible in terms of the other using De Morgan transformations. But I think that further proves the point that both existential and universal quantification are useful as first-class APIs here.

If we do ship both variants, I think the names should complement each other. Following existing .NET terminology that could look as follows:

public bool Any(bool value);
public bool All(bool value);

[danmoseley]

golang bit array doesn't seem to have this
rust has all() and none()
c++ bitset has all() and none()
Python has all() but for none, you have to negate any()
as noted above Java has isEmpty() but no easy way to check all set.

[sakno]

LeadingZeroCount() and/or TrailingZeroCount() can do the same but reusable for other purposes.

[tannergooding]

FWIW AllBitsEqual is not a direct negation of Contains

Right. I meant for the case people are requesting of array.All(true), we shouldn't need to represent it as !array.Contains(false) nor as !array.Contains(true) for array.All(false). It makes it immensely harder to read/etc.

Contains() (or Any()) is the "minimum" API and then there is a common/requested scenario of All() (but possibly with a better/longer name).

[danmoseley]

LeadingZeroCount() and/or TrailingZeroCount() can do the same but reusable for other purposes.

none() can be implemented as LeadingZeroCount() == Length; but how do you implement all() with those?

[sakno]

none() can be implemented as LeadingZeroCount() == Length; but how do you implement all() with those?

Yes, you're right. Probably, these methods are subjects to different proposal.

[tannergooding]

You'd need something like BitArray.PopCount(bitArray) == bitArray.Length).

But, that's also not strictly speaking the best or optimal implementation. Any/All/None can "early exit" where-as PopCount must process the entire array. Likewise LeadingZeroCount and TrailingZeroCount must process up to the first set bit from opposite sides of the array.

[bartonjs]

Video

• The proposed API and the proposed reason are logical opposites... "has all bits set" is !arr.Contains(false). So we came up with more direct questions.
• Count == 0 almost certainly wants both of these methods to return false.

namespace System.Collections
{
    public partial class BitArray
    {
        public bool HasAllSet();
        public bool HasAnySet();
    }
}

[eiriktsarpalis]

Count == 0 almost certainly wants both of these methods to return false.

Can you elaborate? Generally speaking "All" quantifiers return true on empty sets.

[bartonjs]

Heh, should've left it as my original "needs careful attention". Enumerable.All is the only "all" I know of in .NET, and it returns true on empty, so I guess true makes sense here, too.

The trouble is, with an empty set, All is the same as divide by zero to a mathematician: it means "this isn't answerable in a general context, but you might have a specific interpretation to fall back on" (so, had I been the author if it, the LINQ All it would have thrown on empty). (if (blockingIssues.HasAllSet()) { panic(); } clearly thinks that blockingIssues is non-empty)

[eiriktsarpalis]

See https://en.wikipedia.org/wiki/Universal_quantification#The_empty_set

By convention/definition, "forall" over empty is true and "exists" over empty is false. This makes sense if you look at inductive definitions of such quantifiers.

[stephentoub]

Count == 0 almost certainly wants both of these methods to return false.

Can you elaborate? Generally speaking "All" quantifiers return true on empty sets.

HasAllSet should return true for an empty collection. That's what Enumerable.All does, that's what List<T>.TrueForAll does, that's what Array.TrueForAll does, etc.