交换两个元素

刚才练手写快速排序算法的时候，中间用到一个swap函数……不知道怎么脑子抽了忽然想到一个古老的技巧，不使用临时变量交换两个元素：

int a, b;
a ^= b; // a = a^b
b ^= a; // b = a^b^b = a
a ^= b; // a = a^b^a = b

然后我就写了一个这样的函数：

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

结果，发现这个快速排序程序怎么都不对劲……对照quick_sort()，没问题；再对照partition()，也没问题啊。直到我恍然大悟，问题出在swap函数上，假如a和b指向同一个地址，这个函数会怎么样呢？

int i = 1;
int *a = &i;
int *b = &i;
swap (a, b);
printf ("%d\n", i);

猜猜i等于多少？归零了……

所以还是用传统的swap函数吧

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

然后然后，脑子继续抽，如果我们在swap中使用受限指针呢？所谓受限指针，就是函数有2个以上的指针参数的时候，加上restrict关键字，表示这几个指针指向的内存区域不会重叠，方便编译器做优化，详见http://misc.poetpalace.org/C99/_02_The_New_C_It_All_Began_with_FORTRAN.html

试验了一把，发现加了restrict关键字，结果也是一样的，编译器并不会检查你是否传递了一样的指针，而仅仅是假设这两个指针绝对不会一致。也就是说，restrict关键字其实是需要用户来保证的。前几年，linux因为老婆看youtube没声音报告了一个bug，最后查出来好像就跟memset的restrict关键字有关……

测试代码：

/* don't use this, unless you sure that a & b are not overlapped */
static void swap (int * restrict a, int * restrict b)
{
	*a ^= *b;
	*b ^= *a;
	*a ^= *b;
}

交换两个元素

See Also: