Explain using xor to find two non-duplicate integers in an array

Question

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

There is a solution using 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*/
  }
}

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.

Answer 1

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

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.

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)

Let's say the groups are

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

and

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

About

set_bit_no = xor & ~(xor-1);

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. If right most bit was zero it would be set to 1 and exit
2. Reset rightmost bit to zero and try to add 1 to next bit (step 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 anding, 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)

Answer 2

The simple way to explain here is that when you do a^b then only those bit positions are set that have different values in a from b. So if you group elements in the array with their values at particular set bit in a^b then a and b will be in separate groups as xor-ing the group will cancel out others and the result of two groups will be a and b.

Example :-

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

Answer 3

This algorithm would only work if and only if

1) elements are non-zero
2) contains no more than 2 non-repeating integers. If only 1
   non-repeating, one of the result (x or y) will be 0.
3) the repeated numbers occurs in pairs (ie. 2,4,6....)

If 0 is a possible number, then you can't differentiate between an answer found or no answer.

By XORing all the elements, this gives the difference between the 2 non-repeating integers (ie. 4 ^ 6 in your example). This is because all the other elements would be repeating (ie. even amount of times) and in XOR, they cancel themselves out. It is important to note that XOR is commutative (ie. order doesn't matter a^b = b^a)

Now the set_bit_no. This just stores the right most set bit or xor. Why the right most? Because it is easy to get I guess. But any set bit would do. The set bits in xor variable contains the bits where it is different between 4 and 6.

100 ^ 110 = 010

The second bit is 1 because that's the only bit different between 4 and 6. Similarly the difference between 3 and 8

0011 ^ 1000 = 1011

which shows 4th, 2nd and 1st bit are different between 3 and 8.

The reason to get the set bit and use that in the if condition is to make sure the answers (4 and 6) is written to different variable (x or y). Why does this work? Because the set bit guarantees that the 2 answers will contain different values at that bit position.

if(arr[i] & set_bit_no)

Answer 4

When you xor two equal values, they cancel out. This allows to reveal the non-repeating pair.

XOR(aabbccddeeffgh) = XOR(gh) = ...1...

Knowing any bit on which g and h differ allows to set g and h aside in two subsets:

...0... => XOR(aabbcceeg) = g

...1... => XOR(ddffh) = h