c++ - 简化 (A & B) && !(A & C)

Question

A、B 和 C 是一些无符号整数类型的变量。从概念上讲，A 是一个测试 vector ，B 是“必需”位的位掩码(必须设置 A 中的至少一个对应位)，C 是“禁止”位的位掩码(A 中的对应位不能设置)。由于我们混合了按位和逻辑运算符，否则看起来很自然的解决方案

A & B & ~C

不正确。而是标题表达式等价于伪代码

((a0 & b0) | ... | (an & bn)) & (~(a0 & c0) & ... & ~(an & cn))

其中 a0 等表示单个位(而 n 是最高位的索引)。我不知道如何有效地重新排列并提取相应的代码，但是，有没有一种聪明的方法，也许是 ^，来简化标题中的表达？

编辑:在@huseyintugrulbuyukisik 的问题提示下，我注意到我们可以假设 (B & C) == 0，但我不知道这是否有帮助。

编辑 2: 结果:这取决于分支预测的好坏!

#include <chrono>
#include <cmath>
#include <iostream>
#include <vector>

using UINT = unsigned int;
int main(void)
{
    const auto one = UINT(1);
    const UINT B = (one << 9); // Version 1
//  const UINT B = (one << 31) - 1;  // Version 2
    const UINT C = (one << 5) | (one << 15) | (one << 25);

    const size_t N = 1024 * 1024;
    std::vector<UINT> vecA(N);
    for (size_t i = 0; i < N; ++i)
        vecA[i] = (UINT)rand();

    int ct = 0; //To avoid compiler optimizations
    auto tstart = std::chrono::steady_clock::now();
    for (size_t i = 0; i < N; ++i)
    {
        const UINT A = vecA[i];
        if ((A & B) && !(A & C))
            ++ct;
    }
    auto tend = std::chrono::steady_clock::now();
    auto tdur = std::chrono::duration_cast<std::chrono::milliseconds>(tend - tstart).count();
    std::cout << ct << ", " << tdur << "ms" << std::endl;

    ct = 0;
    tstart = std::chrono::steady_clock::now();
    for (size_t i = 0; i < N; ++i)
    {
        const UINT A = vecA[i];
        if (!((!(A & B)) | (A & C)))
            ++ct;
    }
    tend = std::chrono::steady_clock::now();
    tdur = std::chrono::duration_cast<std::chrono::milliseconds>(tend - tstart).count();
    std::cout << ct << ", " << tdur << "ms" << std::endl;

    return 0;
}

版本 1:

$ ./ops_test 
    65578, 8ms
    65578, 3ms

版本 2:

$ ./ops_test
    130967, 4ms
    130967, 4ms

这些是代表值(实际上我多次运行每个测试)。 g++ 4.8.4，默认优化。我得到了类似版本 2 的结果，在 B 中只设置了 4 位。但是，我的用例仍然更接近版本 1，所以我认为 @DougCurrie 的回答是一种改进。

Answer 1

!(A & B) 必须为零

A & C 必须为零

所以

(!(A & B)) | (A & C) 必须为零

这会保存与 && 关联的分支；一些编译器也可以将 ! 优化为无分支。