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

Question

A、B、C是某种无符号整数类型的变量。从概念上讲，A 是一个测试向量，B 是 'required' 位的位掩码（必须设置 A 中的至少一个对应位），C 是 'prohibited' 位的位掩码（A 中可能没有对应的位被设置）。由于我们混合了按位运算符和逻辑运算符，否则 natural-seeming

的解决方案

A & B & ~C

不正确。相反，标题表达式等同于伪代码

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

其中 a0 等代表各个位（而 n 是最高位的索引）。我不知道如何有效地 rear运行ge 并提取相应的代码，但是，有没有聪明的方法，也许用 ^ 来简化标题中的表达式？

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

编辑 2： 结果：这取决于 b运行ch 预测的好坏！

#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，默认优化。在 B 中仅设置了 4 位，我得到了类似版本 2 的结果。但是，我的用例仍然更接近版本 1，所以我认为 @DougCurrie 的回答是一个改进。

Answer 1

!(A & B) 必须为零

A & C 必须为零

所以

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

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

Answer 2

诚然，我找不到它的数学证明，但我引导自己认为你的表达式不能进一步简化，至少不能简化为纯位逻辑。

原因是这两个测试（A & B 和 !(A & C)）是两种不同类型的测试：第一个测试是否 any 位是这样的-or-so（1，在本例中），而另一个测试 all 位是否是 so-or-so（0，在本例中）。

在所有情况下，要将最终位数组转换为单个布尔值，您需要一些将所有位合并为一位的操作（例如 ! 或隐式 != 0 if 子句）。由于上述原因，您需要两个不同的此类合并运算符。我对你的问题的解释是，通过 "simplifying" 表达式，你的意思是将它变成全按位运算，这意味着只使用隐含在 if 子句中的一个合并运算符——如果我是正确，还不够。

最后，我可能会补充一点，即使表达式可以按某种标准进行简化，我也不确定是否应该这样做。它的当前形式毕竟很好地表达了实际意图："These, but not those".

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

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

c++

bit-manipulation

bit

bitmask