XOR 的数学(算术)表示 [英] Mathematical (Arithmetic) representation of XOR
问题描述
过去 5 个小时我一直在寻找答案.尽管我找到了很多答案，但它们没有任何帮助.
I have spent the last 5 hours searching for an answer. Even though I have found many answers they have not helped in any way.
我主要寻找的是任何 32 位无符号整数的按位 XOR 运算符的数学、仅算术表示.
What I am basically looking for is a mathematical, arithmetic only representation of the bitwise XOR operator for any 32bit unsigned integers.
尽管这听起来很简单，但没有人(至少看起来如此)设法找到这个问题的答案.
Even though this sounds really simple, nobody (at least it seems so) has managed to find an answer to this question.
希望我们能集思广益，共同寻找解决办法.
I hope we can brainstorm, and find a solution together.
谢谢.
推荐答案
异或任意数字输入
a + b - ab(1 + a + b - ab)
XOR 二进制输入
a + b - 2ab 或 (a-b)²
推导
基本逻辑运算符
NOT = (1-x)
AND = x*y
我们可以从这些运营商那里得到...
From those operators we can get...
OR = (1-(1-a)(1-b)) = a + b - ab
注意:如果 a 和 b 互斥，那么它们的 and 条件将始终为零 - 从维恩图的角度来看，这意味着没有重叠.在这种情况下，我们可以写成 OR = a + b，因为对于 a & 的所有值都有 a*b = 0.b.
Note: If a and b are mutually exclusive then their and condition will always be zero - from a Venn diagram perspective, this means there is no overlap. In that case, we could write OR = a + b, since a*b = 0 for all values of a & b.
2 因子异或
定义异或为(a OR B) AND (NOT (a AND b)):
(a OR B) -->(a + b - ab)
(NOT (a AND b)) -->(1 - ab)
AND这些条件加在一起得到...
AND these conditions together to get...
(a + b - ab)(1 - ab) = a + b - ab(1 + a + b - ab)
计算替代方案
如果输入值是二进制的，则可以忽略幂项以得出简化的计算等效形式.
If the input values are binary, then powers terms can be ignored to arrive at simplified computationally equivalent forms.
a + b - ab(1 + a + b - ab) = a + b - ab - a²b - ab² + a²b²
如果 x 是二进制的(1 或 0)，那么我们可以忽略幂，因为 1² = 1 和 0² = 0...
If x is binary (either 1 or 0), then we can disregard powers since 1² = 1 and 0² = 0...
a + b - ab - a²b - ab² + a²b² -- 移除权力 --> a + b - 2ab
XOR (二进制) = a + b - 2ab
二进制还允许其他方程在计算上与上述方程等效.比如……
Binary also allows other equations to be computationally equivalent to the one above. For instance...
给定 (a-b)² = a² + b² - 2ab
如果输入是二进制的，我们可以忽略幂，所以...
If input is binary we can ignore powers, so...
a² + b² - 2ab -- 移除权力 --> a + b - 2ab
允许我们写...
XOR (二进制) = (a-b)²
多因素异或
XOR = (1 - A*B*C...)(1 - (1-A)(1-B)(1-C)...)
Excel VBA 示例...
Excel VBA example...
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 个条件为真.
These same methods can be extended to allow for any n number out of k conditions to qualify as true.
例如，在 a、b 和 c 三个变量中，如果您愿意接受任何两个条件，那么您需要 a&b 或 a&c 或 b&c.这可以从复合逻辑算术建模...
For instance, out of three variables a, b, and c, if you're willing to accept any two conditions, then you want a&b or a&c or b&c. This can be arithmetically modeled from the composite logic...
<代码>(a && b) ||(a & & c) ||(b & & c) ...
并应用我们的翻译...
and applying our translations...
1 - (1-ab)(1-ac)(1-bc)...
1 - (1-ab)(1-ac)(1-bc)...
这可以扩展到 k 个条件中的任意 n 个.有一种变量和指数组合的模式，但这会变得很长；但是，您可以通过忽略二进制上下文的幂来简化.确切的模式取决于 n 与 k 的关系.对于n = k-1，其中k是被测试条件的总数，结果如下:
This can be extended to any n number out of k conditions. There is a pattern of variable and exponent combinations, but this gets very long; however, you can simplify by ignoring powers for a binary context. The exact pattern is dependent on how n relates to k. For n = k-1, where k is the total number of conditions being tested, the result is as follows:
c1 + c2 + c3 ... ck - n*∏
c1 + c2 + c3 ... ck - n*∏
其中 c1 到 ck 都是 n 变量组合.
Where c1 through ck are all n-variable combinations.
例如，如果满足 4 个条件中的 3 个，则为 true
For instance, true if 3 of 4 conditions met would be
abc + abe + ace + bce - 3abce
abc + abe + ace + bce - 3abce
这完全合乎逻辑，因为我们得到的是 AND 条件的加法 OR 减去重叠的 AND 条件.
This makes perfect logical sense since what we have is the additive OR of AND conditions minus the overlapping AND condition.
如果您开始查看 n = k-2、k-3 等.模式会变得更加复杂，因为我们要减去更多重叠.如果这完全扩展到 n = 1 的最小值，那么我们将得到一个常规的 OR 条件.
If you begin looking at n = k-2, k-3, etc. The pattern becomes more complicated because we have more overlaps to subtract out. If this is fully extended to the smallest value of n = 1, then we arrive at nothing more than a regular OR condition.
思考非二进制值和模糊区域
实际的代数异或方程 a + b - ab(1 + a + b - ab) 比计算等效的二进制方程(如 x + y - 2xy)复杂得多代码> 和 (xy)².这是否意味着什么?这种增加的复杂性有什么价值吗?
The actual algebraic XOR equation a + b - ab(1 + a + b - ab) is much more complicated than the computationally equivalent binary equations like x + y - 2xy and (x-y)². Does this mean anything, and is there any value to this added complexity?
显然，为此，您必须关心离散点 (0,0)、(0,1)、(1,0) 和 (1,1) 之外的十进制值.为什么这会很重要?有时您想放松离散问题的整数约束.在这种情况下，您必须查看用于将逻辑运算符转换为方程式的前提.
Obviously, for this to matter, you'd have to care about the decimal values outside of the discrete points (0,0), (0,1), (1,0), and (1,1). Why would this ever matter? Sometimes you want to relax the integer constraint for a discrete problem. In that case, you have to look at the premises used to convert logical operators to equations.
在将布尔逻辑转换为算术时，您的基本构建块是 AND 和 NOT 运算符，您可以使用它们构建 OR 和 XOR.
When it comes to translating Boolean logic into arithmetic, your basic building blocks are the AND and NOT operators, with which you can build both OR and XOR.
OR = (1-(1-a)(1-b)(1-c)...)
XOR = (1 - a*b*c...)(1 - (1-a)(1-b)(1-c)...)
因此，如果您正在考虑小数区域，那么值得考虑我们如何定义这些运算符以及它们在该区域中的行为方式.
So if you're thinking about the decimal region, then it's worth thinking about how we defined these operators and how they behave in that region.
NOT
我们将 NOT 表示为 1-x.显然，这个简单的方程适用于 0 和 1 的二进制值，但真正酷的是它还为 0 到 1 之间的值提供了小数或百分比补码.这很有用，因为 NOT在布尔逻辑中也称为Compliment，当涉及到集合时，NOT指的是当前集合之外的所有内容.
We expressed NOT as 1-x. Obviously, this simple equation works for binary values of 0 and 1, but the thing that's really cool about it is that it also provides the fractional or percent-wise compliment for values between 0 to 1. This is useful since NOT is also known as the Compliment in Boolean logic, and when it comes to sets, NOT refers to everything outside of the current set.
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%.
We expressed AND as x*y. Once again, obviously it works for 0 and 1, but its effect is a little more arbitrary for values between 0 to 1 where multiplication results in partial truths (decimal values) diminishing each other. It's possible to imagine that you would want to model truth as being averaged or accumulative in this region. For instance, if two conditions are hypothetically half true, is the AND condition only a quarter true (0.5 * 0.5), or is it entirely true (0.5 + 0.5 = 1), or does it remain half true ((0.5 + 0.5) / 2)? As it turns out, the quarter truth is actually true for conditions that are entirely discrete and the partial truth represents probability. For instance, will you flip tails (binary condition, 50% probability) both now AND again a second time? Answer is 0.5 * 0.5 = 0.25, or 25% true. Accumulation doesn't really make sense because it's basically modeling an OR condition (remember OR can be modeled by + when the AND condition is not present, so summation is characteristically OR). The average makes sense if you're looking at agreement and measurements, but it's really modeling a hybrid of AND and OR. For instance, ask 2 people to say on a scale of 1 to 10 how much do they agree with the statement "It is cold outside"? If they both say 5, then the truth of the statement "It is cold outside" is 50%.
总结中的非二进制值
从这种非二进制值的角度来看，我们可以在选择运算符时捕捉实际逻辑并从头开始构建方程，但我们必须牢记数值行为.我们习惯于将逻辑视为离散(二进制)并将计算机处理视为离散，但非二进制逻辑正变得越来越普遍，并且可以帮助使离散逻辑难以解决的问题更容易/可能解决.您需要考虑该地区的价值观如何相互作用，以及如何将它们转化为有意义的东西.
The take away from this look at non-binary values is that we can capture actual logic in our choice of operators and construct equations from the ground up, but we have to keep in mind numerical behavior. We are used to thinking about logic as discrete (binary) and computer processing as discrete, but non-binary logic is becoming more and more common and can help make problems that are difficult with discrete logic easier/possible to solve. You'll need to give thought to how values interact in this region and how to translate them into something meaningful.
这篇关于XOR 的数学(算术)表示的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
