如何使用基本的数学运算符(+、-、*、/)来实现异或(XOR)操作？
更新：实际上，我需要跟踪两个具有布尔值的矩阵中的变化。可以通过将每个值与另一个矩阵中相应的值进行异或操作来完成此操作。但是，Lp_Solve库不支持异或操作。此外，它仅接受线性方程。
9个回答
17
(a − b)²
这个公式之所以可行，是因为：
(a − b)² = a * (a − b) + b * (b − a)
因为在 ℤ₂ 中，乘法是指数 (&), 1 - a 表示为否定 (!)，因此上述公式对于 a, b ∈ {0, 1} 等价于异或操作:
(a & !b) | (b & !a)
请参阅Pascal Cuoq在下面的评论中解释为什么这不能是线性方程。
- glebm
2
2我考虑了一下，这不会是一个线性方程。你能想到一些线性形式的东西吗？ - Mayur
35@Mayur 看看在三维空间中点(0,0,0), (1,0,1), (0,1,1), (1,1,0)形成的形状。那就是异或函数的图像。由于这些点不在同一个平面上，因此不存在通过所有这些点的
x和y的线性函数。 - Pascal Cuoq12
简述：
对于任何数字输入，XOR的结果为
a + b - ab(1 + a + b - ab)
对于二进制输入，XOR的结果为
a + b - 2ab 或 (a-b)²
推导过程
基本逻辑运算符
NOT = (1-x)
AND = x*y
从这些运算符中可以得到...
OR = (1-(1-a)(1-b)) = a + b - ab
注意：如果a和b是互斥的，则它们的and条件将始终为零-从Venn图的角度来看，这意味着没有重叠。在这种情况下，我们可以写OR= a + b，因为对于所有的a和b值，a*b=0。
双因素XOR
将XOR定义为(a OR B) AND (NOT (a AND b)):
(a OR B) --> (a + b - ab)
(NOT (a AND b)) --> (1 - ab)
AND这些条件得到...
(a + b - ab)(1 - ab) = a + b - ab(1 + a + b - ab)
计算替代方案
如果输入值是二进制的，则可以忽略幂次项，以简化计算等效形式。
a + b - ab(1 + a + b - ab) = a + b - ab - a²b - ab² + a²b²
如果x是二进制（要么是1，要么是0），那么我们可以忽略幂次项，因为1²=1和0²=0...
a + b - ab - a²b - ab² + a²b² -- 去掉幂次项 --> a + b - 2ab
XOR (二进制) = a + b - 2ab
二进制还允许其他方程式在计算上等同于上述方程。例如...
给定 (a-b)² = a² + b² - 2ab
如果输入是二进制的，我们可以忽略幂次，所以...
a² + b² - 2ab -- 移除幂次 --> a + b - 2ab
使我们能够写成...
XOR (二进制) = (a-b)²
多因素异或
XOR = (1 - A*B*C...)(1 - (1-A)(1-B)(1-C)...)
当你想要对(A,B,C...)进行异或时怎么办？问题在于，如果我们像在2因素异或的组合逻辑中那样尝试确定所有真实条件，它不会非常好扩展，因为您必须添加每个真实条件的排列组合。然而，由于逻辑本质如此，我们可以通过补充方式得出异或...
XOR = !(A & B & C...) & !(!A & !B & !C...)
从中，您可以构造任意数量的因素的算术异或形式...
(1 - A*B*C...)(1 - (1-A)(1-B)(1-C)...)
下面是一些Excel VBA代码，可以对整个单元格范围进行异或操作...
Function ArithmeticXOR(R As Range, Optional EvaluateEquation = True)
Dim AndOfNots As String
Dim AndGate As String
For Each c In R
AndOfNots = AndOfNots & "*(1-" & c.Address & ")"
AndGate = AndGate & "*" & c.Address
Next
AndOfNots = Mid(AndOfNots, 2)
AndGate = Mid(AndGate, 2)
'Now all we want is (Not(AndGate) AND Not(AndOfNots))
ArithmeticXOR = "(1 - " & AndOfNots & ")*(1 - " & AndGate & ")"
If EvaluateEquation Then
ArithmeticXOR = Application.Evaluate(xor2)
End If
End Function
任意n个中的k
在这里还有一个小细节。有时候，如果任意n个输入为true，则希望条件为true。这可以视为一种放松的AND条件，你可以接受a&b或a&c或b&c等情况。这可以从组合逻辑算术模型中表示为...
(a && b) || (a && c) || (b && c) ...
并应用我们的翻译...
1 - (1-ab)(1-ac)(1-bc)...
这本身就很有用，但是当您扩展这些术语时会发现一个有趣的模式。变量和指数组合的模式取决于n与k的关系。对于n = k-1，其中k是正在测试的所有条件的总数，结果如下：
c1 + c2 + c3 ... ck - n*∏
其中c1到ck都是n变量组合。
例如，如果满足4个条件中的3个，则为true
abc + abe + ace + bce - 3abce
这是完全合乎逻辑的，因为我们所拥有的是OR条件的加法AND条件减去重叠的AND条件。
如果您开始查看n = k-2，k-3等。该模式变得更加复杂，因为我们有更多的重叠要减掉。如果将其完全扩展到最小值n = 1，则最终得到的就是常规的OR条件。
考虑非二进制值和模糊区域
实际的代数异或方程a + b - ab(1 + a + b - ab)比计算等效的二进制方程如x + y - 2xy和(x-y)²要复杂得多。这意味着什么，这种额外的复杂性有任何价值吗？
显然，要使此事成立，您必须关心离散点（0,0），（0,1），（1,0）和（1,1）之外的十进制值。为什么这会有所影响？有时候，您希望放宽离散问题的整数约束。在这种情况下，您必须查看用于将逻辑运算符转换为方程的前提条件。
当涉及将布尔逻辑转换为算术时，您的基本构建块是AND和NOT运算符，您可以使用它们构建OR和XOR。
OR = (1-(1-a)(1-b)(1-c)...)
XOR = (1 - a*b*c...)(1 - (1-a)(1-b)(1-c)...)
如果你考虑十进制区域，那么值得思考的是我们如何定义这些运算符以及它们在该区域内的行为。
NOT的非二进制含义
我们将NOT表示为1-x。显然，这个简单的方程适用于0和1的二进制值，但真正酷的地方在于它还提供了0到1之间值的分数或百分比补充。这很有用，因为NOT在布尔逻辑中也被称为Compliment，当涉及到集合时，NOT指的是当前集合之外的所有内容。
AND的非二进制含义
我们将AND表示为x*y。同样，它适用于0和1，但对于0到1之间的值，乘法会导致部分真相（小数值）相互抵消。在这个区域内，可能想要将真相建模为平均或累积。例如，如果两个条件假设是半真的，那么AND条件是只有四分之一真（0.5 * 0.5），还是完全真（0.5 + 0.5 = 1），或者它仍然是半真的（（0.5 + 0.5）/ 2）？事实证明，对于完全离散的条件而言，四分之一的真相实际上是真实的，而部分真相则代表概率。例如，你会不会掷硬币反面朝上（二进制条件，50％的概率）现在和再次掷硬币反面朝上？答案是0.5 * 0.5 = 0.25，即25％的真相。累积并没有太多意义，因为它基本上是在建模OR条件（记住当不存在AND条件时，OR可以用+进行建模，因此总和特征上是OR）。平均值在考虑协议和测量时是有意义的，但它实际上是在建模AND和OR的混合物。例如，请两个人在1到10的刻度上说出他们对“外面很冷”这个陈述的同意程度。如果他们都说5，则“外面很冷”的真相为50％。
非二进制值总结
从这篇关于非二进制值的文章中，我们可以得出的结论是，我们可以通过选择运算符捕获实际逻辑并从基础构建方程，但我们必须牢记数值行为。我们习惯于将逻辑视为离散（二进制），计算机处理为离散，但非二进制逻辑变得越来越普遍，可以帮助解决使用离散逻辑难以解决/可能解决的问题。您需要考虑值在此区域内如何相互作用以及如何将它们转化为有意义的内容。- u8it
7
2真是太聪明了。 - Rob
这是一个深思熟虑且富有洞见的回答！ - Maxim Khanov
4公式
f(a,b)=a + b - ab(1 + a + b - ab) 的计算结果 f(1,2)=-1，但预期值 XOR(1,2)=3，如何解决这个差异？ - Eric值得注意的是，负数除了让数字带有符号外并不存在。有符号整数仅仅是正整数的解释表示，其中正整数通过其模2^k的剩余类直接计算为负数。因此，如果您想要NOT(x)，您应该使用NOT(x) = 2 **（floor(log_2(x))）+1）- x来模拟NOT（以及“最小”格式的二进制补码整数）。我不能说我信任您用于表示整数的“数字”表示的基础。 - AMDG
数学公式 a + b - ab(1 + a + b - ab) 是错误的。 - HabibS
显示剩余2条评论
9
我能提供的最简单的表达方式是：
a != b。（之前的最佳尝试是(a + b) == 1）- Paul R
2
2@Paul：通常，在这些求解器中，诸如
a != b之类的表达式是不可能的（没有检查过这个特定的求解器）。因此，如果可以输入方程（而不仅仅是不等式），则您先前的最佳答案可能仍然是最好的。 - Konrad Rudolph@Konrad：谢谢，是的，我不确定哪些运算符是允许的，所以我把之前的建议留作可能的替代方案。如果OP能够明确指定可用的运算符，那将会很有帮助... - Paul R
8
在 Brown, G. 和 Dell, R. 的文章《Formulating linear and integer linear programs: A rogues’ gallery》中，可以找到以下用于XOR的线性规划公式：
解析为
Z3 = Z1 XOR Z2
解析为
Z3 <= Z1 + Z2
Z3 >= Z1 - Z2
Z3 >= -Z1 + Z2
Z3 <= 2 - Z1 - Z2
- Turnip
6
嗯……这并不是那么简单。
要建立一个异或模型（我们称之为X），我们需要从逻辑开始。
在数学中，以上可以写成：
但是上述表达式是非线性的（由于双线性项——为了保持线性，我们不允许将变量彼此相乘）。
但是！因为我们可以使用约束条件，我们可以将上述表达式重写为线性形式。
首先，我们展开这些项：
现在我们需要处理A*B项（实际上意味着A＆B）。让变量H表示逻辑条件A＆B。我们现在可以将AND条件写成如下形式：（见下面引用的PDF参考资料）
线性异或公式
最后，让我们把所有东西放在一起。这是您的异或公式，只使用线性约束。
我知道看起来很复杂（对于一个像 XOR 这样简单的操作）。可能有更紧凑的表达方式。
但通常情况下，在线性规划上写逻辑条件是很复杂的，因为人们通常在可以执行的操作上受到严格限制——以避免破坏问题的理论特性。
参考文献：
请查看此处列出的标准整数公式列表，以线性方式表示逻辑。http://brblog.typepad.com/files/mipformref-1.pdf
编辑：
在上述情况下，H 可以取的唯一值是 0，因为 H 属于区间 [0,0]。因此我们得到 (A,B) = (0,0) => H = 0。
让我们再看一个例子，(A,B) = (1,1)。
从上面可以立即看出，1 <= H <= 1 意味着 H = 1。我们得到 (A,B) = (1,1) => H = 1。
依此类推。你会发现H的限制条件恰好模拟了“AND”条件。
要建立一个异或模型（我们称之为X），我们需要从逻辑开始。
X = (A & !B) | (!A & B)
在数学中，以上可以写成：
X = A*(1-B) + B*(1-A)
但是上述表达式是非线性的（由于双线性项——为了保持线性，我们不允许将变量彼此相乘）。
但是！因为我们可以使用约束条件，我们可以将上述表达式重写为线性形式。
首先，我们展开这些项：
X = A*(1-B) + B*(1-A) = A + B - 2*A*B
现在我们需要处理A*B项（实际上意味着A＆B）。让变量H表示逻辑条件A＆B。我们现在可以将AND条件写成如下形式：（见下面引用的PDF参考资料）
H <= A
H <= B
H >= A + B - 1
H >= 0
线性异或公式
最后，让我们把所有东西放在一起。这是您的异或公式，只使用线性约束。
X = A + B - 2*H
H <= A
H <= B
H >= A + B - 1
H >= 0
我知道看起来很复杂（对于一个像 XOR 这样简单的操作）。可能有更紧凑的表达方式。
但通常情况下，在线性规划上写逻辑条件是很复杂的，因为人们通常在可以执行的操作上受到严格限制——以避免破坏问题的理论特性。
参考文献：
请查看此处列出的标准整数公式列表，以线性方式表示逻辑。http://brblog.typepad.com/files/mipformref-1.pdf
编辑：
说明H约束如何模拟“AND”逻辑条件
实质上，在LP中，我们提出了不等式约束，必须在解决方案点上满足——这里我们正在玩一个把H“挤压”到正确值的技巧。例如，给定元组（A，B）=（0,0），H的约束将是：
H <= 0
H <= 0
H >= -1
H >= 0
在上述情况下，H 可以取的唯一值是 0，因为 H 属于区间 [0,0]。因此我们得到 (A,B) = (0,0) => H = 0。
让我们再看一个例子，(A,B) = (1,1)。
H <= 1
H <= 1
H >= 1
H >= 0
从上面可以立即看出，1 <= H <= 1 意味着 H = 1。我们得到 (A,B) = (1,1) => H = 1。
依此类推。你会发现H的限制条件恰好模拟了“AND”条件。
- Gilead
2
+1 for
X = A*(1-B) + B*(1-A); it's more efficient than X = (a-b)(a-b), but I'm confused about how Mayur can use the H AND condition。有趣的阅读！ - JohnB谢谢！我已经在上面添加了一个数学解释。实质上，将H约束条件添加到问题中，LPsolve会在解决问题时考虑它们。这更多是数学问题，而不是计算机科学问题。如果将此优化问题作为非线性程序（NLP）而不是线性程序（LP）来解决，则X = A *（1-B）+ B *（1-A）将完美地工作。当需要提出线性公式时，就需要进行一些数学技巧了。 - Gilead
5
你能做这样的事情吗：
(a + b) % 2
- Alexander Vakrilov
1
它可能有效，但你必须明确指定a和b属于哪个集合。因为如果我们只是采用通常的例子1 ^ 2 == 3，在你的情况下我们得到：
(1 + 2 ) % 2 = 3 % 2 = 1 - Lorenzo
0
abs(A+B-1)。如果不起到绝对值的作用，那么(A+B-1)*(A+B-1)就可以实现。
- Jason
1
4(1,1) ---|1+1-1|//(1+1-1)^2---> 1，应该是0。这样不行。 - nlucaroni
0
异或是一个线性函数，但关于布尔函数的“线性”定义与多项式函数不同。您需要查阅lp_solve库的文档，以确定它是否能够处理线性布尔函数。从我所读的内容来看，我怀疑它无法处理。
编辑： 在进一步研究lp_solve使用的单纯形算法后，我相当确定您无法做到您试图做的事情。
- bta
0
你可以使用以下代码：
Xor(n,x,y)=x+y - Pow(2,n+1)(floor((x+y)/Pow(2,n+1)));
其中：
x => Z集合中的正整数，x>=0
y => Z集合中的正整数，y>=0
n => 数据位长度，例如32或64
pow(2,3)=> 222
floor(1.6594565)=1 或 floor(4562.21)=4562
- Azad Developments
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
if语句的？ - Anton Gogolev