高效檢查子集

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;` 

也許，比我更精通的人可以評論他們的表現。但我最好的猜測是第一種方法利用了應該提供最佳性能的庫函數，但是如果大多數查詢的結果爲「結果否」，並且B1-B2不會同意先前的一個位，那麼第二種方法可能會有更好的運行時。因爲所涉及的庫函數具有最差的運行時複雜度O（n）。