CODEWITHSUNDEEP
javaarrays
Bryan Mcneil
Bryan Mcneil

Reputation: 395

JAVA - How does the bitwise exclusive OR assignment operator work in this given solution

I recently was doing some coding challenges and this was one of the problems.

A non-empty zero-indexed array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired. Find the unpaired value. For example, given array A: A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9 the function should return 7.

After finishing my own, I came across this solution.

public int solution(int[] A) {
  int r = 0;
  for(int i=0;i<A.length;i++)
    r ^=A[i];

  return r;
}

I was amazed at this code. I have never seen the exclusive OR assignment operator before and was wondering how this solution works. If someone could walk me through this simple code and explain how it works that would be wonderful.

Upvotes: 7

Views: 531

Answers (2)

user8885515
user8885515

Reputation:

xor ^ between two same numbers result in zero, for a binary system 

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

The same applies to any system, in your example, binary representation of 9 is 1001, so xor ^ between 9 and 9 is

 1001
 1001
 ----
 0000
 ----

So in your example the (9^9)^(9^9) makes a zero and (3^3) makes a zero and you are left with 0^7 which is 7

Upvotes: 1

Adrian Shum
Adrian Shum

Reputation: 40056

In brief, A ^ B ^ B will give you back A. The two ^Bs does not need to be consecutive: As long as you have XORed same value twice, it clear out the effect. In your question, as values are in pairs, so normally same value will be XORed twice, which gives no effect in the final value, except that un-paired value. So the final result will simply be 0 ^ thatUnPairedValue, which is simply thatUnPairedValue.

Upvotes: 9

Related Questions