我尝试在Python中实现XOR交换算法。
x,y= 10,20
x,y,x = x^y,x^y,x^y
print('%s , %s'%(x,y))
输出：
30 , 30
我对 Python 并不陌生，但是我无法解释这个输出。输出应该是 20,10。
底层发生了什么？
Python中的XOR交换算法？
3
- Pratik Deoghare
4
6Python在执行这个操作时并不会原地修改整数，因此即使你像这样使用3个步骤，也无法避免使用额外的临时存储，正如你所期望的那样。 - John La Rooy
你的意思是在Python中不使用任何额外的存储空间就无法实现异或排序吗？ - Pratik Deoghare
@Matthew Flaschen：请将您的答案发布为答案，而不是评论。请删除评论并插入答案，以便我们可以适当地投票支持答案。 - S.Lott
应该使用异或交换而不是排序，对吧？ - MAK
6个回答
17
首先创建一个由x^y, x^y和x^y组成的元组。然后将该元组解包到x，y和x中，导致两者都绑定到x^y的结果。
避免头痛，请按照Pythonic的方式操作：
x, y = y, x
- Ignacio Vazquez-Abrams
2
x, y = y, x 在底层是如何运作的？ - Anirban Nag 'tintinmj'@Anirban 右侧被评估为对象的元组，然后分配给左侧名称的元组。 - wjandrea
11
虽然像其他答案所说，最好使用x, y = y, x的方法，但是如果你对创建和拆分元组过敏，你仍然可以通过连续进行异或操作来做到...只要是连续的，而不是同时的！
>>> x = 1234
>>> y = 3421
>>> x ^= y
>>> y ^= x
>>> x ^= y
>>> print x
3421
>>> print y
1234
xor-swap技巧的关键在于进行三次连续的异或操作，即按照顺序执行三条^=语句，就像这个片段中所示。当然，这在实践中没有任何意义，但如果你真的很想尝试，它在Python和其他任何地方都是可以正常工作的;-)。
- Alex Martelli
19
1@Matthew：关键是它只需要两个名称/句柄/框/寄存器/任何东西，而不像通常的三人MHTP算法 :-) - John Machin
3在Python中，每个整数操作都可能“创建一个新对象”，也可能不创建：这完全取决于实现，因为这严格是性能问题（对语义没有任何影响！），应用程序代码无法控制它。例如，小的整数可能会被缓存（因此对于小于某个阈值的整数，实际上不会创建新对象，完全取决于Python实现），如果实现可以证明对其的最后引用已被删除，则可能重用现有对象的内存等。你的确切保证是不适当的（更多...） - Alex Martelli
2@Matthew，针对你的纠缠细节：“不使用额外空间作为临时变量”--这里没有使用额外的变量（可能有额外的对象——它们不是变量而是不可变的——但绝对没有变量，所以我们没问题！）。并且：如果一个对象是“执行环境中数据存储区域”，那么一旦对它的最后一个引用被删除，Python 对象就不再是对象了，因为这意味着它不在执行环境中——它是可用于底层实现下方使用（或不使用）的死亡位。 - Alex Martelli
2@Matthew，标识符的可用性与编译器使对象可访问的能力无关：例如，实现可以决定
__x在任何范围内可见，并返回指针以允许访问该对象（根据C++ std（2003）17.4.3.2.1，C std（1999）7.1.3，“保留给实现任何用途”，因此该用法是可以的），因此这些对象完全可以“在执行环境中”，与您的说法相反。同样，CPU（视为其机器语言的实现）可以合法地分配额外的对象“在执行环境中”。 - Alex Martelli2所有这些的重点是，你所谓的Python不能进行异或交换的“证明”（因为如果值为1234和3421，则给定实现可能会分配额外的对象——尽管如果值为10和20，例如在CPython中，自许多版本以来就不会这样做）是完全错误的：在执行环境中，“可能分配额外的对象”（取决于Python、C、任何机器语言的实现），因此显然不能用于“推断”任何东西，与你的愚蠢主张相反。 - Alex Martelli
显示剩余14条评论
4
你需要逐字逐句地转录“算法”这一行。
>>> 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
>>>
您需要阅读维基百科文章的其余部分，该文章解释了正确实现会阻止并行操作，并且整个想法在现代计算机架构上基本上是无用的。
- John Machin
1
1除了学习目的外，整个想法基本上是毫无用处的。这种技巧会让任何阅读代码的人感到头痛。 - Adrien Plisson
2
XOR交换算法只有在您有两个可变对象的指针时才有意义。a和b是对不可变整数的两个引用。
编辑（按照要求从评论中移动并扩展）：
Python整数是不可变的。因此，每次使用XOR“修改”一个整数时，都会分配新的存储空间（或重用，例如进行内部处理）。这与（例如C）根本不同，其中swap更改值而不分配新内存。换句话说，XOR交换在C99意义上（“数据存储区域在执行环境中，其内容可以表示值”）或Python意义上都不会创建新对象。如here所述，真正的XOR交换可以“在不使用临时变量的情况下交换变量a和b的值”。
或经验性地说：
在这种情况下，我们看到解释器（2.6.4）似乎正在对整数进行内部化处理，因此x最终具有y最初的内存地址。但主要问题是交换需要至少一个分配（137452836），并且x和y不能始终保留相同的内存地址。
在C中：
"给予："
这是一个真正的异或交换，因此 x 和 y 总是保持相同的内存位置，没有临时变量。
编辑（按照要求从评论中移动并扩展）：
Python整数是不可变的。因此，每次使用XOR“修改”一个整数时，都会分配新的存储空间（或重用，例如进行内部处理）。这与（例如C）根本不同，其中swap更改值而不分配新内存。换句话说，XOR交换在C99意义上（“数据存储区域在执行环境中，其内容可以表示值”）或Python意义上都不会创建新对象。如here所述，真正的XOR交换可以“在不使用临时变量的情况下交换变量a和b的值”。
或经验性地说：
>>> 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
在这种情况下，我们看到解释器（2.6.4）似乎正在对整数进行内部化处理，因此x最终具有y最初的内存地址。但主要问题是交换需要至少一个分配（137452836），并且x和y不能始终保留相同的内存地址。
在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);
"给予："
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
这是一个真正的异或交换，因此 x 和 y 总是保持相同的内存位置，没有临时变量。
- Matthew Flaschen
3
3正如我的回答所示，使用不可变整数的引用与使用可变对象的指针一样合理（即并不是很合理）。真正关键的是时间上的先后顺序与同时评估！ - Alex Martelli
1我觉得我们对这个交换过程的实现和XOR算法本身的目的产生了混淆。当你不想使用额外的存储空间时，你可以选择使用XOR实现，但这样做绝对需要可变数据的原因是没有意义的。所以，即使可以证明使用XOR可以正确工作 - 就像你的回答中所示，Alex - 也没有太大意义，因为你可以只使用新值作为临时值。 - Kylotan
1数学计算是正确的，但节省空间的交换目标并未实现。 - Mike Graham
1
你可以使用以下方法轻松地进行交换：
x, y = 10, 20 x, y = y, x print((x,y))
至于你看到的行为，我很确定那是因为整个右侧表达式被同时评估并分配给左侧，而在这种情况下x^y始终为30。
- durin42
0
你可以结合使用“元组交换”和“XOR交换”：x，y = x ^ x ^ y，x ^ y ^ y
Python：
x, y = 10, 20
print('Before swapping: x = %s, y = %s '%(x,y))
x, y = x ^ x ^ y, x ^ y ^ y
print('After swapping: x = %s, y = %s '%(x,y))
或者
x, y = 10, 20
print('Before swapping: x = %s, y = %s '%(x,y))
print('After swapping: x = %s, y = %s '%(x ^ x ^ y, x ^ y ^ y))
输出：
Before swapping: x = 10 , y = 20
After swapping: x = 20 , y = 10
- u-betcha
1
1这只是
x, y = y, x 带有一些冗余的异或操作；x ^ x 和 y ^ y 都等于零。 - kaya3网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接