How is XOR helping find the unique value?-CodePudding

I have a problem to writhe a function that finds the unique value from an array, i could not solve the problem but i asked someone to help, he provided the solution by using XOR(^), but could not explain for me to understand it. I know that XOR has the following table:

1 ^ 0 = 1
1 ^ 1 = 0
0 ^ 0 = 0
0 ^ 1 = 1

So, if the values are different XOR returns 1 or a non negative value in case of other numbers but I still don't get how this is helping me to solve this. Can someone please explain how the code below is working and how is it finding the unique value?

int xor = 0;
int index = 0;
    
while(index < arr.length) {
    xor = arr[index] ^ xor;
    index  ;
}
    
return xor;

CodePudding user response：

If all the elements of the array can be grouped as pairs of equal numbers, XORing each pair of numbers will result in 0. The order in which the elements are XORed doesn't matter.

For example, if the array is 4,5,4,5

xor = arr[0] ^ xor; // 0..0100 ^ 0..0000 = 0..0100
xor = arr[1] ^ xor; // 0..0101 ^ 0..0100 = 0..0001
xor = arr[2] ^ xor; // 0..0100 ^ 0..0001 = 0..0101
xor = arr[3] ^ xor; // 0..0101 ^ 0..0101 = 0..0000 = 0

If, on the other hand, all the elements of the array but one can be paired, after XORing all of them, only that one un-paired element will remain.

For example, if the array is 4,5,6,4,5

xor = arr[0] ^ xor; // 0..0100 ^ 0..0000 = 0..0100
xor = arr[1] ^ xor; // 0..0101 ^ 0..0100 = 0..0001
xor = arr[2] ^ xor; // 0..0110 ^ 0..0001 = 0..0111
xor = arr[3] ^ xor; // 0..0100 ^ 0..0111 = 0..0011
xor = arr[4] ^ xor; // 0..0101 ^ 0..0011 = 0..0110 = 6

CodePudding user response：

This work only when you have one unique value and even number of duplicate values.

Consider the following test case: 7 ^ 3 ^ 5 ^ 4 ^ 5 ^ 3 ^ 4 This can be rearranged as 7 ^ (3 ^ 3) ^ (4 ^ 4) ^ (5 ^ 5)

xor is commutative: A ^ B = B ^ A
xor is associative: (A ^ B) ^ C = A ^ (B ^ C)
xoring with zero does nothing: A ^ 0 = A
xoring something twice removes it: A ^ A = 0

Applying this rules on above test case gives 7 ^ 0 ^ 0 ^ 0 then 7 ^ 0 i.e 7

Refer this for more info about XOR