CODEWITHSUNDEEP
javafunctional-programmingbitwise-operatorsbitxor
Yone
Yone

Reputation: 2134

How does xor give different number in two arrays‽

I have answered the following kata: Lost number in number sequence. The description is:

"An ordered sequence of numbers from 1 to N is given. One number might have deleted from it, then the remaining numbers were mixed. Find the number that was deleted.

Example:

The starting array sequence is [1,2,3,4,5,6,7,8,9]
The mixed array with one deleted number is [3,2,4,6,7,8,1,9]
Your function should return the int 5.

If no number was deleted from the array and no difference with it, your function should return the int 0.

Note that N may be 1 or less (in the latter case, the first array will be [])."

I have written a simple answer:

import java.util.*;

  public class Kata {
    public static int findDeletedNumber (int[] arr, int[] mixedArr) {  
      Arrays.sort(mixedArr);
      for(int i = 0; i < arr.length; i++){
        try{
          if(arr[i] != mixedArr[i]){
            return arr[i];
          }
        }catch(ArrayIndexOutOfBoundsException e) {
          return arr[i];
        }
      }
      return 0;
    }
}

I was reading other people's answers and I found one which I find very hard to understand deeply:

import java.util.Arrays;

public class Kata {
    public static int findDeletedNumber(int[] arr, int[] mixedArr) {
        return Arrays.stream(arr).reduce((a, b) -> a ^ b).orElse(0) ^ Arrays.stream(mixedArr).reduce((a, b) -> a ^ b).orElse(0);
    }
}

The link to the answer: https://www.codewars.com/kata/reviews/595be553429e11365c00006f/groups/59bef3a1eda42eb0bc001612

I would like to have some help, if anyone cares and have the patience to write an explanation and/or a trace, would be helpful. Currently I can see the answer but I do not understand it. 🤯

In addition I have tried to understand it by myself reading: What does the ^ operator do in Java? https://www.geeksforgeeks.org/bitwise-operators-in-java/

Upvotes: 2

Views: 225

Answers (1)

Eritrean
Eritrean

Reputation: 16498

Truth table of XOR (Exclusive-OR)

X   Y    result
0   0    0
0   1    1
1   0    1
1   1    0

What means X^Y? Let´s look at an example, 5^6

dec       bin

5     =  101
6     =  110
------------------ xor
3     =  011

XOR-ing two numbers is just converting the two numbers to binary and apply the rules in the truth table.

Looking at the table above, it is obvious that X^X = 0 for any integer X

5     =  101
5     =  101
------------------ xor
0     =  000

and X^0 = X

5     =  101
0     =  000
------------------ xor
5     =  101

Given your two arrays XOR-ing each element in both arrays and XOR-ing the result means something like 

(1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9) ^ (3 ^ 2 ^ 4 ^ 6 ^ 7 ^ 8 ^ 1 ^ 9)

and because X^Y = Y^X and X^Y^Z = (X^Y)^Z = X^(Y^Z) you can rearrange the above to

(1 ^ 1) ^ ( 2 ^ 2) ^ (3 ^ 3) ^ (4 ^ 4)  ^ (5) ^ (6 ^ 6) ^ (7 ^ 7) ^ (8 ^ 8) ^ (9 ^ 9)

everything cancels each other out except for the missing number, i.e 5.

Upvotes: 4

Related Questions