c语言不用变量交换两个数分析

c++
c

首先看这样一个程序

1
2
3
4
int a, b;
a = a + b;
b = a - b;    //此时b = (a + b) - b = a; (经过第一步a为a+b)
a = a - b;    //此时a = (a + b) - a = b;  (经过第二步时b已为a)


可见这个程序实现了a和b的交换。注意+和-互为逆运算,可以得到(a+b)-b=a,埋个伏笔先。
在看这个例子:

1
2
3
4
int a, b;
a = a ^ b;
b = a ^ b;
a = a ^b;

这样也可以实现a和b的交换,是不是比较诡异。分析一下就很容易明白为什么可以这么实现了。
首先需要熟悉位运算关于异或^的知识,异或即对应位相同为0,相异为1.假设a为一个二进制位只能取0和1,可以得到这样几个恒等式:

1
2
3
a ^ 1 = !a.    把a分别当做01,自己运算一下很容易得到这个。
a ^ 0 = a.    还是把a分别当做01,自己运算一下很容易得到这个。
a ^ a = 0.   这个更容易了,每一位都相同,结果肯定为0.

再来看看这个(a^b)^b = a,这个说明了什么,其实异或^的逆运算就是本身,现在利用上面三个公式就可以证明这个公式。分别令b为0和1,当b为0时,(a^0)^0=a^0=a,  当b为1,(a^1)^1 = !(!a)=a。证毕。(注意a当成二进制位所以!(!a)成立)
再回头看为什么可以用异或交换两个数字:

1
2
3
a = a ^ b;    
b = a ^ b;  (b=a^b=(a^b)^b=a),此时b被赋值为a
a = a ^ b;  (a=a^b=(a^b)^a=(b^a)^a=b),此时a被赋值为b,注意异或满足交换律)

现在就很容易理解了。
推广:
实际上,如果定义两个满足逆运算的符号#,@,(a#b)@b=a,
a = a # b;
b = a @ b;
a = a @ y;
都可以实现a和b的交换。
这时候你可能会写一个交换的程序

1
2
3
4
5
6
void swap(int *x, int *y)
{
*y = *x ^ *y;
*x = *x ^ *y;
*y = *x ^ *y;
}

这个程序大部分时间正确,但是有个致命缺陷,当x和y指向同一个位置时,计算*x ^*y就会得到0。这样写的前提是假设两个指针不会指向同一个位置。这也是编译器优化时经常考虑的一点,这种两个指针指向同一个存储器的情况叫做存储器别名使用(memory aliasing)。


异或运算的性质:

异或是一种基于二进制的位运算,用符号XOR或者 ^ 表示,其运算法则是对运算符两侧数的每一个二进制位,同值取0,异值取1。它与布尔运算的区别在于,当运算符两侧均为1时,布尔运算的结果为1,异或运算的结果为0。
简单理解就是不进位加法,如1+1=0,,0+0=0,1+0=1。
性质

  • 交换律
  • 结合律
  • 对于任何数x,都有x^x=0,x^0=x
  • 自反性 A XOR B XOR B = A xor 0 = A

异或运算最常见于多项式除法,不过它最重要的性质还是自反性:A XOR B XOR B = A,即对给定的数A,用同样的运算因子(B)作两次异或运算后仍得到A本身。这是一个神奇的性质,利用这个性质,可以获得许多有趣的应用。 例如,所有的程序教科书都会向初学者指出,要交换两个变量的值,必须要引入一个中间变量。但如果使用异或,就可以节约一个变量的存储空间: 设有A,B两个变量,存储的值分别为a,b,则以下三行表达式将互换他们的值 表达式 (值)A=A XOR B (a XOR b) B=B XOR A (b XOR a XOR b = a) A=A XOR B (a XOR b XOR a = b)类似地,该运算还可以应用在加密,数据传输,校验等等许多领域。


运用:

1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?

解法一、显然已经有人提出了一个比较精彩的解法,将所有数加起来,减去1+2+…+1000的和。

这个算法已经足够完美了,相信出题者的标准答案也就是这个算法,唯一的问题是,如果数列过大,则可能会导致溢出。

解法二、异或就没有这个问题,并且性能更好。

将所有的数全部异或,得到的结果与1^2^3^…^1000的结果进行异或,得到的结果就是重复数。
但是这个算法虽然很简单,但证明起来并不是一件容易的事情。这与异或运算的几个特性有关系。
首先是异或运算满足交换律、结合律。
所以,1^2^…^n^…^n^…^1000,无论这两个n出现在什么位置,都可以转换成为1^2^…^1000^(n^n)的形式。
其次,对于任何数x,都有x^x=0,x^0=x。
所以1^2^…^n^…^n^…^1000 = 1^2^…^1000^(n^n)= 1^2^…^1000^0 = 1^2^…^1000(即序列中除了n的所有数的异或)。
令,1^2^…^1000(序列中不包含n)的结果为T
则1^2^…^1000(序列中包含n)的结果就是T^n。
T^(T^n)=n。
所以,将所有的数全部异或,得到的结果与1^2^3^…^1000的结果进行异或,得到的结果就是重复数。
当然有人会说,1+2+…+1000的结果有高斯定律可以快速计算,但实际上1^2^…^1000的结果也是有规律的,算法比高斯定律还该简单的多。