c++ - 如果两个数字都指向同一位置，则在不使用额外空间的情况下交换两个数字不起作用？

Question

最近我遇到了这个问题，写一个函数来交换两个数字而不使用额外的空间？该函数可以有两种方式：

int swap ( int *a, int* b)
{
    *a = *a+*b;
    *b = *a-*b;
    *a = *a-*b;
}

另一种方式是异或运算：

int swap ( int *a, int* b)
{
    *a = *a^*b;
    *b = *a^*b;
    *a = *a^*b;
}

即使这两个函数都是一个好主意，但如果 a 和 b 都指向一个内存位置，它们将无法工作？如何解决这个问题？

Answer 1

这个问题在数学上很明显。

int swap ( int *a, int* b)
{
    *a = *a+*b;
    *b = *a-*b;
    *a = *a-*b;
}

当a和b指向同一个地方然后，上面的代码变成

*a = *a + *a; // *a = 2 x (*a)
*b = *a - *a; // = 0
*a = *a - *a; // = 0

因此，两者*a和*b都为零。因此，您应该使用以下方法处理它if：

int swap ( int *a, int* b)
{
    if (a!=b)
    {
      *a = *a+*b;
      *b = *a-*b;
      *a = *a-*b;
    }
}

版本也一样xor。

Answer 2

#define SWAP(a, b) (((a) == (b)) || (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b))))

Answer 3

为什么有人会在不使用额外空间的情况下交换两个数字？

哪个虐待狂会给你足够的空间容纳两个而不是三个？

你为什么称它为“空间”呢？这只是第三个数字，没有必要提到一个巨大的、真空的地方。

使用临时的算法在交换操作的数量上使用 O(1) 空间。数字的长度为 O(n)，但给定处理器不友好的 n，位旋转和算术长度很可能也是如此。

如果您没有足够的空间容纳一个简单的数字，那么您只是用完了空间。在那种情况下，我看不出你可以从交换中去哪里。

为什么不首先将这两个数字存储在适当的位置？

Answer 4

你可以试试这个，a=a+b; b=ab; a=ab;