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*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因子XOR
将XOR定义为(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还允许其他方程式在计算上等同于上述方程式.例如...
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
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.
关于非二进制值和模糊区域的思考
实际的代数XOR方程a + b - ab(1 + a + b - ab)比诸如x + y - 2xy和(x-y)²的计算等效二元方程要复杂得多.这意味着什么，这种增加的复杂性是否有任何价值?
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条件进行建模(请记住，当AND条件不存在时，OR可以由+进行建模，因此求和通常是OR).如果您正在查看一致性和度量标准，则平均值是有意义的，但是它实际上是在模拟AND和OR的混合体.例如，请两个人以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屋！
