使用 XOR 运算符交换数组在 Python 中不起作用

Question

我试图在 Python 中编写快速排序代码（请参阅问题末尾的完整代码）并且在分区函数中我应该交换数组的两个元素（称之为 x).我正在使用以下代码基于 xor 运算符进行交换：

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

我知道它应该工作，因为 xor 运算符（即 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

至于为什么它不起作用，这真的不重要¹，因为你 shouldn't be using 一开始就这样编码，尤其是当Python给你一个非常好的'atomic swap'能力时：

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

我一直认为，所有程序最初都应该首先针对可读性进行优化，并且只有在有明确的需求和明显的好处（我都没有见过 XOR 技巧）时才对性能或存储进行改进在某些非常小的数据环境（例如某些嵌入式系统）之外）。

即使在不提供该漂亮功能的语言中，使用临时变量也更具可读性并且可能更快：

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

¹ 然而，如果你真的想知道为什么它不起作用，那是因为这个技巧可以交换两个 distinct 变量，但当您将它与 same 变量一起使用时效果不佳，这就是您尝试交换 [=14] 时将要执行的操作=] 与 x[j] 当 i 等于 j.

它在功能上等同于以下内容，添加了 print 语句，因此您可以看到整个事情在哪里崩溃：

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

将其与两个 distinct 变量进行对比，效果还不错：

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

问题是这个技巧是通过在两个变量之间逐渐传递信息来实现的（类似于 fox/goose/beans 谜题）。当它是 same 变量时，第一步与其说是传递信息，不如说是破坏信息。

Python的'atomic swap'和使用临时变量都可以完全避免这个问题。

Answer 2

我正在审查这个事实，例如，您可以像下面的表达式那样表达异或：

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

所以，基本上，如果将 a 替换为 b，哇！ xDD 你会得到它，零。

使用 XOR 运算符交换数组在 Python 中不起作用

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

python

xor