Упростить (A & B) &&! (A & C) - программирование

A, B и C являются переменными некоторого неподписанного интегрального типа. Понятно, что A - тестовый вектор, B - битмаска "обязательных" бит (должен быть установлен как минимум один соответствующий бит в A), а C - битмаска "запрещенных" битов (никакой соответствующий бит в не может быть установлен). Поскольку мы смешиваем побитовые и логические операторы, в противном случае естественно-кажущееся решение

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 является улучшением.

Ответ 2

По общему признанию, я не могу найти математическое доказательство этого, но я заставляю себя думать, что ваше выражение не может быть упрощено, по крайней мере, не упрощено в чисто битовую логику.

Причина состоит в том, что два теста (A & B и !(A & C)) - это тесты двух разных типов: первые проверяют, являются ли какие-либо биты такими-то (в данном случае - 1), а остальные тесты все ли бит-то или так (0, в этом случае).

Во всех случаях для преобразования конечного битового массива в одно булево значение требуется некоторая операция, которая объединяет все биты в один бит (например, ! или неявный != 0 в предложении if), По причине, описанной выше, вам нужны два разных таких оператора коалесценции. Моя интерпретация вашего вопроса о том, что вы, "упростив" выражение, означаете превращение его во всеподобные операции, что означает только использование одного оператора коалесцирования, неявного в предложении if, который, если я прав, не является достаточно.

В конце концов, я мог бы добавить, что даже если выражение может быть упрощено некоторым стандартом, я не уверен, что это должно произойти. Текущая форма его в конце концов очень хорошо выражает фактическое намерение: "Эти, но не те".

Ответ 1

Ответ 2