Unable to understand the logic behind `XOR` when finding the missing value in an array

Question

Here is the sample of code, which I got from here.

public class Snippet {
    private static final int[] ARRAY = {1, 4, 3, 18, 2, 8, 9, 6, 5, 10,
            11, 12, 13, 14, 15, 16, 17, 19, 0, 20};

    //{1,2,4,5,6,8,7,9,3}
    private int getMissingElem() {
        int XOR = 0;
        for (int i = 0; i < 20; i++) {
            if (ARRAY[i] != 0) {
                XOR ^= ARRAY[i];
            }
            XOR ^= (i + 1);
        }
        return XOR;
    }

    public static void main(String[] args) {
        Snippet s = new Snippet();
        System.out.println(s.getMissingElem());
    }
}

I just came to know about how, XOR have the values of missing elements of array.

https://www.roseindia.net/java/master-java/java-bitwise-xor.shtml << This explanation of java's XOR operator comes up by googling "Java XOR" — Davy M, May 11 '18 at 16:22
Possible duplicate of [What does the ^ (XOR) operator do?](https://stackoverflow.com/questions/14526584/what-does-the-xor-operator-do). This is for a question in python, but the XOR operator reacts the same in Python or Java. — Davy M, May 11 '18 at 16:25
Note your code only works if the array contains integers 1 to `ARRAY.length` except one integer becomes 0. — Ṃųỻịgǻňạcểơửṩ, May 11 '18 at 16:25
There is no need to check if the number is non-zero before xor. `a ^ 0 = a`. — Andy Turner, May 11 '18 at 16:41

Ṃųỻịgǻňạcểơửṩ · Answer 1 · 2018-05-11T17:10:09.213

XOR is bitwise. That means, given two integer values a, b, a ^ b has a 1 bit on that position if and only if either that position of a or b is 1, but not both.

The value 15 would be bitwise (with 8 bits here, for simplicity) represented as 00001111, whereas the value 60 would be bitwise represented as 00111100. Note that 15 ^ 60 would equal 00110011, because bits 2-3 equals 1 for both 15 only, and bits 6-7 equals 0 for 60 only.

For your question regarding finding the missing element of an array, it only works if the array otherwise contains integers 1 to ARRAY.length except that one integer is 0 (Precondition).

Notice that XOR is commutative and associative. That means, a ^ b == b ^ a, and (a ^ b) ^ c == a ^ (b ^ c) == a ^ b ^ c)
for all a, b, c. Also, if you XOR the same number twice, it cancels out, and the result becomes 0. Given any number n, n ^ n == 0, also a ^ n ^ n == a.
For all a, a ^ 0 == a because if this bit of a is 1, exactly one bit in that position is 1.

The logic behind your XOR-based solution is that in that for all numbers that are included in this array, you performed XOR on that same number twice, which cancels out. The only exception is the missing number n, as 0 ^ n equals n.

Suppose ARRAY is an array that meets the precondition:

Case 1: number m appears in array. The condition (*) for performing that XOR is when the loop is at the ith position such ARRAY[i] == m or at the m - 1th position. We have XOR ^ m when the condition is met the first time. As the loop progresses, the same condition is met again, so we have XOR ^ m ^ k ^ m == XOR ^ (m ^ m) ^ k == XOR ^ k, where k is the result of XORing the number between the first and second indices where the condition holds.
Case 2: number nis missing from the array. Notice that the previous condition (*) is met only once while you iterate through the loop. We therefore have XOR ^ n.
Because XOR is commutative and associative, we eventually get a final result of XOR == a^a^b^b^...^n...^x^x^y^y. Notice all the numbers except n is XORed twice as the loop finishes, we have (a^a)^(b^b)^...^n^(x^x)^(y^y) == 0^0^...^n^...0^0, hence we obtained n as desired.

Unable to understand the logic behind `XOR` when finding the missing value in an array

1 Answers1