使用c语言写一个函数实现两个数交换，很简单写下以下代码：

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

只有三行代码，且没有引入中间变量，使用位运算，效率高！

但首先必须保证a, b 不是空指针，否则就会出现段错误。

于是代码进一步改成：

void swap(int *a, int *b)
{
    if (a == NULL || b == NULL)
        return;
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

似乎这样就完美了？

咋一看，真没有什么问题了，不信你可以测试，无论正数，负数，还是0,基本都不会出错了。。

那么请看以下代码：

static int count = 0;
void permutation(int *a, int from, int to)
{
    if (from == to) {
        cout << ++count << ":";
        for (int i = 0; i <= to; ++i)
            cout << a[i] << " ";
        cout << endl;
        return;
    }
    for (int i = from; i <= to; ++i) {
        swap(&a[from], &a[i]);
        permutation(a, from + 1, to);
        swap(&a[from], &a[i]);
    }
}

以上代码是求一个数组全排列的递归方法，算法应该没有错？

可是输出大量0！！为什么呢？？？

答案在下面：

原因在于当swap(int *a, int *b)传的是同一个地址时，就会等于0

即若 a == b

*a ^= *b，此时 *a == 0, *b == 0

最后必然是 *a == 0, *b == 0,

 for (int i = from; i <= to; ++i) {
        swap(&a[from], &a[i]);
        permutation(a, from + 1, to);
        swap(&a[from], &a[i]);
    }

上面代码没有考虑当from == i的情况，即传递的是同一个地址。

所以正确的swap函数，应该是：

void swap(int* a, int* b)
{
    if (a == NULL || b == NULL || a == b)
        return;
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

• 相关文章
• 全局相关文章