c#使用按位XOR进行交换

Question

void swap(ref int x, ref int y)
{       x = x ^ y;   y = y ^ x;   x = x ^ y;  }

我正在学习按位异或.这种交换是如何发生的？这让我大吃一惊.这个方法应该交换X和Y的内容,但我不明白AT ALL会发生什么？

Answer 1

谨防.这种方法有一个非常讨厌的属性.它被用于其中一项Underhanded C Contest参赛作品.它会愉快地工作......直到有一天有人尝试交换两个数组元素a [i]和[j]之类的东西,而不保证i!= j.

当两个引用都引用相同的变量时,此方法将其归零.

Answer 2

维基百科对Swap-By-XOR算法有很好的解释.

该算法有效的形式证明有点涉及,并且需要使用二进制数的数学属性.

但是在简化形式中,我们可以将二进制值的每个位分开,因为XOR操作独立地作用于每个位.因此,足以证明这适用于1位值,因为通过归纳我们可以证明它适用于任何长度的二进制值.为这些操作构建一个合适的真值表非常简单,所以我把它排除在外.

XOR交换不是唯一可能的"创造性"交换算法.使用算术运算可以获得类似的结果:

void Swap( ref int x, ref int y )
{
  x = x + y; 
  y = x - y;
  x = x - y; 
}

从实际角度来看,这是一种在大多数情况下应该避免的技术.正如您自己认识到的那样,这种方法的逻辑并不是立即显而易见的,它可能导致可维护性和可扩展性问题......其中最重要的是Swap( ref x, ref x )不会做方法名称所暗示的事实(它会将值清零) , 事实上).

Answer 3

只需一次看一下,一次一步.

x|y -> x = x ^ y x|y -> y = y ^ x x|y -> x = x ^ x x|y
0|0              0|0              0|0              0|0
0|1              1|1              1|0              1|0
1|0              1|0              1|1              0|1
1|1              0|1              0|1              1|1

在这里,您可以清楚地看到每种情况下的结果都是比特的交换.从这里可以清楚地看出为什么它在一般情况下起作用.更正式的解释是可能的.

任何时候你发现自己说"我完全不了解发生的事情"是一个强有力的迹象,你应该找到一种更清晰的方法来编写语义等效的代码.