解释这个函数中异或的用法

本文关键字：用法 函数 解释 | 更新日期: 2023-09-27 18:09:02

我看到了这个代码片段，它用于解决"在数组中找到一个没有重复的数字"的问题。今天早上我一直在看这个，但不能确切地确定它是如何做到的。

我不明白为什么k总是保留非重复的值。有人能解释一下这是怎么回事吗?

  static void Main(string[] args)
  {
     int[] list = { 3,6,9,12,3,6,9 };
     int k = 0;

     for (int i = 0; i < list.Length; i++)
     {
        k = k ^ list[i];
     }
     Console.WriteLine(k);
  }

解释这个函数中异或的用法

只有当只有一个数字不重复(或出现任何奇数次)而所有其他数字出现偶数次时才有效。

当你将一个数字与另一个数字相乘两次(或任何其他偶数次)，它会自我抵消，留下原来的数字。

这有点类似于"书呆子、运动员和储物柜"的问题，就"位翻转"而言，将某些位设置为设置而其他位不设置。

基本行为是A或B的工作原理类似于"(A或B) AND NOT (A AND B)"。所以，0^0=0 1^0 = 1，但1^1 =0(不像OR)现在，你从K上的0开始(没有设置任何位)，然后将它与字面值3(作为一个字节)的位为00000011进行异或，并将结果赋值给K。最后K得到00000011，因为当K为0时，在字面值3上设置的位都没有在K上设置。现在，如果您再次将K与字面量3进行异或，您将得到0，因为两个值之间的所有位都匹配，因此异或将在每个位上返回0。

此过程是可交换的，因此((((0 XOR 3) XOR 6) XOR 3) XOR 6)将给出与((((0 XOR 6) XOR 6) XOR 3) XOR 3)相同的结果(0)，或者几乎任何其他XORing 0与3和6的组合。

最终结果是，给定一个这些数字的列表，任何出现两次(或偶数次)的数字第一次被"xorin"到K，然后第二次被"xoror out"，使K的位设置为只出现一次的一个值;12 .

下面是完整问题的二进制演示(使用"nibbles"，因为我们没有任何超过16的值):

0000 0
^^^^ XOR
0011 3
---- =
0011 3
^^^^ XOR
0110 6
---- =
0101 5
^^^^ XOR
1001 9
---- =
1100 12
^^^^ XOR
1100 12
---- =
0000 0 <-this is coincidence; it'd work the same regardless of the unduped value
^^^^ XOR
0011 3
---- =
0011 3
^^^^ XOR
0110 6
---- =
0101 5
^^^^ XOR
1001 9
---- =
1100 12 <- QED

EDIT FROM COMMENTS:虽然这个答案对所问的特定问题起作用，但即使对问题进行最小的更改也会"破坏"这个实现，例如:

  • 算法对数字0 完全无响应;因此，该算法无法区分单个未配对值为零和根本没有未配对值之间的区别。
  • 该算法仅适用于对，而不适用于三元组。如果3出现了三次，仍然是一个"欺骗"，12仍然是正确的答案，这个算法实际上会返回15(1100 ^ 0011 == 1111)，甚至不在列表中。
  • 该算法仅在列表中只有一个非重复值时才有效;如果8和12都是预期返回的未配对值，则算法将返回这两个值的异或(1100 ^ 1000 == 0100 == 4)

可以开发一种有效的算法，除了原始情况外，还可以在所有这些情况下返回正确答案，但它可能不涉及异或。

任何数字都可以表示为位序列:

3 == 0...00011
6 == 0...00110
9 == 0...01001

如果对它们进行两次异或，位交换将相互抵消。

因此，如果一个单个数字在列表中出现一次(或奇数次)，那么它将是唯一留下"未取消"位的数字。

keith这是正确的，但这可能更容易遵循。

我能想到的最简单的解释与异或的四个属性有关:

  1. 0 XOR x = x，对于任意数字x
  2. x异或x = 0，对于任意数字x
  3. 异或是可交换的:x异或y = y异或x(这允许您重新安排一系列异或操作，无论您认为合适)
  4. XOR是关联的:(x XOR y) XOR z = x XOR (y XOR z)(这允许您以任何您认为合适的顺序评估XOR)

通过属性2和3，你可以重新排列你的输入列表，使所有重复项彼此相邻:

{3、6、9、12、3、6、9}->{3、3、6、6、9、9、12};

根据性质1和4，我们可以任意顺序对这些数进行异或，并且所有相同的数对都为0。在此之后，只有未重复的数字保持非零:

{0,0,0,12};

同样根据性质1，因为k从0开始，并且所有重复的数都必须异或变为0，所以只剩下12

这是因为XOR算子既是交换的又是结合的。这意味着您可以按任何顺序重新排列术语:

a ^ b ^ c == a ^ c ^ b == c ^ a ^ b == ... (etc.)

这适用于任何长度的序列。因此:

3 ^ 6 ^ 9 ^ 12 ^ 3 ^ 6 ^ 9 == (3 ^ 3) ^ (6 ^ 6) ^ (9 ^ 9) ^ 12

因为x ^ x == 0对于任何整数，这意味着你可以消除所有的对直到你得到0 ^ 12，它正好等于12 

a ^ a = 0
a ^ 0 = a
0 ^ a = a ^ 0
a = b ^ c
a = c ^ b
int[] list = { 3,6,9,12,3,6,9 };
k ^ 3
k ^ 6
k ^ 9
k ^ 12
k ^ 3
k ^ 6
k ^ 9
=
k ^ 3 // dupe
k ^ 3 
k ^ 6
k ^ 6
k ^ 9
k ^ 9
k ^ 12 // non-dupe
=
k ^ 12
=
0 ^ 12
=
12

当使用异或时，您必须记住您将使用位。换句话说，你只需要处理0和1。

异或的定义很简单:

0 XOR 0 -> 0
0 XOR 1 -> 1
1 XOR 1 -> 0
因此，如果您将此应用到您的代码中，并将3转换为0011，将6转换为0110，将9转换为1001，将12转换为1100，并像下面的示例一样对它们调用异或方法，您将最终得到1100表示值12。

: 

    0011
XOR
    0110
=
    0101 -> 5

这不是一个消除重复值的算法。这只是巧合，你得到了12。

您引用的代码实际上并不能解决问题。例如，在列表中放入三个12s，您将得到12，即使12被重复了两次。

异或的结果本质上是该位组合是奇数还是偶数。因此，如果列表包含奇数个12(无论是一个12还是一百零一个12)和偶数个其他数字，结果将始终是12。

更糟糕的是，如果列表包含多个不同数字的奇数，的结果值可能不是列表中的任何一个数字。例如，1个3加1个14等于13。这是因为异或操作的是位，而不是整数。对14 (1110b)和3 (0011b)进行异或运算得到13 (1101b)，因为异或运算将这两个数字之间的公共位置零。

实际解决问题的代码:

using System.Linq;
using System.Collections.Generic;
...
static void Main ( string[] args)
{
    int[] list = { 3,6,9,12,3,6,9 };
    int[] nonDupes = list
        .GroupBy(x => x)
        .Where(x => x.Count() == 1)
        .Select(x => x.Key)
        .ToArray();
    string output = string.Join(",", nonDupes);
    Console.WriteLine(output);
}
相关文章：