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;
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