CODEWITHSUNDEEP
javaarraysxor
JoshO
JoshO

Reputation: 3

What is the compiler doing step-by-step when searching for integers occurring an odd number of times?

You are given an array with random integers. All integers occur an even amount of time throughout the array except for one integer. You are able to use ^ (or XOR) to single out which integer occurs an odd number of times in the array

I do not understand what the compiler is doing step-by-step when running through this code.

Looking at addition/subtraction/XOR principles for comparison of two binary numbers.

int[] a = {20,1,-1,2,-2,3,3,20,5,5,1,2,4,20,4,-1,-2};

int xor = 0;
for (int i = 0; i < a.length; i++){
           xor ^= a[i];
}
return xor;

After running the above code 20 will be shown as the integer that occurs an odd number of times (3 times as opposed to all other integers occurring 2 times)

If you debug and step through the code step-by-step, for example, you will store 20, then after hitting 1, it will become 21, then after hitting -1, it will become -22. I do not understand what math the compiler is performing at the 21 -> -22 step.

Upvotes: 0

Views: 48

Answers (1)

rgettman
rgettman

Reputation: 178303

The most important thing to recognize about this code is that it doesn't matter what the value of xor is in the middle of the loop. You don't need to know that one of the intermediate values of xor is -22. It only matters that it represents that the numbers 20, 1, and -1 are in the "odd" state, and anything else is in the "even" state (including a count of 0).

As you may know, using the XOR operator a second time on the same number reverses the first operation. That is, (a ^ b) ^ b is a. This fact (along with the commutativity of the XOR operator) is used to store the number(s) that currently have an odd count.

Because we are given that there is only one number with an odd number of occurrences, using the XOR operator on all of them means that all of the numbers with an even number of occurrences will reverse themselves out of the value xor. The only value that won't reverse itself out is the number that you're searching for.

All that the compiler is doing is generating bytecode to use the ^ (XOR) operator to manipulate the variable xor. It is the algorithm designer who is using this operator as part of the algorithm to determine which integer occurs an odd number of times.

Upvotes: 1

Related Questions