18

如何使用 +、-、*、/ 等基本数学运算符实现 XOR

更新：实际上，我需要跟踪两个具有布尔值的矩阵的变化。这可以通过将每个值与其他矩阵中的相应值进行异或来完成。但是，Lp_Solve 库不支持 XOR 操作。此外，它只接受线性方程。

4

9 回答 9

15

(a - b)²

(a − b)² 的 3D 图

这有效，因为：

(a − b)² = a * (a − b) + b * (b − a)

由于 ℤ₂ 中的乘法是合取 ( &)，并且1 - a是否定 ( !)，因此上式等价于 XOR a, b ∈ {0, 1}：

(a & !b) | (b & !a)

请参阅 Pascal Cuoq 下面的评论，解释为什么这不能是线性方程。

于 2010-03-05T08:33:52.967 回答
9

我能想到的最简单的表达方式是：a != b.

（以前的最大努力是(a + b) == 1）

于 2010-03-05T08:54:36.090 回答
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
于 2011-03-30T13:23:28.747 回答
7

TL;博士

异或任何数字输入

a + b - ab(1 + a + b - ab)

异或二进制输入

a + b - 2ab或者(a-b)²

推导

基本逻辑运算符

NOT=(1-x)

AND=x*y

从这些运营商我们可以得到...

OR= (1-(1-a)(1-b))=a + b - ab

注意：如果 a 和 b 互斥，那么它们的and条件将始终为零 - 从维恩图的角度来看，这意味着没有重叠。在这种情况下，我们可以写OR= a + b，因为a*b = 0对于 a & b 的所有值。

2 因子异或

将 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)...)

当你想要 XOR(A,B,C...) 时呢？这里的问题是，如果我们尝试识别所有真值条件，就像我们在 2 因子 XOR 的复合逻辑中所做的那样，它不能很好地扩展，因为您必须添加每个真值排列。然而，逻辑就是这样，我们可以以互补的方式得出 XOR ......

XOR=!(A & B & C...) & !(!A & !B & !C...)

您可以从中构造任意数量的因子的算术 XOR，形式为...

(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

k中的任意n

这里最后一个花絮。有时，如果任意 n 个输入为真，您希望条件为真。这可以被视为一种放松的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*∏</p>

其中 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) 之外的十进制值。为什么这会很重要？有时您想放松离散问题的整数约束。在这种情况下，您必须查看用于将逻辑运算符转换为方程式的前提。

在将布尔逻辑转换为算术时，您的基本构建块是ANDandNOT运算符，您可以使用它们构建ORand 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（请记住OR，可以通过条件不存在+时进行建模，因此总和是典型的）。如果您正在查看一致性和测量值，则平均值是有道理的，但它实际上是在模拟混合和ANDORANDOR. 例如，请 2 个人从 1 到 10 分的范围内说出他们对“外面很冷”的说法的同意程度是多少？如果他们都说 5，那么“外面很冷”这句话的真实性是 50%。

总结中的非二进制值

从这种非二进制值的角度来看，我们可以在选择运算符时捕捉实际逻辑并从头开始构建方程，但我们必须牢记数值行为。我们习惯于将逻辑视为离散（二进制）并将计算机处理视为离散，但非二进制逻辑正变得越来越普遍，并且可以帮助使离散逻辑难以解决的问题更容易/可能解决。你需要考虑价值观在这个地区是如何相互作用的，以及如何将它们转化为有意义的东西。

于 2017-10-09T21:04:36.990 回答
6

嗯嗯嗯嗯嗯…………

它不是那么简单。

为了对 XOR（我们称之为 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

线性异或公式

最后，让我们把所有东西放在一起。这是您的 XOR 公式，仅使用线性约束。

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”条件。

于 2010-07-25T06:02:55.497 回答
5

你可以做类似的事情：

(a + b) % 2
于 2010-03-05T08:55:35.487 回答
0

绝对（A+B-1）。如果它不做 abs，那么 (A+B-1)*(A+B-1) 应该做。

于 2010-06-17T16:24:00.697 回答
0

异或是线性函数，但关于布尔函数的“线性”定义与多项式函数不同。您将不得不查看您的lp_solve库的文档以查看它是否能够处理线性布尔函数。从我所读到的，我不怀疑它可以。

编辑：在进一步研究了使用的单纯形算法之后lp_solve，我相当肯定你不能做你想做的事情。

于 2010-03-06T00:47:15.177 回答
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

战俘（2,3）=> 2 2 2

地板(1.6594565)=1 或地板(4562.21)=4562

于 2020-12-12T20:57:04.670 回答