util: add BitSet
Extracted from #30126.
This introduces the BitSet
data structure, inspired by std::bitset
, but with a few features that cannot be implemented on top without efficiency loss:
- Finding the first set bit (
First
) - Finding the last set bit (
Last
) - Iterating over all set bits (
begin
andend
).
And a few other operators/member functions that help readability for #30126:
-
operator-
for set subtraction -
Overlaps()
for testing whether intersection is non-empty -
IsSupersetOf()
for testing (non-strict) supersetness -
IsSubsetOf()
for testing (non-strict) subsetness -
Fill()
to construct a set with all numbers from 0 to n-1, inclusive -
Singleton()
to construct a set with one specific element.
Everything is tested through a simulation-based fuzz test that compares the behavior with normal std::bitset
equivalent operations.