无辅助空间交换值

最近每天一直在刷算法题，经常遇到一个常见场景：需要实现两个变量值的交换。我习惯性地采用最常规的方法来完成这一需求，即创建一个临时变量来暂存其中一个变量的值，随后完成交换。

int a = 100, b = 200;
int temp = a;
a = b;
b = temp;

然而，这种方法引入了一个额外的变量 temp，从而占用了额外的辅助空间。我开始思考，是否存在无需额外空间就能完成交换的方法，以及实现这一目的的具体方式有多少种。

简单加减法

一个直观的思路是，直接赋值会导致一个变量中存储的值丢失，这正是该需求中的核心问题。解决问题的关键在于，用一个变量去存储两个变量的特征。我们可以尝试通过简单的加减法来构造解决方案，如下所示：

由此，我们可以只通过两个空间把原来的 a 和 b 变量都表示出来，也就是不需要额外分配辅助空间，代码如下：

int a = 100, b = 200;
a = a - b;
// 目前: a = 原a - 原b, b = 原b
b = a + b;
// 目前: a = 原a - 原b, b = 原a
a = b - a;
// a = 原b, b = 原a

这种方法在 a 和 b的数值处于一定范围内时能够正常运行，但如果它们都是较大的值，就需要警惕计算过程中可能发生的溢出风险。

相关内容详见：

位运算（异或）

鉴于加减法实现可能改变原始数值的范围，并引发溢出问题，我们开始思考是否能在尽可能不改变原数值范围的前提下，存储两个变量的特征。这时，我们可以考虑利用位运算中的异或运算性质，以及异或运算的交换律。如下所示：

int a = 100, b = 200;
a ^= b;
b ^= a;
a ^= b;

通过连续的三个异或操作，我们可以优雅地完成数值的交换，而无需引入额外的空间。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。