用异或操作符交换数组在Python中不起作用

Question

我试图在Python中编写快速排序代码(请参阅问题末尾的完整代码)，并且在分区函数中，我应该交换数组的两个元素(称为x)。我使用以下代码进行基于异或操作符的交换:

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

我知道它应该工作，因为异或运算符(即x^x=0)是无效的，我已经在Java和C中做过一百万次了，没有任何问题。我的问题是:为什么它不能在Python中工作?当x[i] == x[j](可能是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

Answer 1

至于为什么它不起作用，这真的不重要¹，因为你不应该首先使用这样的代码，特别是当Python为你提供了完美的'原子交换'功能时:

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

我一直认为，所有的程序都应该首先优化可读性，只有在有明确的需求和明显的好处的情况下才会对性能或存储进行改进(除了一些非常小的数据环境，比如一些嵌入式系统，我从来没有看到过异或技巧)。

即使在没有提供这个漂亮特性的语言中，使用临时变量也会更容易读，而且可能更快:

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

---

¹然而，如果你真的想知道为什么它不起作用，那是因为这个技巧对于交换两个不同的变量是可以的，但是当你使用相同的变量时就不那么好了，当你试图交换x[i]和x[j]时，当i等于j。

它在功能上等同于下面的代码，添加了print语句，这样您就可以看到整个代码在哪里崩溃了:

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

将其与两个不同的变量进行对比，效果良好:

>>> 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

问题是，这个技巧是通过在两个变量之间逐渐传递信息来工作的(类似于狐狸/鹅/豆子的谜题)。当它是相同的变量时，第一步与其说是传递信息，不如说是销毁信息。

Python的'原子交换'和使用临时变量都可以完全避免这个问题。

Answer 2

我正在回顾这个事实，例如，您可以像下面这样表示xor:

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

所以，基本上，如果你用b替换a，哇!xDD你会得到的，零。