简化(A&B)&&!(A&C)

Question

A,B和C是某些无符号整数类型的变量.从概念上讲,A是测试向量,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的结果,只有4位设置B.但是,我的用例仍然接近版本1,所以我认为@ DougCurrie的答案是一个改进.

Answer 1

!(A & B) 必须为零

A & C 必须为零

所以

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

这样可以节省与之相关的分支&&; 一些编译器也可以优化!为无分支.