我已经花费了过去的5小时寻找答案。尽管我找到了许多答案，但它们并没有在任何方面帮助我。
我基本上正在寻找的是针对任何32位无符号整数的按位异或运算符的数学、仅涉及算术的表示。
尽管这听起来非常简单，但似乎没有人能够找到这个问题的答案。
我希望我们可以一起集思广益，找到解决方案。
谢谢。
XOR的数学（算术）表示方式
23
- user3170842
7
1可能是XOR使用数学运算符的重复问题。 - Matt Ball
7绝对不能有重复，因为链接的主题没有提供任何有用的信息。 - user3170842
@Pietu：那么为什么我可以用数学模拟位旋转？肯定有一种方法，直到被证明无法完成。据我所知，这还没有被证明。 - user3170842
按位旋转是二进制中乘法（和除法）执行的特殊情况，因为它与乘以/除以2相同。这也适用于十进制整数：如果将其向左旋转并添加0，则会发生什么？它将乘以10，即基数（在二进制中是2）。 - PurkkaKoodari
@user3170842，首先考虑如何使用系列求和来表示数字的位数。一旦您以该表示法获得了两个操作数，就可以使用'无用'答案中的方程式来计算每个单独位的异或。了解您尝试使用此方法的上下文可能会有所帮助，因为问题的性质通常驱动数学表示法的最佳选择。 - Dan Bryant
显示剩余2条评论
9个回答
36
对于0到1之间的任何数字输入进行异或运算，包括两端
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条件总是为零——从Venn图的角度来看，这意味着没有重叠。在这种情况下，我们可以写成OR = a + b，因为对于所有的a和b值，a*b = 0。
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)...)
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个条件中的k个条件都符合要求。
例如，在三个变量a、b和c中，如果您愿意接受任何两个条件，则需要a&b或a&c或b&c。这可以从复合逻辑中算术建模...
(a && b) || (a && c) || (b && c) ...
并应用我们的翻译...
1 - (1-ab)(1-ac)(1-bc)...
这可以扩展到任意n个中的k个条件。有一种变量和指数组合的模式，但这会变得非常冗长；但是，在二进制上下文中，您可以通过忽略幂来简化。确切的模式取决于n与k的关系。对于n = k-1，其中k是正在测试的所有条件的总数，结果如下：
c1 + c2 + c3 ... ck - n*∏
其中c1到ck都是n变量组合。
例如，如果满足4个条件中的3个，则为真
abc + abe + ace + bce - 3abce
这在逻辑上是完全合理的，因为我们拥有的是AND条件的加法OR减去重叠的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也被称为布尔逻辑中的补集，当涉及到集合时，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
2
2你的回答对我很重要。 - Land
1顶部的“XOR任何数字输入”这句话有点误导，因为您不能使用此公式对两个任意的32位值进行异或运算。将该方程应用于值3和5会产生98的结果，而不是按位异或它们所期望的6。 - Desty
1
"数学，仅算术表示"不是正确的术语。您要寻找的是一个从IxI到I（整数域）的函数。
您希望这个函数有哪些限制？只有线性代数吗？（+，-，*，/），那么无法模拟XOR运算符。
如果您接受一些非线性运算符，如Max() Sgn()等，则可以使用一些“更简单”的运算符来模拟XOR运算符。
您希望这个函数有哪些限制？只有线性代数吗？（+，-，*，/），那么无法模拟XOR运算符。
如果您接受一些非线性运算符，如Max() Sgn()等，则可以使用一些“更简单”的运算符来模拟XOR运算符。
- user3042724
2
FYI，数学家通常使用Z表示整数。 I有时表示无理数，尽管这种情况远不常见。 - Teepeemm
1@user3042724，为什么不可能？ - Grzegorz Adam Kowalski
1
考虑到 (a-b)(a-b) 很明显可以计算单个位的异或，您可以构建一个函数使用 floor 或 mod 算术运算符来拆分位，然后进行异或，最后求和以重新组合。 (a-b)(a-b) = a2 -2·a·b + b2，因此异或的一位会产生一个具有 3 项的多项式。
如果没有 floor 或 mod，不同的位会相互干扰，因此您只能查看将输入 a、b 视为单个值进行 多项式插值 的解决方案： a xor b = g(a · 232 + b) 该多项式有 264-1 项，但由于异或是可交换的，因此将对称于 a 和 b，因此您只需要计算一半的系数。我没有足够的空间为您写出它。
如果没有 floor 或 mod，不同的位会相互干扰，因此您只能查看将输入 a、b 视为单个值进行 多项式插值 的解决方案： a xor b = g(a · 232 + b) 该多项式有 264-1 项，但由于异或是可交换的，因此将对称于 a 和 b，因此您只需要计算一半的系数。我没有足够的空间为您写出它。
- Pete Kirkham
1
我无法找到32位无符号整数的解决方案，但我找到了一些关于2位整数的解决方案，我试图在我的Prolog程序中使用它们。其中一个解决方案（使用指数和模）在this StackOverflow question中描述，其他解决方案（一些不使用指数，纯代数）可以在this code repository on Github中找到：请参见不同的
对于2位无符号整数而言，最好的异或表示为：
使用+、-、*、/表示为Excel公式的解决方案（其中单元格从A2到A5，单元格从B1到E1包含数字0-4），要插入到单元格从A2到E5中：
xor0和o_xor0实现。对于2位无符号整数而言，最好的异或表示为：
xor(A,B) = (A + B*((-1)^A)) mod 4。使用+、-、*、/表示为Excel公式的解决方案（其中单元格从A2到A5，单元格从B1到E1包含数字0-4），要插入到单元格从A2到E5中：
(1-$A2)*(2-$A2)*(3-$A2)*($A2+B$1)/6 - $A2*(1-$A2)*(3-$A2)*($A2+B$1)/2 + $A2*(1-$A2)*(2-$A2)*($A2-B$1)/6 + $A2*(2-$A2)*(3-$A2)*($A2-B$1)/2 - B$1*(1-B$1)*(3-B$1)*$A2*(3-$A2)*(6-4*$A2)/2 + B$1*(1-B$1)*(2-B$1)*$A2*($A2-3)*(6-4*$A2)/6
- Grzegorz Adam Kowalski
1
可能可以将此解决方案调整和优化以适用于32位无符号整数。这很复杂并且使用了对数，但似乎是最通用的一种，因为它可以用于任何整数。此外，您需要检查它是否确实适用于所有数字组合。
- Grzegorz Adam Kowalski
0
OEIS（Online Encyclopedia of Integer Sequences）是离散算法师最好的朋友。专业技巧。
XOR是一种条件否定操作：
给定x XOR y，其中x，y ∈ 正整数，当且仅当x = 2**floor(log_2(y+1)) - 1时，x XOR y = NOT y；反之亦然，即对于x XOR y = NOT x。
在二进制中，对于2 - x和1 - x的模二余数运算分别得到x ∈ {0, 1}的XOR结果，意味着2 - x可用于计算x的身份，而1 - x可用于计算x的否定：
对于二：
10 - 01 = 01 同余于 1 模 2
10 - 00 = 10 同余于 0 模 2
对于一：
01 - 01 = 00 同余于 0 模 2
01 - 00 = 01 同余于 1 模 2
给定我们希望进行异或运算的 x 和 y，正如我们在上面已经展示的那样，异或是条件取反的操作；在第二个陈述中，我们给出了计算一个数字的恒等和逻辑取反的两个表达式。为了简化起见，我们将使用 x XOR y = NOT y。
在这种情况下，x 中对应于第 2^i 位数字为 1 意味着我们应该取反 y 中的第 2^i 位数字；而 x 中对应于第 2^i 位数字为 0 意味着我们应该计算 y 中对应位数字的恒等（即保持不变）。
在二进制中，数字2需要两个数字来表示，但在四进制中，数字2只需要一个数字，并且可以直接用二进制表示。
莫泽-德布鲁因序列（链接：https://oeis.org/A000695）是用四进制表示的正整数序列。以下是如何构造该序列的方法，给定一个正整数n（以二进制表示），并且a(n) | n ∈ positive integers表示该序列：
a(0) = 00
a(1) = 01
a(10) = 01 00
a(11) = 01 01
a(100) = 01 00 00
依此类推
这只是一种可能的纯数学定义之一（请参阅OEIS上的公式部分以获取该序列并找到合适的内容，但在撰写本文时，我对给定的闭式形式并不满意，因为我希望使用O(1)操作的闭式形式），然而，有一种简单的方法，它需要通过一个无限的01（或10）序列进行AND操作，这似乎是一个可行的线索，但在撰写本文时，我尚未弄清楚。如果有任何进展，我将在下面的新部分中介绍这个方法。
XOR是一种条件否定操作：
给定x XOR y，其中x，y ∈ 正整数，当且仅当x = 2**floor(log_2(y+1)) - 1时，x XOR y = NOT y；反之亦然，即对于x XOR y = NOT x。
在二进制中，对于2 - x和1 - x的模二余数运算分别得到x ∈ {0, 1}的XOR结果，意味着2 - x可用于计算x的身份，而1 - x可用于计算x的否定：
对于二：
10 - 01 = 01 同余于 1 模 2
10 - 00 = 10 同余于 0 模 2
对于一：
01 - 01 = 00 同余于 0 模 2
01 - 00 = 01 同余于 1 模 2
给定我们希望进行异或运算的 x 和 y，正如我们在上面已经展示的那样，异或是条件取反的操作；在第二个陈述中，我们给出了计算一个数字的恒等和逻辑取反的两个表达式。为了简化起见，我们将使用 x XOR y = NOT y。
在这种情况下，x 中对应于第 2^i 位数字为 1 意味着我们应该取反 y 中的第 2^i 位数字；而 x 中对应于第 2^i 位数字为 0 意味着我们应该计算 y 中对应位数字的恒等（即保持不变）。
在二进制中，数字2需要两个数字来表示，但在四进制中，数字2只需要一个数字，并且可以直接用二进制表示。
莫泽-德布鲁因序列（链接：https://oeis.org/A000695）是用四进制表示的正整数序列。以下是如何构造该序列的方法，给定一个正整数n（以二进制表示），并且a(n) | n ∈ positive integers表示该序列：
a(0) = 00
a(1) = 01
a(10) = 01 00
a(11) = 01 01
a(100) = 01 00 00
依此类推
NOT(x)等于-x，这是我们领域中所谓的“二进制补码有符号整数”的基础：NOT(x) = (2**floor(log_2(x)) - 1) - x。因此，对于所有的
x,y ∈ 正整数，令b(n)使得b(a(n)) = n，以下等式成立：
x XOR y = b(AND(a(x) + a((2**floor(log_2(x)) - 1) - x) - a(y)), a((2**floor(log_2(x)) - 1) - x))
这只是一种可能的纯数学定义之一（请参阅OEIS上的公式部分以获取该序列并找到合适的内容，但在撰写本文时，我对给定的闭式形式并不满意，因为我希望使用O(1)操作的闭式形式），然而，有一种简单的方法，它需要通过一个无限的01（或10）序列进行AND操作，这似乎是一个可行的线索，但在撰写本文时，我尚未弄清楚。如果有任何进展，我将在下面的新部分中介绍这个方法。
- AMDG
0
我认为这个关系可能有助于回答你的问题
A + B = (A XOR B ) + 2*(A.B)
- Visluck
1
这是一个等式：
A + B = (A XOR B) + 2 (A AND B)。A AND B 表示二进制加法中的进位位。A XOR B 在GF(2)中表示 A + B，如果我使用术语正确的话（这意味着对于A和B的每一位，求和并计算模2的余数）。这对于解决问题有所帮助，但并不是很大。 - undefined0
我确实意识到这是一个有关编程的老话题，但是这个问题值得回答，而且是可以使用算法解决的。与其详细说明它是如何工作的，不如用一个简单的例子（用C语言编写）来演示：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
typedef unsigned long
number;
number XOR(number a, number b)
{
number
result = 0,
/*
The following calculation just gives us the highest power of
two (and thus the most significant bit) for this data type.
*/
power = pow(2, (sizeof(number) * 8) - 1);
/*
Loop until no more bits are left to test...
*/
while(power != 0)
{
result *= 2;
/*
The != comparison works just like the XOR operation.
*/
if((power > a) != (power > b))
result += 1;
a %= power;
b %= power;
power /= 2;
}
return result;
}
int main()
{
srand(time(0));
for(;;)
{
number
a = rand(),
b = rand();
printf("a = %lu\n", a);
printf("b = %lu\n", b);
printf("a ^ b = %lu\n", a ^ b);
printf("XOR(a, b) = %lu\n", XOR(a, b));
getchar();
}
}
- Sir Galahad
-2
(a-b)*(a-b) 是正确的答案。唯一的答案？我想是这样的！
- jackiszhp
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接