14 операций для всех масок.

Идея состоит в том, чтобы сначала отсортировать биты, используя min = x & y и max = x | y в качестве условного обмена. Это стоит 10 операций. Затем просто извлеките маски, что стоит 4 операции.

// Split in lower and upper half
var c1 = b1 & b2;
var c3 = b1 | b2;
var c2 = b3 & b4;
var c4 = b3 | b4;

// Sort within each half
var d1 = c1 & c2; // (b1 & b2) & (b3 & b4)
var d2 = c1 | c2; // (b1 & b2) | (b3 & b4)
var d3 = c3 & c4; // (b1 | b2) & (b3 | b4)
var d4 = c3 | c4; // (b1 | b2) | (b3 | b4)

// Sort middle
var e1 = d1;      // (b1 & b2) & (b3 & b4)
var e2 = d2 & d3; // ((b1 & b2) | (b3 & b4)) & ((b1 | b2) & (b3 | b4))
var e3 = d2 | d3; // ((b1 & b2) | (b3 & b4)) | ((b1 | b2) & (b3 | b4))
var e4 = d4;      // (b1 | b2) | (b3 | b4)

// Extract masks
var m4 = e1;      // (b1 & b2) & (b3 & b4)
var m3 = e2 ^ e1; // (((b1 & b2) | (b3 & b4)) & ((b1 | b2) & (b3 | b4))) ^ ((b1 & b2) & (b3 & b4))
var m2 = d3 ^ d2; // The same as e3 ^ e2, saves two operations if only m2 is required
var m1 = e4 ^ e3; // ((b1 | b2) | (b3 | b4)) ^ (((b1 & b2) | (b3 & b4)) | ((b1 | b2) & (b3 | b4)))
var m0 = ~e4;     // ~((b1 | b2) | (b3 | b4))

