以下の (非効率的な) C++ 検索コードが正しいと仮定すると、ops が最も少なく、一時変数が許可されない式は次のようになります。
(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を手で確認しただけです。これは興味深い問題ですが、これがソフトウェアのボトルネックであると確信していますか? たとえそうであったとしても、ops が最も少ない実装が最速ではないかもしれません。例えば、わかりませんが、他の ops よりも速くなる可能性はありません。
// 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;
}