XOR swap algorithm in python?

Question

I tried to implement XOR swap in python.

x,y= 10,20

x,y,x = x^y,x^y,x^y

print('%s , %s'%(x,y))

OUTPUT:

30 , 30

I am not new to python but I am unable to explain this output. It should have been 20,10.

What is going on under the hood?

Answer 1

First, a tuple is created consisting of x^y, x^y and x^y. Then the tuple is unpacked into x, y, and x, causing both to be bound to the result of x^y.

Save yourself the headache and do it the Pythonic way:

x, y = y, x

Answer 2

You can do this swap easily using the following:

x, y = 10, 20
x, y = y, x
print((x,y))

As for the behavior you're seeing, I'm pretty sure that's because the entire RHS is evaluated and then assigned to the LHS at the same time, and x^y is always 30 in that case.

Answer 3

The XOR swap algorithm only makes sense when you have two pointers to mutable objects. a and b are two references to immutable ints.

EDIT (moving from comments as requested, and expanding):

Python integers are immutable. So every time you "modify" one using XOR, new storage will be allocated (or reused, e.g. for interning). This is fundamentally different from (e.g. C), where swap changes the value without allocating new memory. Put another way, XOR swap does not create new objects in either the C99 sense ("region of data storage in the execution environment, the contents of which can represent values") or the Python sense. As noted here, a true XOR swap can "exchange the values of the variables a and b without using extra space for a temporary variable."

Or empirically:

>>> x = 3
>>> y = 5
>>> print "x: ", x, ", id(x): ", id(x), "y: ", y, ", id(y): ", id(y)
x:  3 , id(x):  137452872 y:  5 , id(y):  137452848
>>> x ^= y
>>> print "x: ", x, ", id(x): ", id(x), "y: ", y, ", id(y): ", id(y)
x:  6 , id(x):  137452836 y:  5 , id(y):  137452848
>>> y ^= x
>>> print "x: ", x, ", id(x): ", id(x), "y: ", y, ", id(y): ", id(y)
x:  6 , id(x):  137452836 y:  3 , id(y):  137452872
>>> x ^= y
>>> print "x: ", x, ", id(x): ", id(x), "y: ", y, ", id(y): ", id(y)
x:  5 , id(x):  137452848 y:  3 , id(y):  137452872

In this case, we see that the interpreter (2.6.4) seems to be interning the integers, so x ends up with the memory address y originally had. But the main point is that the swap requires at least one allocation (137452836), and x and y don't retain the same memory address throughout.

In C:

int x = 3;
int y = 5;
printf("x: %d, &x: %p, y: %d, &y: %p\n", x, &x, y, &y);
x ^= y;
printf("x: %d, &x: %p, y: %d, &y: %p\n", x, &x, y, &y);
y ^= x;
printf("x: %d, &x: %p, y: %d, &y: %p\n", x, &x, y, &y);
x ^= y;
printf("x: %d, &x: %p, y: %d, &y: %p\n", x, &x, y, &y);

gives:

x: 3, &x: 0xbfd433ec, y: 5, &y: 0xbfd433e8
x: 6, &x: 0xbfd433ec, y: 5, &y: 0xbfd433e8
x: 6, &x: 0xbfd433ec, y: 3, &y: 0xbfd433e8
x: 5, &x: 0xbfd433ec, y: 3, &y: 0xbfd433e8

This is a real XOR swap, so x and y always maintain the same memory locations and there is no temporary.

Answer 4

While it's definitely best, as other answers say, to just x, y = y, x, if you're allergic to creating and unpacking tuples you can do it with successive x-oring... it just has to be successive, not simultaneous as you're doing!

>>> x = 1234
>>> y = 3421
>>> x ^= y
>>> y ^= x
>>> x ^= y
>>> print x
3421
>>> print y
1234

The key to the xor-swap trick is three successive xors, i.e. one after the other -- the three separate ^= statements, in this snippet. Of course, it makes no practical sense, but, if you're really keen on it, it does work, in Python like anywhere else;-).

Answer 5

You need to transcribe the "algorithm" line for line.

>>> x, y = 10, 20
>>> x = x ^ y; print x, y
30 20
>>> y = x ^ y; print x, y
30 10
>>> x = x ^ y; print x, y
20 10
>>>

You need to read the remainder of the Wikipedia article, which explains that correct implementation blocks parallel operations, and that the whole idea is pretty much useless (on modern computer architectures, at least).