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 (
beginandend).
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.