How does Xor determine which int is different?

user_14772532 0
Viewed 51

here's the problem that's being solved

"You're given three integers, a, b and c. It is guaranteed that two of these integers are equal to each other. What is the value of the third integer? "

here's the code

int extraNumber(int a, int b, int c) {
    return a^b^c;
}

I understand the caret " ^ " mean XOR, which means "this OR that, but not both" in simple terms but what I fail to understand is how this code determines which int is different from the others, or perhaps I don't understand XOR properly?

logical-operators java
3 Answers

Look at it at bit-level:

  • A value x xor-ed with itself will always result in 0 (check: 1^1=0 and 0^0=0).
  • A value y xor-ed with 0 will always result in the same value y (check: 1^0=1 and 0^0=0).

Since it holds true for individual bits and int are just 32 bits, the same rules hold true for full int values.

Therefore the method doesn't need to figure out "which values are different" because a value xor-ed with itself with cancel out to 0 and xor-ing the "remaining" value with 0 will just return the same value.

user_403420

Joachim's answer is correct, and to add bit more details with an example, let's say you pass three arguments (2, 3, 2) to your method, the bit level format usually ...16 8 4 2 1 starts from right side, as per truth table for XOR,

https://en.wikipedia.org/wiki/XOR_gate

private int extraNumber(int a, int b, int c) {
        // 8421  -> this is bit level, 
        // let's compare a^b

        // 0010 = 2 (a value)
        // 0011 = 3 (b value, sum of 2nd + 1st bits)

        // 0001 = 1 (after XOR with a^b)
        // 0010 = 2 (c value)

        // 0011 = 3 (the final output)

        return a^b^c;
    }
user_21829200

you can also check the intermediate results, by breaking up the code a^b^c into two statements.

for example

int a = 0b1010_1010;
int b = 0b1010_1010; //same value as b

int c = 0b1111_0000; //the remaining item

//CASE 1 (xor the different values first)
int d = a^c; //  results in 0b0101_1010
int e = d^b; // results in 0b1111_0000 (the answer) 


//CASE 2 (xor the same values first)
int d = a^b; // results in 0b0000_0000
int e = d^c; // results in 0b1111_0000 (the answer)
user_9088210
Related