子集的高效检查

Question

给定两个长度分别为 'n' 的位集对象 'B1' 和 'B2'。说 'B2' 中设置的所有位是否也在 'B1' 中的有效方法是什么？

示例：

B1 = 110111
B2_bad = 011001
B2_good = 100001

所以，'B1' 和 'B2_good' 不错，但 'B1' 和 'B2_bad' 不好？

Answer 1

嗯，我想下面这两种方法可能会有所帮助。您可能需要对它们进行基准测试，因为哪个更快。

std::bitset<6> B1 (std::string("110111"));
std::bitset<6> B2_bad (std::string("011001"));
std::bitset<6> B2_good (std::string("100001"));
    //////////////One way/////////////////////////
    if ( (~B1 &= (B2_bad)).any()) std::cout << "No" << std::endl;
    else std::cout << "Yes" << std::endl;

    if ( (~B1 &= (B2_good)).any()) std::cout << "No" << std::endl;
    else std::cout << "Yes" << std::endl;

    ///////////////Second way//////////////////
    int i =0;
    for (i = 0; i < B1.size(); ++i) if (B2_bad[i] == 1 && B1[i] == 0) break;
    if (i == B1.size()) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;

    for (i = 0; i < B1.size(); ++i) if (B2_good[i] == 1 && B1[i] == 0) break;
    if (i == B1.size()) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;`

可能比我更熟练的人可以评论他们的表现。但我最好的猜测是第一种方法利用了应该提供最佳性能的库函数，但是如果你的大多数查询都有 'Result NO' 并且 B1-B2 不同意前面的一个位，那么第二种方法可能会更好运行。因为，所涉及的库函数具有最差的运行时复杂度 O(n)。

子集的高效检查

Efficient checking for Subset

bitarray