Skip to content

util: add BitSet

Placeholder Pieter Wuille requested to merge github/fork/sipa/202405_bitset into master

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 and end).

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.

Merge request reports

Loading