Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Check if a bitset contains all values of another bitset

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.

like image 334
Vittorio Romeo Avatar asked Oct 08 '13 21:10

Vittorio Romeo


People also ask

Which BitSet method tests whether all bits from BitSet are set or not?

Member functions Tests whether all bits from bitset are set or not.

Is BitSet faster than vector bool?

As bitset stores the same information in compressed manner the operation on bitset are faster than that of array and vector.

Is BitSet parameterized?

bitset set() function in C++ STL Parameter: The function accepts two parameters which are described below: index – this parameter specifies the position at which the bit has to be set. The parameter is an optional one.


1 Answers

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.

like image 187
TemplateRex Avatar answered Oct 29 '22 02:10

TemplateRex