C#使用按位异或进行交换

Question

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

我正在学习按位异或运算。这种交换是如何发生的？它让我很困惑。这种方法应该交换X和Y的内容，但我完全不明白发生了什么。

- Alex Gordon

---

在纸上写下二进制的示例x和y值，并记录操作。 - Oded

保持这样，不要使用它。将来有人维护您的代码时也不会使用它。在 C++ 标签下可以找到几个关于此的线程，寻找投票下降的线程。否则，以 0 和 1 写出来以查看其工作情况。两位就足够了。 - Hans Passant

这是我在一年级计算机科学课上学到的交换技巧之一，当时只是出于兴趣而选修了这门课。在没有任何理由的情况下，我进行了这种微小的微优化，感觉自己很愚蠢，因为明显的替代方案（temp = x; x = y; y = temp;）清晰易懂得多，而且编译器也更容易进行优化。 - Joren

尝试使用swap(ref x, ref x)。惊喜！:-) - Rauhotz

这在60年代末70年代初编写的HLASM应用程序中是一种常见做法，即使大型机也几乎没有足够的内存来托管应用程序。使用XOR技术的好处是它使用更少的指令来交换寄存器或变量，因此需要更少的空间。我很不幸地成为维护这样一个程序的人，直到它被重写为Y2K的COBOL。我不认为现代系统有任何使用这种技术的必要性。 - bloudraak

Answer 1

注意。这个方法有一个非常非常糟糕的属性。它曾在“Underhanded C Contest”比赛中被使用过。它会开心地工作... 直到某一天有人尝试交换两个数组元素a[i]和a[j]，但没有确保i！=j。

当两个引用都指向同一个变量时，此方法将其归零。

- Rafał Dowgird

---

你的原则是正确的。Swap(ref x, ref x)会将变量x清零。在C/C++中，这种方法存在你所描述的缺陷。然而，在C#中，不可能通过引用传递数组元素，因此该特定情况实际上不会发生。 - LBushkin

@LBushkin：我认为你是错的。你不能通过引用传递索引器的输出，所以如果a是一个List，那么swap(ref a[0], ref a[0])将无法编译，但如果它是一个整数数组，则会编译（并执行）。 - Rafał Dowgird

Answer 2

维基百科对Swap-By-XOR algorithm有很好的解释。

该算法的形式证明有点复杂，需要使用二进制数的数学属性。

但是在简化形式中，我们可以将二进制值的每个位分开考虑，因为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 ) 不会执行该方法名称所暗示的操作（实际上它会将值归零）。

- LBushkin

Answer 3

只需要逐位和逐步查看它。

在处理IT技术时，一定要注意细节和步骤。

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

在这里，您可以清楚地看到每种情况下的结果都是位交换。从这里可以清楚地看出为什么它在一般情况下有效。更多正式的解释也是可能的。

每当您发现自己说“我完全不明白正在发生什么”时，这强烈表明您应该找到一种更清晰的方式来编写语义等效的代码。

- jason

---

你在那里有一个打字错误，最后一步是 x = x ^ y; 但表格条目当然是正确的.. :) - gilligan

Answer 4

在大多数现代架构（包括i686和x86_64）上，swap()可以使用单个CPU指令实现。因此，最好以编译器可以识别和转换的方式编写它，而不是试图进行微小优化，这样会使您的代码变得更慢和难以阅读。

- Krunch

Answer 5

首先看一下 XOR 的工作原理：

a | b | a^b
- - - - - -
0 | 0 | 0
1 | 0 | 1
0 | 1 | 1
1 | 1 | 0

XOR操作的结果是1或true，如果输入不同，则为0。如果输入相等，则为0。另一种看待它的方式是将其视为没有进位的加法，我将其表示为（+）：

x = x ^ y <=> x = x (+) y;
y = y ^ x <=> y = y (+) x;
x = x ^ y <=> x = x (+) y;

第一步：将在x中为0但在y中为1的所有位设置为1。现在在x中某些位是错误的，因为如果在x和y中一个位都是1，则会将它设置为0。其他位是正确的。 第二步：现在将在x中设置为1的相同位位置设置为y中的0（我们已经完成了y）。这样做的原因是x已经具有所有不同位设置为1的位，因此现在用x异或y基本上意味着：切换在x中设置为1的y位。我们现在已经完成了y :) 第三步：现在我们仍然需要将那些在第一步后已经被重置为0的原本设置为1的位在x中设置为1。怎么办？我们只需最后再次使用x XOR y，因为XOR的作用是什么？如果两个输入不同，则将位设置为1，这正是我们所需的。

如果您仍然对此感到困惑，则应将其绘制在纸上并播放以查看其工作方式和/或参考上面Jason制作的表格。

- gilligan