0

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.

Zabuzard
  • 25,064
  • 8
  • 58
  • 82
JoshO
  • 3
  • 1
  • 1
    Do you understand what XOR is? – Thorbjørn Ravn Andersen Jul 24 '19 at 21:51
  • XOR is a bitwise operation. In order to understand it, you need to translate all the integers into their binary representation (2-complement) and then apply bit-wise XOR. You will not be able to understand this if you keep looking at decimal values. – Zabuzard Jul 24 '19 at 21:53
  • 1
    The compiler isn't doing any math there; it's transforming this into bytecode, which [the JVM executes](https://docs.oracle.com/javase/specs/jvms/se10/html/jvms-6.html#jvms-6.5.ixor). – chrylis -cautiouslyoptimistic- Jul 24 '19 at 21:53
  • To understand this, use a website like https://www.exploringbinary.com/twos-complement-converter/ (make sure to set the number of bits to 32, as thats what Java ints use). Translate all your integers to this binary representation, lookup how XOR works and then you will understand. – Zabuzard Jul 24 '19 at 21:57
  • So I was on the right track - I do understand what XOR is doing to this array as a whole and how the compiler arrives at its' final answer, I was just trying to understand what the compiler is actually computing/executing at a particular point in time. Curiosity just getting the best of me. Thank you everyone for the help - useful links! – JoshO Jul 25 '19 at 14:19

1 Answers1

1

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.

rgettman
  • 176,041
  • 30
  • 275
  • 357
  • Thank you! I was just racking my brain trying to understand the intermediary steps the compiler was actually performing to get from 21 to -22 in this example. I understand how XOR works as a whole, as in how this code arrives at its' final answer, I was just hoping I could understand intermediary steps - sounds like the compiler is converting these steps into byte-code and either isn't necessarily important or is something that would be too difficult to understand and isn't worth the time investment. – JoshO Jul 25 '19 at 14:17