(Код написан на C#, но преобразовать его в C несложно.)

Если вы используете этот код, вычисляйте только некоторые маски и просто удаляйте строки, которые не влияют на результат (приличный компилятор должен делать это автоматически). Спектакль тоже не плохой:

m4: 3 операции
m3: 9 операций
m2: 7 операций
m1: 9 операций
m0: 4 операции

Начните с рассмотрения тривиального случая, когда битовые векторы имеют длину 1, т.е. это просто отдельные биты. Что вы действительно пытаетесь сделать, так это подсчитать количество этих установленных битов; тогда сопоставление счетчика с нужной вам битовой маской является относительно тривиальным упражнением.

Хитрость заключается в том, чтобы найти способ подсчитывать биты, используя только побитовые операции (т. е. И, ИЛИ, исключающее ИЛИ и НЕ), при этом каждый бит результирующего подсчета оказывается в отдельной переменной. Если вы можете это сделать, то вы можете сделать это одновременно для столько битов, сколько помещается в переменной. Этот метод известен как разбиение по битам или SIMD-внутри-регистра (SWAR).

Итак, что вы в основном пытаетесь сделать, это реализовать однобитный n-вход двоичный сумматор (где в вашем случае n = 4) с использованием побитовых логических операций. К счастью, эта проблема была тщательно изучена разработчиками цифровых схем.

Общее решение включает поддержку массива из k битовых векторов t₁, t₂ >, ..., t_k (где 2^k > n), сохраняя биты счетчиков и добавляя каждый входной битовый вектор к счетчикам по одному:

// initialize counts to zero
int count[k];
for (int j = 0; j < k; j++) count[j] = 0;

// count input bits
for (int i = 0; i < n; i++) {
    int carry = input[i];
    for (int j = 0; j < k && carry != 0; j++) {
        int temp = count[k];
        count[k] = carry ^ temp;
        carry = carry & temp;
    }
    // XXX: if carry != 0 here, some of the counts have overflowed
}

Затем вы можете извлечь свои битовые маски из подсчетов:

int masks[n+1];
for (int i = 0; i <= n; i++) {
    masks[n] = ~0;  // initialize all mask bits to 1
    for (int j = 0; j < k; j++) {
        masks[n] &= (n & (1 << j) ? count[j] : ~count[j]);
    }
}

Конечно, если количество входных данных небольшое и фиксированное, мы можем оптимизировать код для этого конкретного значения. Например, для n = 4 мы можем использовать:

// count input bits, store counts in bit-planes c0, c1, c2
int c0 = b0 ^ b1 ^ b2 ^ b3;
int c2 = b0 & b1 & b2 & b3;
int c1 = ((b0 & b1) | ((b0 ^ b1) & b2) | ((b0 ^ b1 ^ b2) & b3)) & ~c2;

// build masks from bit-planes
int m0 = ~c0 & ~c1 & ~c2;
int m1 =  c0 & ~c1 & ~c2;
int m2 = ~c0 &  c1 & ~c2;
int m3 =  c0 &  c1 & ~c2;
int m4 =  c2;  // XXX: count cannot be more than 4

Совершенно наивный компилятор сгенерировал бы из этого кода 23 операции И/ИЛИ/исключающее ИЛИ и 9 НЕ. Однако приличный компилятор должен кэшировать значения ~c0, ~c1 и ~c2, сохраняя до 6 операций НЕ, а также, возможно, некоторые повторяющиеся подвыражения, такие как b0 & b1, b0 ^ b1, b0 ^ b1 ^ b2, ~c1 & ~c2 и c1 & ~c2, сохраняя до 6 операций И/XOR, для всего 17 операций И/ИЛИ/исключающее ИЛИ плюс 3 операции НЕ = 20 операций, что довольно близко к решению Джонатана Ми с 19 операциями.

На самом деле, мы можем добиться большего, если поймем, что на самом деле нам не нужно вычислять c1, а вместо этого можно работать с c12 = c1 | c2. Мы также можем немного оптимизировать построение маски, отметив, что c2 нельзя установить, если c0 (или c1) равно:

// count input bits, store counts in bit-planes c0, (c1 = c12 & ~c2), c2
int c0 = b0 ^ b1 ^ b2 ^ b3;
int c2 = b0 & b1 & b2 & b3;
int c12 = ((b0 & b1) | ((b0 ^ b1) & b2) | ((b0 ^ b1 ^ b2) & b3));

// build masks from bit-planes
int m0 = ~c0 & ~c12;
int m1 =  c0 & ~c12;       // c0 implies ~c2
int m2 = ~c0 &  c12 & ~c2;
int m3 =  c0 &  c12;       // c0 implies ~c2
int m4 =  c2;              // c2 implies ~c0 & ~c1

Это 19 операций И/ИЛИ и 5 операций НЕ для наивного компилятора, но тривиальная общая оптимизация подвыражений должна уменьшить это число до 15 операций И/ИЛИ и 3 операций НЕ, всего 18 операций.

(Конечно, реальный прирост производительности на современных процессорах будет обеспечен за счет переупорядочения инструкций для уменьшения простоев конвейера. Я подозреваю, что этот код должен работать довольно хорошо в этом отношении: в то время как маски, очевидно, зависят от счетчиков, а счетчики на входах, не имеют внутренних зависимостей ни в счетчиках, ни в масках, поэтому должно быть достаточно места для изменения порядка.)

Обновление от 23 ноября 2014 г. Приведенный выше код не тестировался и содержал ошибку в выражении для c1 / c12. Я исправил это сейчас и даже смог сделать его немного более оптимизируемым, сэкономив одну операцию после исключения общего подвыражения (но стоило одной дополнительной операции для наивного компилятора). Тем не менее, он по-прежнему использует больше операций, чем решение CodesInChaos на основе сортировки.

Поскольку m2 кажется более сложным для вычисления, вы можете написать:

m2 = ~(m0 | m1 | m3 | m4)  // 4 ops

Если предположить, что приведенный ниже (неэффективный) поисковый код C++ верен, выражения с наименьшим количеством операций, запрещающих временные переменные, будут следующими:

(4 ops): m0 = ~(((b3 | b2) | b1) | b0)
(7 ops): m1 = ((((b1 & b0) | b3) | b2) ^ (((b3 & b2) | b1) | b0))
(7 ops): m2 = (((b3 | b0) & (b2 | b1)) ^ ((b2 & b1) | (b3 & b0)))
(7 ops): m3 = (((((b3 | b2) & b1) & b0) ^ (b3 & b2)) & (b1 | b0))
(3 ops): m4 = (((b3 & b2) & b1) & b0)

Я проверил только m1 вручную. Это интересная проблема, но вы уверены, что это узкое место в вашем программном обеспечении? Даже если это так, реализация с наименьшим количеством операций может быть не самой быстрой, например. Я не знаю, но НЕ может быть быстрее, чем другие операции.

// A program to search for boolean expressions that determine
// whether n of bools x0,..x3 are true, made up of a minimal
// number of ands, ors, xors and nots.

// There are 2**4=16 possible assignments of x0,..x3
// so there are 2**16 functions (assignments) -> (output)
// thus each map can be identified as an integer
// fun[i] will be the list of ids of all functions that
// can be represented with <= n operations

// options
const int max_ops = 7; // max number of ops to search to


#include <tchar.h>
#include <vector>
#include <set>
#include <iostream>
#include <bitset>
#include <map>
#include <string>

using namespace std;

typedef enum {
    LITERAL,
    NOT,
    AND,
    OR,
    XOR
} OpType;

typedef struct {
    int first;
    int second;
    OpType type;
} op;

int get_count_fn(int k)
{
    // return the id of the function which is true if
    // k of the 4 inputs are true
    int x = 0;
    for (int j = 0; j < 16; j++)
    {
        int m = 0;
        for (int i = 0; i < 4; i++)
        {
            if (j & (1 << i))
            {
                m += 1;
            }
        }
        if (m == k)
        {
            x |= (1 << j);
        }
    }
    return x;
}

void add_triple(map<int, op> & src, int first, int second, OpType type, int result)
{
    // record an operation
    op rhs;
    rhs.first = first;
    rhs.second = second;
    rhs.type = type;
    src[result] = rhs;
}

int get_first(const vector<map<int, op>> & src, int val)
{
    // find the first n such that src[n] contains val
    for (unsigned int i = 0; i < src.size(); i++)
    {
        if (src[i].find(val) != src[i].end())
        {
            return i;
        }
    }
    return -1;
}

string display_retrace(const vector<map<int, op>> & src, int val)
{
    // trace a function backwards to find out how it was constructed
    string result;

    // find the op leading to it
    int n = get_first(src, val);
    auto iter = src[n].find(val);
    op o = iter->second;

    // print it out, recursively
    if (o.type == LITERAL)
    {
        result = string("b") + to_string(o.first);
    }
    else if (o.type == NOT)
    {
        result = string("~") + display_retrace(src, o.first);
    }
    else if (o.type == AND)
    {
        result = string("(") + display_retrace(src, o.first) + string(" & ") +
            display_retrace(src, o.second) + string(")");
    }
    else if (o.type == OR)
    {
        result = string("(") + display_retrace(src, o.first) + string(" | ") +
            display_retrace(src, o.second) + string(")");
    }
    else if (o.type == XOR)
    {
        result = string("(") + display_retrace(src, o.first) + string(" ^ ") +
            display_retrace(src, o.second) + string(")");
    }
    return result;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int all_on = (1 << 16) - 1;
    vector<int> countFuns;
    vector<bool> foundCountFuns;
    vector<map<int, op>> src;

    cout << "The `counting' functions we seek are:\n";
    for (int k = 0; k <= 4; k++)
    {
        int cf = get_count_fn(k);
        cout << std::bitset<16>(cf) << "\n";
        countFuns.push_back(cf);
        foundCountFuns.push_back(false);
    }

    for (int i = 0; i <= max_ops; i++)
    {
        src.push_back(map<int, op>());
    }

    // add all the literals to the list for 0 operations

    for (int i = 0; i < 4; i++)
    {
        int x = 0;
        for (int j = 0; j < 16; j++)
        {
            if (j & (1 << i))
            {
                x |= (1 << j);
            }
        }
        add_triple(src[0], i, -1, LITERAL, x);
    }

    // iterate over the number n of operators
    for (int n = 1; n <= max_ops; n++)
    {
        // iterate over i,j with i+j=n-1
        for (int i = 0; i <= n - 1; i++)
        {
            int j = n - i - 1;

            // add all combinations of all vectors to the list for n
            for (auto pi = src[i].begin(); pi != src[i].end(); pi++)
            {
                for (auto pj = src[j].begin(); pj != src[j].end(); pj++)
                {
                    int xi = pi->first;
                    int xj = pj->first;
                    add_triple(src[n], xi, xj, OR, xi | xj);
                    add_triple(src[n], xi, xj, AND, xi & xj);
                    add_triple(src[n], xi, xj, XOR, xi ^ xj);
                }
            }
        }
        // also add the "nots" from n-1
        for (auto pprev = src[n - 1].begin(); pprev != src[n - 1].end(); pprev++)
        {
            int xprev = pprev->first;
            add_triple(src[n], xprev, -1, NOT, all_on - xprev);
        }

        cout << "Functions with " << n << " operators: size is " << src[n].size() << " ---\n";

        // search for the functions we are interested in
        for (unsigned int k = 0; k < countFuns.size(); k++)
        {
            if (!foundCountFuns[k] && src[n].find(countFuns[k]) != src[n].end())
            {
                cout << "Found count function " << k << ":\n";
                cout << "m" << k << " = " << display_retrace(src, countFuns[k]) << "\n";
                foundCountFuns[k] = true;
            }
        }
    }

    system("pause");
    return 0;
}

Прошу прощения за С++. Это просто облегчает вывод.

const int b1 = 0b00001010;
const int b2 = 0b10100111;
const int b3 = 0b10010010;
const int b4 = 0b10111110;

// 4 operations
const int x12 = b1 ^ b2;
const int x34 = b3 ^ b4;
const int a12 = b1 & b2;
const int a34 = b3 & b4;

const int m0 = ~(b1 | b2 | b3 | b4);  // 4 operations
const int m3 = ((x12) & (a34)) | ((a12) & (x34)); // 3 operations
const int m1 = ((x12) ^ (x34)) & ~m3; // 3 operations
const int m4 = a12 & a34; //1 operation
const int m2 = ~(m0 | m1 | m3 | m4); //4 operations

cout << bitset<8>(m0) << endl << bitset<8>(m1) << endl << bitset<8>(m2) << endl << bitset<8>(m3) << endl << bitset<8>(m4) << endl;

А. Максимум, что я мог сделать, это 19 операций.

Вот результаты, отсортированные по количеству масок, рассчитанных одновременно.

Для каждой маски требуется не более 7 операций, если рассчитывать отдельно:

a01 = b0 & b1
a23 = b2 & b3
r01 = b0 | b1
r23 = b2 | b3

m0 = ~(r01 | r23)              // 4 ops
m1 = (a01 | r23) ^ (r01 | a23) // 7 ops
m2 = (r01 & r23) ^ (a01 | a23) // 7 ops
m3 = (r01 & r23) & (a01 ^ a23) // 7 ops
m4 = a01 & a23                 // 3 ops

Здесь много общих подвыражений, поэтому, если вам нужно знать любую пару масок сразу, вам потребуется не более 10 операций (меньше с m0 или m4).

Но расчет некоторых пар можно оптимизировать еще больше:

// m2,m3 in 9 ops
t1 = r01 & r23
t2 = a01 ^ a23
m2 = t1 ^ (a23 | t2)
m3 = t1 & t2

// m1,m3 in 9 ops
t1 = r01 ^ r23
t2 = a01 ^ a23
t3 = t1 ^ t2
m1 = t1 & t3
m3 = t2 & t3

Тот же подход работает для троек масок. Только одна тройка (m1,m2,m3) может быть вычислена быстрее, за 11 операций, с подходом "сортировать биты" , что является оптимальным.

Если вам нужно 4 или 5 масок одновременно, я считаю, что подход «сортировать по битам» даст оптимальный результат.

Возможны еще некоторые оптимизации, если мы разрешим еще одну операцию (NAND). На самом деле последние 3 строки последнего фрагмента кода можно заменить на 2 NAND:

// m1,m3 in 8 ops (NAND is a single op)
t1 = r01 ^ r23
t2 = a01 ^ a23
m1 = t1 & ~t2
m3 = ~t1 & t2

И (m1,m2,m3) тройка также может быть оптимизирована с помощью NAND:

// m1,m2,m3 in 10 ops (NAND is a single op)
x01 = b0 ^ b1
x23 = b2 ^ b3
a01 = b0 & b1
a23 = b2 & b3
t1 = x01 ^ x23
t2 = a01 ^ a23
m1 = t1 & ~t2
m2 = ~t1 & (x23 ^ t2)
m3 = t1 & t2

Добавьте еще одну операцию m4 = a01 & a23, чтобы получить все маски, кроме m0, за 11 операций.

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

Вот код (С++ 14 или С++ 11 плюс двоичные литералы):

/* Search for minimal logical expression (using &|^ operations) for bits set
 * exactly N times (in a group of 4 bits).
 *
 * Uses brute force approach to get one or two expressions for one or two
 * values of N at once. To make it possible getting results in reasonable time
 * some simplifications were made:
 * - first 4 operations pre-defined: &| or ^& or ^| for 2 pairs of input values
 * - number of ops limited, if no result found within limit, print "impossible"
 * - no attempts to perform operation on 2 expr with the same left and the same
 *   right parts
 * - unused nodes are not allowed (to minimize number of duplicate attempts)
 * - no attempt to use "not" (except for "m0")
 * 
 * Also these optimizations were tried (with no significant effect):
 * - no more than 2 different ops on same pair of sub-expressions
 * - do not apply same op on same pair of sub-expressions more than once
 *
 * operation set may be extended by "nand" (kNAnd option)
*/

#include <algorithm>
#include <array>
#include <iostream>
#include <bitset>
#include <thread>
#include <mutex>
#include <cassert>
using namespace std;

enum {
    kMaxSize = 17,
    kNTargets = 5,
    kNInputs = 4,
    kNil = 255,
    kNAnd = 0,
};

enum Op {
    OpAnd = kNInputs,
    OpOr,
    OpXor,
    OpNAndL,
    OpNAndR,
};

array<const char*, kNInputs + 3> g_op_str {
    "b0", "b1", "b2", "b3",
    " & ", " | ", " ^ ",
};

array<unsigned, kNTargets> g_target_masks {
    0b0111111111111111, // gives correct result only after additional "not"
    0b0111100000000000,
    0b0000011111100000,
    0b0000000000011110,
    0b0000000000000001,
};
//    0111122222233334
array<unsigned, kNInputs> g_literal_vals {
    0b0100011100001111,
    0b0010010011010111,
    0b0001001010111011,
    0b0000100101111101,
};

unsigned g_targets = 0;
unsigned g_score_limit = 0;
mutex g_print_mutex;

template<typename C, typename T>
ptrdiff_t findIndex(C c, T t)
{
    auto it = find(begin(c), end(c), t);
    return it - begin(c);
}

struct DAGNode
{
    unsigned value;
    uint8_t op;
    bool l_not;
    bool r_not;
    uint8_t left;
    uint8_t right;
    uint8_t use_cnt;

    void clear()
    {
        use_cnt = 0;
    }

    void setLit(const uint8_t lit, const unsigned v)
    {
        value = v;
        op = lit;
        l_not = false;
        r_not = false;
        left = kNil;
        right = kNil;
        use_cnt = 0;
    }
};

struct DAG
{
    array<DAGNode, kMaxSize> nodes;
    unsigned size;
    unsigned score;

    void print(ostream& out, size_t ind)
    {
        auto& node = nodes[ind];

        if (node.op < kNInputs)
        {
            out << g_op_str[node.op];
        }
        else
        {
            out << '(';
            if (node.l_not) out << '~';
            print(out, node.left);
            out << g_op_str[node.op];
            if (node.r_not) out << '~';
            print(out, node.right);
            out << ')';
        }
    }

    void printAll(ostream& out)
    {
        for (size_t i = 2 * kNInputs; i < size; ++i)
        {
            auto& node = nodes[i];
            auto ind = findIndex(g_target_masks, node.value);

            if ((1 << ind) & g_targets)
            {
                out << 'm' << static_cast<char>('0' + ind) << " = ";
                print(out, i);
                out << '\n';
            }
        }
    }
};

bool operator < (const DAG& l, const DAG& r)
{
    return l.score < r.score;
}

class Find
{
    using SPA = array<uint8_t, (kMaxSize - kNInputs) * (kMaxSize - kNInputs)>;
    using EDA = bitset<(kMaxSize - kNInputs) * (kMaxSize - kNInputs) * 5>;
    SPA same_pair_;
    EDA dup_op_;
    DAG dag_;
    DAG best_;
    unsigned ops_;
    unsigned targets_;
    unsigned unused_;

    class UseCnt
    {
        unsigned& unused_;
        uint8_t& use_cnt_;

    public:
        UseCnt(unsigned& unused, uint8_t& use_cnt)
        : unused_(unused)
        , use_cnt_(use_cnt)
        {
            if (!use_cnt_)
                --unused_;

            ++use_cnt_;
        }

        ~UseCnt()
        {
            --use_cnt_;

            if (!use_cnt_)
                ++unused_;
        }
    };

    class PairLim
    {
        uint8_t& counter_;

    public:
        PairLim(SPA& spa, size_t l, size_t r)
        : counter_(spa[(kMaxSize - kNInputs) * l + r])
        {
            ++counter_;
        }

        bool exceeded()
        {
            return counter_ > 2;
        }

        ~PairLim()
        {
            --counter_;
        }
    };

    class DupLim
    {
        EDA& eda_;
        size_t ind_;

    public:
        DupLim(EDA& eda, size_t l, size_t r, size_t op)
        : eda_(eda)
        , ind_(5 * ((kMaxSize - kNInputs) * l + r) + op - kNInputs)
        {
            eda_.flip(ind_);
        }

        bool used()
        {
            return !eda_.test(ind_);
        }

        ~DupLim()
        {
            eda_.flip(ind_);
        }
    };

    unsigned getPos(uint8_t l)
    {
        return dag_.nodes[l].value;
    }

    bool tryNode(uint8_t l, uint8_t r, uint8_t op)
    {
        //DupLim dl(dup_op_, l, r, op);
        //if (dl.used())
        //    return false;

        addNode(l, r, op);
        auto node = dag_.nodes[dag_.size - 1];
        const auto ind = findIndex(g_target_masks, node.value);
        const auto m = (1 << ind) & targets_;

        if (m)
        {
            ++node.use_cnt;
            --unused_;

            if (targets_ == m)
            {
                best_ = dag_;
                --dag_.size;
                --dag_.score;
                return true;
            }

            targets_ &= ~m;
        }

        search();

        if (!m)
        {
            --unused_;
        }

        targets_ |= m;
        --dag_.size;
        --dag_.score;
        return false;
    }

public:
    Find()
    : ops_(kNInputs)
    , targets_(g_targets)
    , unused_(0)
    {
        dag_.score = 0;
        dag_.size = kNInputs;
        best_.score = g_score_limit;
        best_.size = 0;

        for (int i = 0; i < kNInputs; ++i)
            dag_.nodes[i].setLit(static_cast<uint8_t>(i), g_literal_vals[i]);

        fill(begin(same_pair_), end(same_pair_), 0);
    }

    void addNode(const uint8_t l, const uint8_t r, uint8_t op)
    {
        auto& node = dag_.nodes[dag_.size];

        switch (op)
        {
            case OpAnd:
                node.value = getPos(l) & getPos(r);
                break;

            case OpOr:
                node.value = getPos(l) | getPos(r);
                break;

            case OpXor:
                node.value = getPos(l) ^ getPos(r);
                break;

            case OpNAndL:
                node.value = ~getPos(l) & getPos(r);
                break;

            case OpNAndR:
                node.value = getPos(l) & ~getPos(r);
                break;

            default:
                assert(false);
        }

        node.op = op;
        node.l_not = false;
        node.r_not = false;
        node.left = l;
        node.right = r;
        node.use_cnt = 0;

        if (op == OpNAndL)
        {
            node.l_not = true;
            node.op = OpAnd;
        }
        else if (op == OpNAndR)
        {
            node.r_not = true;
            node.op = OpAnd;
        }

        ++dag_.size;
        ++dag_.score;
        ++unused_;
    }

    void search()
    {
        if (dag_.score >= best_.score)
            return;

        for (uint8_t i_r = kNTargets; i_r < dag_.size; ++i_r)
        {
            UseCnt uc_r(unused_, dag_.nodes[i_r].use_cnt);

            if (unused_ > 2 * (best_.score - dag_.score) - 1)
                continue;

            for (uint8_t i_l = kNInputs; i_l < i_r; ++i_l)
            {
                UseCnt uc_l(unused_, dag_.nodes[i_l].use_cnt);

                if (unused_ > 2 * (best_.score - dag_.score) - 2)
                    continue;

                if (dag_.nodes[i_l].left == dag_.nodes[i_r].left &&
                    dag_.nodes[i_l].right == dag_.nodes[i_r].right
                )
                    continue;

                PairLim pl(same_pair_, i_l, i_r);
                if (pl.exceeded())
                    continue;

                if (tryNode(i_l, i_r, OpAnd))
                    return;
                if (tryNode(i_l, i_r, OpOr))
                    return;
                if (tryNode(i_l, i_r, OpXor))
                    return;

                if (kNAnd)
                {
                    if (tryNode(i_l, i_r, OpNAndL))
                        return;
                    if (tryNode(i_l, i_r, OpNAndR))
                        return;
                }
            }
        }
    }

    void print(ostream& out, const char* name)
    {
        if (best_.score < g_score_limit)
        {
            out << name << " ops = " << best_.score << '\n';
            best_.printAll(out);
            out << '\n';
        }
        else
        {
            out << name << " impossible\n\n";
        }
    }

    void process(ostream& out, const char* name)
    {
        search();
        lock_guard<mutex> lk(g_print_mutex);
        print(out, name);
    }
};

unsigned readTargets(char* str)
{
    unsigned num = 0;

    for (; *str; ++str)
    {
        if (*str >= '0' && *str <= '4')
        {
            g_targets |= 1 << (*str - '0');
            ++num;
        }
    }

    return num;
}

void usage()
{
    cerr << "Usage: bitcnt [0-4]*\n"
        "example: bitcnt 23 (to find targets m2,m3)\n";
    exit(1);
}

int main(int argc, char **argv) {
    if (argc > 1)
        g_score_limit = 6 + 2 * readTargets(argv[1]);
    else
        usage();

    // set score_limit to 10 for m1,m2,m3 (with nand), time ≈ 1h

    array<Find, 3> finders;
    finders[0].addNode(0, 1, OpAnd);
    finders[0].addNode(0, 1, OpOr);
    finders[0].addNode(2, 3, OpAnd);
    finders[0].addNode(2, 3, OpOr);

    finders[1].addNode(0, 1, OpAnd);
    finders[1].addNode(0, 1, OpXor);
    finders[1].addNode(2, 3, OpAnd);
    finders[1].addNode(2, 3, OpXor);

    finders[2].addNode(0, 1, OpXor);
    finders[2].addNode(0, 1, OpOr);
    finders[2].addNode(2, 3, OpXor);
    finders[2].addNode(2, 3, OpOr);

    auto t0 = thread([&finders]{finders[0].process(cout, "&|");});
    auto t1 = thread([&finders]{finders[1].process(cout, "&^");});
    auto t2 = thread([&finders]{finders[2].process(cout, "^|");});

    t0.join(); t1.join(); t2.join();
}

_{Первая версия этого ответа все еще верна, но устарела из-за недавних результатов:}

m2 за 10 операций:

x1 = b1 ^ b2;
x2 = b3 ^ b4;
m2 = (x1 & x2) | (((b1 & b2) ^ (b3 & b4)) & ~(x1 | x2));

m1 за 8 операций:

m1 = (b1 ^ b2 ^ b3 ^ b4) & ~((b1 & b2) | (b3 & b4));