使某些整数的异或为零所需的最小和

使某些整数的异或为零所需的最小和 重述为有界整数线性规划问题

该问题可以作为下面的有界ILP（整数线性规划）问题来重述。

Let x1,...,xN be as in the original problem, i.e. the goal is to minimize(a1+...+aN)under the conditions (x1+a1) XOR ... (xN+aN) = 0, a1,...,aN >= 0.The following is than an equivalent bounded ILP:Find b[k,i] (0 <= k <= K, 1 <= i <= N) and s[k] (0 <= k <= K) such that  (A) b[k,i] in {0, 1} for all i=1..n, k=0..K,  (B) s[k] is an integer >= 0 for all k=0..K,  (C) sum(b[k,i]*2^k, k=0..K) >= x[i] for all i = 1..N,  (D) sum(b[k,i], i=1..N) = 2*s[k] for all k = 0..Kand minimize  sum(b[k,i]*2^k, i=1..n, k=0..K).From a solution of the bounded ILP the ai's are obtained by  a[i] = sum(b[k,i]*2^k, k=0..(K-1)) - x[i]

b [k，i]只是（xi + ai）的二进制表示形式的第k位（条件（A）和（C））。为了使总异或为零，每k的偶数b
[k，i]必须为1。这由条件（B）和（D）表示。（请注意，（D）中的左侧和必须等于2 * s [k]，而s [k]是整数）。

K，即代表所有（xi + ai）所需的位数（实际上为1）必须事先确定。选择一个使所有xi <2 ^
K的K就足够了，即ai比最大xi大1位。但是，选择较大的K并不重要，最高位只会简单地为零。如果将K选得很小，则ILP将没有解决方案。

解决方案的存在

忽略最小条件，可以将问题重述为

给定x，yz，且x <= y，找到a和b使得（x + a）XOR（y + b）= z

给定您原始问题的一个实例，其中N> =2。设x = x1，y = x2，z =（x3 XOR x4 XOR … xn）。如果找到合适的a和b，则设置a1
= a，a2 = b，a3 = … = an = 0以获得原始问题的解决方案。

简化的问题通过以下方式解决（再次 忽略 极小值）

1. 如果（y XOR z）> = x，则a：=（（y xOR z）-x），b：= 0是一个解（*）
2. 如果（x XOR z）> = y，则a：= 0，b：=（（（x XOR z）-y）是一个解（*）
3. 否则，选择一个（x + a）XOR z> = y的a。这样的a总是存在的，例如，可以让：= 2 ^ k的2 ^ k> max（x，y，z）。设置b：=（（（x + a）XOR z）-y）得出解（*）

（*）要看到这些确实是解决方案，您只需要应用一些代数即可。例如，在情况（1）中，用a和b替换后，得到：（x +（y XOR z）-x）XOR（y +
0）。这与：（y XOR z）XOR y相同，因此与：zqed Case（2）相似。在情况（3）中，您得到：（x + a）XOR（y +（（x +
a）XOR z）-y）=（x + a）XOR（（x + a）XOR z）= z。

这表明对于N> = 2，始终存在一个解决方案。

我不知道这些解决方案是否最少。在情况（3）中，很明显取决于a的选择，因此至少您必须找出a的最佳选择。也可能是原始问题比简化问题允许使用更小的解决方案。顺便说一句，也许这种重述可以帮助某人找出完整的解决方案。

顺便说一句，原始问题本质上让您完全自由地选择了如何在xi上“散布”校正值ai，这使我想知道这是否不等同于某种背包问题。如果是这样，找到一个最小的解决方案很可能是NP难题。

关于极简的观察

采取以下问题

(1+a1) XOR (3+a2) XOR (6+a3) = 0

用二进制表示

(001b+a1) XOR (011b+a2) XOR (110b+a3) = 0

a1 = a2 = a3 = 0的残基为001b XOR 011b XOR 110b = 100b。因此，一个明显的解决方案是a1 = 4，a2 =
0，a3 = 0。或者，a1 = 0，a2 = 4，a3 = 0。尽管此解决方案 不是 最小的-以下解决方案较小

a1=1, a2=1, a3=0

这也是最小的，因为所有较小的解决方案都只能具有一个非零的ai，并且所有项（2 XOR 3 XOR 6），（1 XOR 4 XOR 6），（1 XOR 3
XOR 7）都是非零的。

这表明从底部（即最低位）开始工作的gree算法将无法工作，因为这种算法会跳过前两位，因为它们的残差最初为零。

它还表明，您无法从残差中选择某个非零位 k 并尝试通过将 2 ^ k 加到xi 之一
中来将其归零。有时您必须将其添加到多个xi中以找到最小的解决方案。

这使我更进一步地相信，找到一个最小的解决方案是一个相对困难的问题。