Simplify (A & B) && !(A & C)

Question

A, B, and C are variables of some unsigned integral type. Conceptually, A is a test vector, B is a bitmask of 'required' bits (at least one corresponding bit in A must be set) and C is a bitmask of 'prohibited' bits (no corresponding bit in A may be set). Since we're mixing bitwise and logical operators, the otherwise natural-seeming solution of

A & B & ~C

is incorrect. Rather the title expression is equivalent to the pseudocode

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

where a0, etc. represent individual bits (and n is index of the highest bit). I don't see how to rearrange this effectively and pull out the corresponding code but nonetheless, is there a clever way, maybe with ^, to simplify the expression in the title?

Edit: Prompted by @huseyintugrulbuyukisik's question I note that we can assume (B & C) == 0, but I don't know if that helps.

Edit 2: Results: It depends on how good branch prediction is!

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

Version 1:

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

Version 2:

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

These are representative values (in reality I ran each test multiple time). g++ 4.8.4, default optimization. I got version-2-like results with only 4 bits set in B. However, my use case is still closer to version 1 so I think @DougCurrie's answer is an improvement.

Answer 1

!(A & B) must be zero

A & C must be zero

so

(!(A & B)) | (A & C) must be zero

This saves the branch associated with &&; some compilers can optimize ! to be branchless as well.

Answer 2

Admittedly, I cannot find a mathematical proof of it, but I'm leading myself to think that your expression cannot be further simplified, at least not simplified into purely bit-wise logic.

The reason being that the two tests (A & B and !(A & C)) are tests of two different kinds: The first tests whether any bits are so-or-so (1, in this case), while the other tests whether all bits are so-or-so (0, in this case).

In all cases, to convert a final bit-array to a single Boolean value, you need some operation that coalesces all bits into one bit (such as ! or the implicit != 0 of the if clause). For the reason outlined above, you need two different such coalescing operators. It is my interpretation of your question that you, by "simplifying" the expression, mean turning it into all-bitwise operations, meaning only using the one coalescing operator implicit in the if clause – which if I'm correct, is not enough.

In the end, I might perhaps add, that even if the expression can be simplified by some standard, I'm not sure it should. The current form of it does after all express the actual intention very well: "These, but not those".