使用xor解释在数组中找到两个非重复的整数

Question

鉴于[1,1,4,5,5,6]我们可以找到4并6成为非重复整数.

有一个解决方案使用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

如果我们有重复的数字对,它们就不会向xor结果添加任何内容,因为它们的xor将为零.只有一对不同的数字会为xor结果添加非零位.

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 x或d中,唯一的设置位是c和d中不同的位.假设第3位在c xor d中设置.这意味着如果位3在c中为0,则在d中为1,反之亦然.

因此,如果我们将所有数字分成2组,则包含所有数字的第3位为0,而其他第3位为1,则c和d肯定会转到不同的组.并且所有相同数字对将成为同一组.(比特3在a和0都是1或者两者都是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的位位,因此只有这个位将在表达式xor&〜(xor-1)中设置

Answer 2

这里解释的简单方法是，当您a^b这样做时，只会设置 a 和 b 中具有不同值的那些位位置。因此，如果将数组中的元素以其特定设置位的值分组，则a^ba 和 b 将分在不同的组中，因为异或该组将抵消其他组，并且两个组的结果将是 a 和 b。

例子 ：-

a = 4 
b = 6 
a^b = 2

Set_bit_pos = 1

Arr = [1,1,4,5,5,6]

Grouping according to bit no 1 

x = [6] where bit1 is 1 

y = [4,1,1,5,5] where bit1 is 0

Xoring 

x = 6 

y = 4^1^1^5^5 = 4