说明使用XOR找到同一阵列中两个不重复的整数 [英] Explain using xor to find two non-duplicate integers in an array

问题描述

由于 [1,1,4,5,5,6] ，我们可以找到 4 和 6 是不重复的整数。

Given [1,1,4,5,5,6] we can find 4 and 6 to be the non-repeating integers.

有一个<一个href="http://www.geeksforgeeks.org/find-two-non-repeating-elements-in-an-array-of-repeating-elements/"相对=nofollow>解决方案使用 XOR 。

下面是提出笔者的算法：

Here is the algorithm proposed by the author:

#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 作品（包括动机）和任何之后。

I am confused as to what follows after 4^6. I am confused how the set_bit_no works (including the motivation) and whatever after that.

可有人试图解释它更简单的英语的方式？谢谢你。

Can someone try to explain it in more plain English manner? Thanks.

推荐答案

如果我们已经多次对数字，他们也不会添加任何东西到异或结果，作为其中的异或将为零。只有对不同数量将增加非零位异或结果。

If we have repeated pair of numbers, they would not add anything to xor results, as the xor of them would be zero. Only pair of different number would add non zero bits to xor result.

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异或D中，只有一组位是在c和d不同的位。 比方说，第3位是在C XOR D设置。这意味着，如果第3位是0在C这将是1 d或反之亦然。

Now in c xor d, the only set bits are the bits that are different in c and d. Let's say 3rd bit is set in c xor d. This means if bit 3 is 0 in c it would be 1 in d or vice versa.

因此​​，如果我们把所有数字在2基团，其中一个包含所有的数字与第3位是0，和其它，其中，位3是1，c和d肯定会去不同的组。而所有对同一号码会去同一个组。 （第3位是1上都有了或0这两个一）

So if we divide all numbers in 2 group, one which contains all numbers with bit 3 is 0, and other in which bit 3 is 1, c and d would definitely go to different groups. And all pairs of same numbers would go the same group. (Bit 3 is either 1 on both a or 0 in both a)

假设的群体

[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)

基团的其它可能性是

Other possibilities of groups are

[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为零（定义为所有位反转） 在减去1 XOR，

If input array was composed of natural numbers, xor would be positive xor & ~xor is zero (Definition as all bits are inverted) On subtracting 1 from xor,

1. 如果最右边的比特是零，将被设定为1和出口
2. 重置最右边的位为零，并尝试添加1到下一个位（第1步）

总之一切最右边位的分别为1将变为零（倒回类似XOR）和第（最右边）的零位将成为1（同XOR）。现在就结束，这个新设置的1比特的左所有位都在异或不同并〜（XOR-1），所以它们将产生0，所有位权这个新设置的1位是在这两个异或和零〜（xor- 1），这样他们就产生0。只有在位的位置1〜被新设置（XOR-1）位为1的两个的情况下，因此只有该位将在EX pression异或放大器上设置; 〜（XOR-1）

In short all rightmost bits that were 1 would become zero(inverted back similar to xor) and first (rightmost) zero bit would become 1(same as xor). Now on ending, all bits left of this newly set 1 bit are different in xor and ~(xor-1), so they would generate 0, all bits right to this newly set 1 bit are zero in both xor and ~(xor-1) so they would generate 0. Only bit at bit position where 1 was newly set in ~(xor-1) is 1 in both case, so only this bit would be set in expression xor & ~(xor-1)

这篇关于说明使用XOR找到同一阵列中两个不重复的整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！