XOR 的数学(算术)表示

Question

在过去的 5 个小时里，我一直在寻找答案。尽管我找到了很多答案，但它们并没有以任何方式提供帮助。

我基本上要寻找的是任何 32 位无符号整数的按位异或运算符的数学、算术唯一表示。

尽管这听起来很简单，但没有人(至少看起来如此)设法找到这个问题的答案。

我希望我们能集思广益，共同找到解决方案。

谢谢。

Answer 1

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条件将始终为零 - 从维恩图的角度来看，这意味着没有重叠。在这种情况下，我们可以写 OR = a + b , 自 a*b = 0对于 a & b 的所有值。

2-Factor 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 - 2abXOR (二进制)= 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)...)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
可以扩展这些相同的方法以允许 k 个条件中的任何 n 个数字符合条件。
例如，在三个变量 a、b 和 c 中，如果您愿意接受任何两个条件，那么您需要 a&b 或 a&c 或 b&c。这可以从复合逻辑进行算术建模...... (a && b) || (a && c) || (b && c) ...并应用我们的翻译...
1 - (1-ab)(1-ac)(1-bc)...
这可以扩展到 k 个条件中的任意 n 个。有一种变量和指数组合的模式，但这会变得很长；但是，您可以通过忽略二进制上下文的幂来简化。确切的模式取决于 n 与 k 的关系。对于 n = k-1，其中 k 是要测试的条件总数，结果如下:
c1 + c2 + c3 ... ck - n*∏
其中 c1 到 ck 都是 n 变量组合。
例如，如果满足 4 个条件中的 3 个，则为真
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)² .这有什么意义吗，这种增加的复杂性有什么值(value)吗？
显然，为此，您必须关心离散点 (0,0)、(0,1)、(1,0) 和 (1,1) 之外的十进制值。为什么这会很重要？有时您想放宽离散问题的整数约束。在这种情况下，您必须查看用于将逻辑运算符转换为方程的前提。
在将 boolean 逻辑转换为算术时，您的基本构建块是 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在 boolean 逻辑中，当涉及到集合时， 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 条件不存在时， + 可以由 AND 建模，因此求和的特征是 OR )。如果您查看一致性和测量值，则平均值是有意义的，但它实际上是对 AND 的混合建模。和 OR .例如，请 2 个人从 1 到 10 的范围内说出他们对“外面很冷”这句话的同意程度如何？如果他们都说 5，那么“外面很冷”这句话的真实性是 50%。
非二进制值摘要
从这种非二进制值的角度来看，我们可以在我们选择运算符时捕捉实际逻辑并从头开始构建方程，但我们必须牢记数值行为。我们习惯于将逻辑视为离散(二进制)并将计算机处理视为离散，但非二进制逻辑正变得越来越普遍，并且可以帮助使离散逻辑难以解决的问题更容易/可能解决。您需要考虑值(value)观如何在该地区相互作用以及如何将它们转化为有意义的东西。