Swapping array with the XOR operator doesn’t work in Python

Question

I was trying to code Quicksort in Python (see the full code at the end of the question) and in the partition function I am supposed to swap two elements of an array (call it x). I am using the following code for swapping based on the xor operator:

x[i]^=x[j]
x[j]^=x[i]
x[i]^=x[j]

I know that it should work because of the nilpotence of the xor operator (i.e. x^x=0) and I have done it like a million times in Java and in C without any problem. My question is: why doesn’t it work in Python? It seems that it is not working when x[i] == x[j] (maybe i = j?).

x = [2,4,3,5,2,5,46,2,5,6,2,5]
print x
def part(a,b):
  global x
  i = a
  for j in range(a,b):
    if x[j]<=x[b]:
      x[i]^=x[j]#t = x[i]
      x[j]^=x[i]#x[i] = x[j]
      x[i]^=x[j]#x[j]=t
      i = i+1
  r = x[i]
  x[i]=x[b]
  x[b]=r
  return i
def quick(y,z):
  if z-y<=0:
    return
  p = part(y,z)
  quick(y,p-1)
  quick(p+1,z)
quick(0,len(x)-1)
print x

So what is your question? Are you getting wrong output? If so you should include that in the question. — Anand S Kumar, Aug 26 '15 at 04:59
Those 3 lines do work, so the problem is somewhere else. But as paxdiablo said in his answer, you shouldn't be swapping like that. — Cyphase, Aug 26 '15 at 05:03
@AnandSKumar Thanks for asking. My question is why it does not work. If i use the xor swap i get [0, 0, 0, 0, 0, 0, 0, 2, 5, 5, 6, 46] and if i use the commented code i get [2, 2, 2, 2, 3, 4, 5, 5, 5, 5, 6, 46] — user16117, Aug 26 '15 at 05:04
@Cyphase Thanks for replying, it is there the problem. I use the commented swapping and it works. — user16117, Aug 26 '15 at 05:06
@user16117, that's very strange; I'm not running your exact code, but `d=[1,2]; d[0]^=d[1];d[1]^=d[0];d[0]^=d[1]` works for me; `d` will be `[2,1]`. — Cyphase, Aug 26 '15 at 05:12
@user16117, ah, I think it is because `i == j`, as you mentioned it might be. — Cyphase, Aug 26 '15 at 05:12

score 4 · Accepted Answer · edited May 23 '17 at 11:43

4

As to why it doesn't work, it really shouldn't matter¹, because you shouldn't be using code like that in the first place, especially when Python gives you a perfectly good 'atomic swap' capability:

x[i], x[j] = x[j], x[i]

It's always been my opinion that all programs should be initially optimised for readability first and only have performance or storage improvements imposed if there's a clear need and a clear benefit (neither of which I've ever seen for the XOR trick outside some incredibly small data environments like some embedded systems).

Even in languages that don't provide that nifty feature, it's more readable and probably faster to use a temporary variable:

tmp = x[i]
x[i] = x[j]
x[j] = tmp

¹ However, if you really want to know why it's not working, it's because that trick is okay for swapping two distinct variables, but not so well when you use it with the same variable, which is what you'll be doing when you try to swap x[i] with x[j] when i is equal to j.

It's functionally equivalent to the following, with print statements added so you can see where the whole thing falls apart:

>>> a = 42
>>> a ^= a ; print(a)
0
>>> a ^= a ; print(a)
0
>>> a ^= a ; print(a)
0

Contrast that with two distinct variables, which works okay:

>>> a = 314159; b = 271828; print(a,b)
314159 271828

>>> a ^= b; print(a,b)
61179 271828

>>> b ^= a; print(a,b)
61179 314159

>>> a ^= b; print(a,b)
271828 314159

The problem is that the trick works by transferring information between the two variables gradually (similar to the fox/goose/beans puzzle). When it's the same variable, the first step doesn't so much transfer information as it does destroy it.

Both Python's 'atomic swap' and use of a temporary variable will avoid this problem completely.

edited May 23 '17 at 11:43

Community

1
1

answered Aug 26 '15 at 04:59

paxdiablo

854,327
234
1,573
1,953

Yes, your last update for now, it is really what is about the question, so, why can we explain that behavior? it's weird, doesn't it? – Jonathan Prieto-Cubides Aug 26 '15 at 05:07
Thanks for answering paxdiablo. Why it should not matter? I am not a native python coder and i am not used to those expressions. I get it works like that and i am thankful about the knowledge but, for me, it matters why/how things works and why/how they do not. – user16117 Aug 26 '15 at 05:10
@user16117 If you take `xor` for any number with same number, it will give you a zero. Then how can you reproduce same number from zero? – niyasc Aug 26 '15 at 05:11
@niyasc Ah 0k, i get it now. I was using exactly the same variable. Thanks :) – user16117 Aug 26 '15 at 05:12
1

@niyasc, the problem isn't that the numbers are the same, it's that `x[i]` and `x[j]` are referring to the same variable. `x[i]` can be equal to `x[j]`, as long as `i` is not equal to `j`. – Cyphase Aug 26 '15 at 05:14
@niyasc, yea, `x ^ x == 0`, but try doing `a = 42; b = 42; a ^= b; b ^= a; a ^= b`. It works; meaning, `(a, b) == (42, 42)`. – Cyphase Aug 26 '15 at 05:17
@Cyphase; Ok I got it. – niyasc Aug 26 '15 at 05:18

score 1 · Answer 2 · answered Aug 26 '15 at 05:13

1

I was reviewing this fact, and for example, you could express the xor like the following expression:

a xor b = (a or b) - (a & b)

So, basically, if you replace a by b, Whoa! xDD You'll get it, zero.

answered Aug 26 '15 at 05:13

Jonathan Prieto-Cubides

2,577
2
18
17

Swapping array with the XOR operator doesn’t work in Python

2 Answers2