c - 解释使用 xor 在数组中查找两个不重复的整数

Question

给定 [1,1,4,5,5,6] 我们可以找到 4 和 6 是非重复的整数。

有一个solution使用 XOR。

这里是作者提出的算法:

#include <stdio.h>
#include <stdlib.h>

/* This finction sets the values of *x and *y to nonr-epeating
 elements in an array arr[] of size n*/
void get2NonRepeatingNos(int arr[], int n, int *x, int *y)
{
  int xor = arr[0]; /* Will hold xor of all elements */
  int set_bit_no;  /* Will have only single set bit of xor */
  int i;
  *x = 0;
  *y = 0;

  /* Get the xor of all elements */
  for(i = 1; i < n; i++)
   xor ^= arr[i];

  /* Get the rightmost set bit in set_bit_no */
  set_bit_no = xor & ~(xor-1);

  /* Now divide elements in two sets by comparing rightmost set
   bit of xor with bit at same position in each element. */
  for(i = 0; i < n; i++)
  {
    if(arr[i] & set_bit_no)
     *x = *x ^ arr[i]; /*XOR of first set */
    else
     *y = *y ^ arr[i]; /*XOR of second set*/
  }
}

我对 4^6 之后的内容感到困惑。我对 set_bit_no 的工作原理(包括动机)以及之后的任何事情感到困惑。

有人可以尝试用更简单的英语方式解释它吗？谢谢。

Answer 1

如果我们重复一对数字，它们不会对异或结果添加任何内容，因为它们的异或将为零。只有一对不同的数字会将非零位添加到异或结果中。

a xor a = 0
[a, b, c, b, d, a]
a xor b xor c xor b xor d xor a = c xor d

现在在 c xor d 中，唯一设置的位是 c 和 d 中不同的位。假设第 3 位设置为 c xor d。这意味着如果第 3 位在 c 中为 0，则在 d 中将为 1，反之亦然。

所以如果我们把所有的数字分成2组，一个包含所有第3位的数字是0，另一个是第3位是1的，c和d肯定会分到不同的组。所有成对的相同数字都属于同一组。 (第 3 位要么在两个 a 上都为 1，要么在两个 a 上都为 0)

假设这些组是

[a c a] and [b d b]
xoring them
a xor c xor a = c (The first number)
b xor d xor b = d (The second number)

组的其他可能性是

[c] and [a b d b a]
xoring them
c = c (The first number)
a xor b xor d xor b xor a = d (The second number)

和

[a b c b a] and [d]
xoring them
a xor b xor c xor b xor a= c (The first number)
d = d (The second number)

关于

set_bit_no = xor & ~(xor-1);

如果输入数组由自然数组成，则xor为正xor & ~xor 为零(定义为所有位都反转)从 xor 中减去 1，

1. 如果最右边的位为零，它将被设置为 1 并退出
2. 将最右边的位重置为零并尝试将下一位加 1(步骤 1)

简而言之，所有最右边为 1 的位都将变为零(类似于 xor 反转)并且第一个(最右边)零位将变为 1(与 xor 相同)。现在，这个新设置的 1 位左边的所有位在 xor 和 ~(xor-1) 中都是不同的，所以它们将生成 0，这个新设置的 1 位右边的所有位在 xor 和 ~(xor- 1) 所以它们会生成 0。只有在 ~(xor-1) 中新设置 1 的位位置的位在这两种情况下都是 1，所以只有这个位会在表达式 xor & ~(xor-1)