What is the XOR operator evaluating when switching the int values of two variables?

Question

Possible Duplicate:
How does XOR variable swapping work?

I found a solution to switching the values of two variables, without creating a third variable, which is as follows:

x ^= y;
y ^= x;
x ^= y;

This is using the exculsive-or operator ("XOR"), in a way other than boolean (I'm assuming it's bitwise?). Having learned some Discrete Mathematics recently, I can understand the usage of the XOR operator with a truth-table:

.......................
    x  y  (x XOR y)
.......................
    T  T      F
    T  F      T
    F  T      T
    F  F      F

The expression (x XOR y) evaluates to false when both variables are equivalent, and to true otherwise. But WTF when the values are not boolean?

Anyway, if I set x and y equal to int values instead of boolean values, the operations are not very straightforward. So, for example let x = 3, and y = 5:

public class SwitchValues
{
    // instance methods
    public void SwitchBoolean(boolean x, boolean y)
    {
        System.out.println("The variable \"x\" is initially: " + x + ".\n" +
            "The variable \"y\" is initially: " + y + ".");
        x ^= y;
        System.out.println("x ^= y is equal to: " + x + ".");
        y ^= x;
        System.out.println("y ^= x is equal to: " + y + ".");
        x ^= y;
        System.out.println("x ^= y is now equal to: " + x + ".");

        System.out.println("The variable \"x\" is now: " + x + ".\n" +
            "The variable \"y\" is now: " + y + ".\n");
    } // end of SwitchBoolean

    public void SwitchInts(int x, int y)
    {
        System.out.println("The variable \"x\" is initially: " + x + ".\n" +
            "The variable \"y\" is initially: " + y + ".");
        x ^= y;
        System.out.println("x ^= y is equal to: " + x + ".");
        y ^= x;
        System.out.println("y ^= x is equal to: " + y + ".");
        x ^= y;
        System.out.println("x ^= y is now equal to: " + x + ".");

        System.out.println("The variable \"x\" is now: " + x + ".\n" +
            "The variable \"y\" is now: " + y + ".\n");
    } // end of SwitchInts

    // main method
    public static void main(String[] args)
    {
        SwitchValues obj = new SwitchValues();

        obj.SwitchBoolean(true, false);
        obj.SwitchInts(3, 5);

    } // end of main method
} // end of class SwitchValues

... and the results printed out for the int values are as follows:

The variable "x" is initially: 3.
The variable "y" is initially: 5.
x ^= y is equal to: 6.
y ^= x is equal to: 3.
x ^= y is now equal to: 5.
The variable "x" is now: 5.
The variable "y" is now: 3.

Welcome back to the old days of assembly programming (where I think this trick was actually used to minimize register usage)... Out of curiosity: you do not intend to use this anywhere in real code? PS: This is IMHO somewhat related to XORed doubly linked lists, perhaps you find this interesting: http://en.wikipedia.org/wiki/XOR_linked_list. — Axel, Sep 21 '12 at 06:43
Interesting about the assembly programming @Axel. This XOR variable swap thing is mentioned on a number of blogs as being a relevant interview question, but upon looking into this I see that it is somewhat obscure and not very intuitive. I think I'd rather just use a third variable to do the 2 variable swap thing, because that is much easier to read. So, further down the rabbit hole though, I am now interested in learning how to convert ints into bits, and what usage that may have. How relevant is such binary conversion though? — Ian Campbell, Sep 22 '12 at 06:34

score 4 · Answer 1 · answered Sep 21 '12 at 06:33

This is how the operations works. First we will write your numbers in binary:

3 = 011, 5 = 101

Now, when we xor them we got a number which represent which bits are different between the two original numbers.

011 xor 101 => 110 which is 6 in decimal.

Now we take the second number and xor with the difference we just got

101 xor 110 => 011 (3 in decimal) and we get the difference between these numbers and we are back with the original first number. Now we again take this new number and xor it with the difference we originally got

011 xor 110 => 101 (5 decimal) and we have gotten back the original second number.

On XOR Swap wiki you can see a clearer description and also reasoning why this is slower than using a temporary variable on most modern architectures and compilers.

score 3 · Answer 2 · answered Sep 21 '12 at 06:12

3

XOR when applied to a numeric type is a bit-by-bit exclusive or. So you can take your original truth table and apply it to each of the bits in parallel. That should help understand what's happening.

answered Sep 21 '12 at 06:12

Larry Osterman

16,086
32
60

And yes, I know this is a somewhat terse answer, sorry about that. – Larry Osterman Sep 21 '12 at 06:13
Ha that's ok, thanks for the help @Larry! So how exactly does the number 3 for example break down to bits in parallel? What value is 3 evaluated as in bits? – Ian Campbell Sep 21 '12 at 06:15
1

The number 3 is 0x0011. (3 = 2^1+2^0). The number 14 would be 0x1110 (14 = 8+4+2 = 2^3+2^2+2+1). – Larry Osterman Sep 21 '12 at 22:08

Robert Kühne · Accepted Answer · 2012-09-21T06:41:32.887

3

Actually you gave the answer yourself. You assumed xor on int is bitwise and thats correct. Transform the numbers to bit representation and then apply the xor bit by bit.

3 is 11 in binary. 5 is 101 in binary

011
101
--- xor
110

110 is 6 in decimal.

If you want to know how to calculate the binary represantation of a number you should look up Horner's method. Its quite easy to do.

edited Sep 21 '12 at 06:41

answered Sep 21 '12 at 06:17

Robert Kühne

898
1
12
33

Ok thanks @Sponiro, but why does x in `x ^= y` equal to 6 when `x = 3` and `y = 5`? What bitwise numbers do x and y become to evaluate to 6? – Ian Campbell Sep 21 '12 at 06:25
1

I have added an example for you. – Robert Kühne Sep 21 '12 at 06:41
Thanks @Sponiro for the clear example! I will look into this "**Horner's method**". – Ian Campbell Sep 21 '12 at 17:10

What is the XOR operator evaluating when switching the int values of two variables?

3 Answers3