c - 多个位向量；如何找到恰好设置 n 次的位？

Question

我有四个位向量的集合，例如：

b1 = 00001010
b2 = 10100111
b3 = 10010010
b4 = 10111110

我想获得在给定位向量的 0、1、2、3 或 4 中设置的那些位的掩码。因此 m0 将是未在四个位向量中的任何一个中设置的位的掩码，m3 是在恰好三个位向量中设置的那些位的掩码，等等：

m0 = 01000000
m1 = 00000001
m2 = 00111100
m3 = 10000000
m4 = 00000010

使用按位运算符找到这些掩码的最快方法是什么？

我假设这些对 0 位和 4 位的操作最少：

m0 = ~(b1 | b2 | b3 | b4)  // 4 ops
m4 = b1 & b2 & b3 & b4     // 3 ops

对于其他选项，我不太确定我的方法操作最少：

m1 = ((b1 ^ b2) & ~(b3 | b4)) | (~(b1 | b2) & (b3 ^ b4)) // 9 operations
m2 = ((b1 ^ b2) & (b3 ^ b4)) | ((b1 ^ b3) & (b2 ^ b4)) | ((b1 ^ b4) & (b2 ^ b3)) // 11 operations
m3 = ((b1 ^ b2) & (b3 & b4)) | ((b1 & b2) & (b3 ^ b4)) // 7 operations

这是计算这些掩码的最快方法还是我可以做得更快（在更少的操作中）？

在大多数情况下，我需要这些面具中的一个或几个，而不是同时使用所有这些面具。

（注意，实际上我会为 64 位或 128 位向量执行此操作。这可能无关紧要，但我在 32 位 x86 平台上的 C 中执行此操作。）

Answer 1

所有口罩的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 次操作

Answer 2

首先考虑位向量长度为​​ 1 的简单情况，即它们只是单个位。你真正想做的是计算这些被设置的位的数量；将计数映射到您想要的位掩码是一个相对简单的练习。

诀窍是找到一种仅使用按位运算（即AND、OR、XOR 和NOT）对位进行计数的方法，结果计数的每一位都以一个单独的变量结束。如果你能做到这一点，那么你可以同时对变量中的尽可能多的位进行操作。这种技术称为位切片或寄存器内 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 个 AND / OR / XOR 操作和 9 个 NOT。然而，一个体面的编译器应该缓存 , 和 的值~c0，~c1最多~c2保存 6 个 NOT，并且可能还有一些重复的子表达式，如b0 & b1, b0 ^ b1, b0 ^ b1 ^ b2, ~c1 & ~c2and c1 & ~c2，最多保存 6 个 AND/XOR，总共 17 个 AND/OR/ XORs plus 3 NOTs = 20 ops，这非常接近于 Jonathan Mee 的 19-op 解决方案。

事实上，我们可以通过意识到我们实际上不需要计算c1，而是可以使用 来做得更好c12 = c1 | c2。我们还可以通过注意c2不能设置 if c0(or 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 个 AND/OR 和 5 个 NOT，但简单的公共子表达式优化应该将其减少到 15 个 AND/OR 和 3 个 NOT，总共18 个 ops。

（当然，现代处理器的真正性能提升将来自指令重新排序以减少流水线停顿。我怀疑这段代码在这方面应该做得相当好：虽然掩码显然取决于计数和输入的计数，但在计数或掩码中都没有内部依赖关系，因此应该有足够的空间进行重新排序。）

---

2014 年 11 月 23 日更新：我之前的代码未经测试，并且在c1/的表达式中包含一个错误c12。我现在已经修复了它，甚至设法使它更易于优化，在消除常见的子表达式后节省了一个操作（但对于一个幼稚的编译器来说要花费一个额外的操作）。不过，它仍然使用比 CodesInChaos 的基于排序的解决方案更多的操作。

Answer 3

假设下面的（低效）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。这是一个有趣的问题，但您确定这是您软件的瓶颈吗？即使是这样，具有最少操作的实现也可能不是最快的，例如我不知道但 NOT 可能比其他操作更快。

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

Answer 4

由于m2似乎更难计算，你可以写：

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

Answer 5

以下是按同时计算的掩码数量排序的结果。

如果单独计算，每个掩码最多需要 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 次操作（少用m0or 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

同样的方法适用于掩码三元组。在 11 次操作中，只有一个三元组 ( m1, m2, m3) 可以更快地计算，使用“排序位”方法，这是最佳的。

如果您一次需要 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以获取除m011 项操作之外的所有掩码。

这些结果是在详尽的搜索代码的帮助下获得的（见下文）。这段代码使用了一些简化的假设，以便能够足够快地运行。这些假设并不明显，这使得该代码不是证明结果最优性的好工具。至少单独掩码的结果是最佳的，这已由其他答案的代码证明。我的代码“证明”了掩码对和三元组结果的最优性，这意味着您很可能无法更快地做到这一点。

这是代码（C++14 或 C++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));

Answer 6

请原谅 C++。它只是使输出更容易。

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;

A. 我能做的最好的就是 19 次手术。