How does Xor work in swapping values?

Question

Here is the original code:

public static String reverseString(String s){       
    if(s == null) return "";        
    char[] rev = s.toCharArray();
    int i = 0, j = s.length() - 1;
    while(i < j) {
        rev[i] ^= rev[j];
        rev[j] ^= rev[i];
        rev[i++] ^= rev[j--];           
    }       
    return String.valueOf(rev); 
}

My question is how does Xor work in swapping character values here, and why is rev[i++]^=rev[j--] needed here?

Answer 1

The code is equivalent to

    rev[i] ^= rev[j];
    rev[j] ^= rev[i];
    rev[i] ^= rev[j];           
    i++;  j--;

The last part is just needed to increment i and decrement j for the next loop iteration.

As to why x ^= y; y ^= x; x ^= y works to swap the values, I don't know why, but you can see that it works on 1-bit values by look at all four possibilities:

 start   after x^=y  after y^=x   after x^=y
x    y     x   y       x   y        x   y
0    0     0   0       0   0        0   0
0    1     1   1       1   0        1   0
1    0     1   0       1   1        0   1
1    1     0   1       0   1        1   1

So you can see that in all cases, the x and y bits are swapped. When the statements are applied to larger integers, the ^ operator works on all bits in parallel, so the end result is that every pair of bits is swapped, i.e. the entire values are swapped.

Answer 2

XOR operator has this very unique operator that it acts as inequality detector meaning only when the two bits differ result will be 1 else result is 0.

Now take this for example say in A^B, ith bit 1, this means that ith bit of A and B differ. Meaning one of them is 1 and the other is 0.

Now when we do this (A^B)^B , if the ith bit in B was 0, what we will get is 1 since 1^0 = 1, which is equal to ith bit in A and (A^B)^A = 0, which is ith bit in B.

Similarly,When ith bit is B is 1 and in A is 0, again swapping occurs.

Same logic applies to when ith bit in A^B is 0. You can veryify it very easily.

Its easy to see how the swapping is occurring, When you xor the original number with A^B, you get the other number, because swapping happens for each of the respective bits