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

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 thema 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 themc = 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 thema 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 positivexor & ~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)

This algorithm would only work if and only if

1) elements are non-zero2) 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)

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 = 2Set_bit_pos = 1Arr = [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 0Xoring x = 6 y = 4^1^1^5^5 = 4