I was studying on leetcode for an interview. There were a question about finding missing number unpaired in array. I solved it by using HashSet. But i saw the below solution which is more efficient than mine.My question is that what the logic XOR of a ^= nums[i] means ?
int a = 0;
for (int i = 0; i < nums.length; i++) {
a ^= nums[i];
}
return a;
You are now familiar by all answers that ^= is the XOR-and-becomes operator.
As x ^ x == 0 and x ^ 0 == x doing a cumulative XOR will remove twice occurring duplicates and the result will be the sole single occurrence.
3 ^ 5 ^ 3 ^ 7 ^ 5 = (3 ^ 3) ^ (5 ^ 5) ^ 7 = 0 ^ 0 ^ 7 = 7
3 6 5 2 7 <--- stepwise accumulated: 3=1+2, 5=1+4, 7=1+2+4
XOR is an interesting commutative and associative function "bit is different" as it does not loose information,
z = x ^ y => y = z ^ x
^ Bitwise exclusive OR or XOR
It will traverse over all the elements of your array and will perform XOR operation over all the elements.It is a form of compound assignment in java.
a ^= nums[i]
which is equivalent to
a = a ^ nums[i]
The ^ operator is the bitwise exclusive OR.
And of course, a ^= b is equivalent to a = a ^ b.
As for what "bitwise exclusive OR" means, see e.g. Wikipedia:
The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1.
Bitwise XOR operator.
a ^= nums[i] is the shorthand notation.
You can write it as a = a ^ nums[i]
int a = 0;
for (int i = 0; i < nums.length; i++) {
a = a ^ nums[i];
}
return a;
^ is the bitwise XOR operator:
A | B | A XOR B
--+---+--------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
In Java, Compound Assignments are a shorter way to apply arithmetic (or bitwise operation), and to assign the value to the variable on the left-hand side. So:
a ^= nums[i];
is equivalent to:
a = a ^ nums[i];
We take advantage of the fact that XOR of two equal numbers cancels each other, and solve the problem by iterating through the array's elements and XOR them with each other (with an initial value of 0).