Check if a bitset contains all values of another bitset

Question

I'm trying to create an entity/component system that automatically matches suitable entities suitable systems. I'm using std::bitset and RTTI to automatically assign a bit value to every component type.

A system is defined like this: MovementSystem : System<Position, Velocity>.

MovementSystem, in this example, accepts any entity that has both the Position and the Velocity components (and any other component).

To check if an entity is suitable, I compare the system's bitset to the entity's bitset.

// Let's assume there are max 4 components

1          1          0         1        // Entity bitset
^          ^                    ^
Position   Velocity             OtherB

1          1          0         0        // Suitable example system bitset
^          ^
Position   Velocity

1          1          1         0        // Unsuitable example system bitset
^          ^          ^                  // Entity does not have OtherA!
Position   Velocity   OtherA

So far, my solution is this one:

if(entityBitset & systemBitset) == systemBitset)) { /* entity is suitable! */ }

It seems to work, but I found it after doodling bitsets on a whiteboard. Is it correct? Can it be improved any further? (Entities will be created and destroyed an immense amount of times in my games, so performance is very important!)

Code is here if needed (shouldn't be), but it's almost impossible to read.

I'm sorry but why would a built in stdlib function not work? — aaronman
– aaronman, Commented Oct 8, 2013 at 21:19
@SJuan76: I tried messing around with XOR but couldn't get it to work. Should I XOR the entity bitset with the system bitset or viceversa? And should I .all() or .any() the XOR result? — Vittorio Romeo
– Vittorio Romeo, Commented Oct 8, 2013 at 21:20

Gregory · Accepted Answer · 2020-08-26 11:11:30Z

7

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.

edited Aug 26, 2020 at 11:11

Gregory

731 silver badge8 bronze badges

answered Oct 8, 2013 at 21:22

TemplateRex

70.9k21 gold badges176 silver badges316 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Vittorio Romeo Over a year ago

I know it has an equality operator. My question is about the correctness of my solution and possible ways of improving it. In fact, I already use the equality operator in my solution: if(entityBitset & systemBitset) == systemBitset))

Vittorio Romeo Over a year ago

how is it the same? a=1110, b=1100 - a == b == false - (a & b) == b == true

Collectives™ on Stack Overflow

Check if a bitset contains all values of another bitset

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related