c++ - 检查一个 bitset 是否包含另一个 bitset 的所有值

Question

我正在尝试创建一个实体/组件系统，自动匹配合适的实体和合适的系统。我正在使用 std::bitset和 RTTI自动为每个组件类型分配一个位值。

系统定义如下:MovementSystem : System<Position, Velocity> .

MovementSystem ，在此示例中，接受同时具有 Position 的任何实体和 Velocity组件(以及任何其他组件)。

为了检查实体是否合适，我将系统的位集与实体的位集进行比较。

// 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

到目前为止，我的解决方案是:

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

它似乎 可以工作，但我是在白板上乱写位集后发现的。这是正确的吗？还能再改进吗？ (在我的游戏中实体会被创建和销毁很多次，所以性能非常重要!)

---

代码是 here如果需要(不应该)，但几乎不可能阅读。

Answer 1

您的支票

(a & b) == b;     // check whether b is a subset of a

检查是否b是 a 的子集, 或等价物，无论是 a包含/包含 b .请注意，您正在创建一个临时文件，然后是 break-early operator== .

这相当于检查b是否不同和 a为空(注意顺序!)

(b & ~a).none(); 

这将同样快:一个临时的，然后是一个提前休息 .none()

给定 std::bitset 的接口(interface)，这是您可以获得的最快速度。 std::bitset 的问题是它的所有按位成员( & ， | ， ^ 和 ~ 循环遍历每个单词。像 none() ， any() ， == 或 < 这样的提前终止操作不能与它们交织在一起。这是因为 std::bitset 没有公开底层词存储，因此您无法自己执行迭代。

但是，如果您要编写自己的 bitset 类，则可以编写一个特殊用途的 includes()循环遍历每个单词的算法，执行 &直到你早点休息

// 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;
}

std::bitset 中缺少类似的算法将是 intersects() , 有效地测试 (a & b) != 0 .目前，您必须首先进行按位与，然后进行零测试，而这在一个循环中完成会更有效。如果std::bitset永远得到更新，如果它们包括 includes() 就好了和 intersects()原语。