使用异或运算符交换数组在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

- user16117

---

那么你的问题是什么？你得到错误的输出吗？如果是这样，你应该在问题中包含它。 - Anand S Kumar

那三行代码是有效的，所以问题出在其他地方。但正如paxdiablo在他的回答中所说，你不应该这样交换。 - Cyphase

@AnandSKumar 感谢您的提问。我的问题是为什么它不起作用。如果我使用异或交换，我会得到[0, 0, 0, 0, 0, 0, 0, 2, 5, 5, 6, 46]，而如果我使用已注释的代码，我会得到[2, 2, 2, 2, 3, 4, 5, 5, 5, 5, 6, 46]。 - user16117

@Cyphase 感谢您的回复，问题就在那里。我使用了注释掉的交换方法并且它有效。 - user16117

@user16117，这很奇怪；我没有运行你的确切代码，但是d=[1,2]; d[0]^=d[1];d[1]^=d[0];d[0]^=d[1]对我来说有效；d将会是[2,1]。 - Cyphase

@user16117，啊，我认为这可能是因为i == j，正如你所提到的那样。 - Cyphase

Answer 1

关于为什么它不起作用，实际上并不重要¹，因为您首先不应该使用那样的代码，尤其是当Python已经为您提供了完美的“原子交换”功能时：。

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

我一直认为所有程序应该最初优化可读性，只有在存在明确的需求和明显的益处时才会强制进行性能或存储改进（除了一些极小的数据环境，如某些嵌入式系统外，我从未见过XOR技巧的明确需求和益处）。

即使在不提供这个巧妙功能的语言中，使用临时变量更易读，可能更快：

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的“原子交换”和使用临时变量都可以完全避免这个问题。

- paxdiablo

---

是的，你现在的最后更新，确实是关于这个问题的，那么，为什么我们能解释这种行为呢？这很奇怪，不是吗？ - Jonathan Prieto-Cubides

如果你对任何数值使用“异或”操作符与同一个数进行运算，结果将会是零。那么如何从零中恢复出原数呢？ - niyasc

@niyasc，问题不在于数字相同，而是x[i]和x[j]引用的是同一个变量。只要i不等于j，x[i]可以等于x[j]。 - Cyphase

@niyasc，是的，x ^ x == 0，但试试执行 a = 42; b = 42; a ^= b; b ^= a; a ^= b。它可以工作；也就是说，(a, b) == (42, 42)。 - Cyphase

@Cyphase；好的，我明白了。 - niyasc

Answer 2

我正在审查这个事实，例如，你可以用以下表达式表示异或：

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

基本上，如果你用 b 替换 a，哇！xDD 你会得到零。

- Jonathan Prieto-Cubides