周二, 9月 16 2014, 10:02:57 晚上

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

c++

c

首先看这样一个程序

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，埋个伏笔先。
在看这个例子：

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

```
a ^ 1 = !a.　　　  把a分别当做0和1，自己运算一下很容易得到这个。
a ^ 0 = a.　　　   还是把a分别当做0和1，自己运算一下很容易得到这个。
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)成立）
再回头看为什么可以用异或交换两个数字:

```
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的交换。
这时候你可能会写一个交换的程序

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的结果也是有规律的，算法比高斯定律还该简单的多。

Next Prev