Your check
(a & b) == b; // check whether b is a subset of a
checks whether b
is a subset of a
, or equivalent, whether a
contains/includes b
. Note that you are creating one temporary followed by the break-early operator==
.
This is equivalent to checking whether the difference of b
and a
is empty (note the order!)
(b & ~a).none();
This will be equally fast: a temporary followed by a break-early .none()
Given the interface of std::bitset
, this is as fast you can get. The problem with std::bitset
is that all its bitwise members (&
, |
, ^
and ~
loop over every word. The early termination operations like none()
, any()
, ==
or <
, cannot be intertwined with them. This is because std::bitset
does not expose the underyling word storage so you cannot perform the iteration yourself.
However, if you would write your own bitset class, you could write a special-purpose includes()
algorithm that loops over each of the words, doing the &
until you break-early
// test whether this includes other
bool YourBitSet::includes(YourBitSet const& other) const {
for (auto i = 0; i < NumWords; ++i)
if ((other.word[i] & ~(this->word[i])) != 0)
return false;
return true;
}
A similar algorithm missing from std::bitset
would be intersects()
, to efficiently test (a & b) != 0
. Currently you have to first do bitwise and, and then the test for zero, whereas that would be more efficiently done in one loop. If std::bitset
ever gets updated, it would be nice if they include includes()
and intersects()
primitives.