一段神奇的代码—用异或实现两数据交换



前几天，同事给我秀了一段代码，初看之时，没弄懂其作用。这并不意外，因为我对这段代码所用到的C语言异或^操作符不熟悉。一是在我的编程里这个操作符不常用，看其它代码也少见到；二是我编程的基础知识本身就不是很扎实。

同事秀的这段代码以前并未见过，当他说出这段代码的功能后，先是惊讶其精妙绝伦地实现，然再搜索其原理，发现其也不是想象的那么美好。在这里一一探究。

这是一段什么代码呢？

代码很简单，也许你见过。如下：

int a = 100, b = 200;

a = a ^ b;
b = a ^ b;
a = a ^ b;

printf("a = %d, b = %d\n", a, b);

执行的结果是：a = 200, b = 100。

从结果也许你想到了，这段代码其实就是实现了两个数据的交换功能。 与课本上见到的两数据交换功能实现不同，这里没用到第3个临时变量。如果你是第一次见到它，或许你也会像我一样，感觉太神奇了。神奇归神奇，咱们还是来了解下这段代码的实现原理吧。其实原理很简单，实质就是C语言中异或运算符的应用。所以，这里先简单介绍下异域运算符。

异或运算xor

异或运算：参与运算的两个值，如果对应bit位相同，则结果为0，否则为1。也就是：

0 ^ 0 = 0;
0 ^ 1 = 1;
1 ^ 0 = 1;
1 ^ 1 = 0;

异或运算特点

• 0^0 = 0，0^1 = 1  ：0异或任何数＝任何数；
• 1^0 = 1，1^1 = 0  ： 1异或任何数 =任何数取反；
• 任何数异或自己 ＝ 把自己置0

一句话总结就是：按位进行异或，相异为1，相同为0

异或运算法则

1. a ^ b = b ^ a
2. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c
3. d = a ^ b ^ c 可以推出 a = d ^ b ^ c
4. a ^ b ^ a = b

实现原理

通过上面对异或运算符的介绍，相信你已大概明白使用异或运算符实现两个数据交换的原理了。这里说下我对它的理解。

a = a ^ b;
b = a ^ b;
a = a ^ b;

// 前两句等效变换为：
b = (a ^ b) ^ b == > b = a ^ (b ^ b) ==> b = a // 这样把a就赋值给了b

// 第三句等效变换为： 
a = (a ^ b) ^ ((a ^ b) ^ b) == > a = (a ^ b) ^ (a ^ b ^ b) == > a = a ^ b ^ a == > a = b // 这样把b赋值给了a

异或运算延伸使用

异或运算除了可实现两变量交换功能外，还可以实现其它功能，这里从网上整理如下：

1. 使某些特定的位翻转，如对数10100001的bit2和bit3翻转，则可将该数与00000110进行按位异或运算：

10100001^00000110 = 10100111

2. 在汇编语言中经常用于将变量置零：xor   a，a

3. 快速判断两个值是否相等。

举例1: 判断两个整数a，b是否相等，则可通过下列语句实现：

 return ((a ^ b) == 0)

举例2: Linux中最初的ipv6_addr_equal()函数的实现如下:

    static inline int ipv6_addr_equal(const struct in6_addr *a1, const struct in6_addr *a2)
    {
        return (a1->s6_addr32[0] == a2->s6_addr32[0] &&
            a1->s6_addr32[1] == a2->s6_addr32[1] &&
            a1->s6_addr32[2] == a2->s6_addr32[2] &&
            a1->s6_addr32[3] == a2->s6_addr32[3]);
    }

可以利用按位异或实现快速比较, 最新的实现已经修改为:

    static inline int ipv6_addr_equal(const struct in6_addr *a1, const struct in6_addr *a2)
    {
    return (((a1->s6_addr32[0] ^ a2->s6_addr32[0]) |
        (a1->s6_addr32[1] ^ a2->s6_addr32[1]) |
        (a1->s6_addr32[2] ^ a2->s6_addr32[2]) |
        (a1->s6_addr32[3] ^ a2->s6_addr32[3])) == 0);
    }

注：关于异或运算符延伸使用的内容介绍摘自：“kapu” 博客。

再说使用异或实现两变量交换

虽然使用异或运算符实现两个变量交换的代码看起来很巧妙，但一些书本上却不提倡使用。究其原因就是：代码看似精妙，节省了一个临时变量内存空间（无需第3个临时变量），实际上可能未必如此，反而可能需占用更多内存，效率上也未必比传统的实现更高。关于这部分的说明，参考文章：http://blog.csdn.net/solstice/article/details/5166912

几种两变量交换的实现

第一种方法，即传统的实现方法，借助第3个变量实现。如：C=A;A=B;B=C; 该方法需借助第三变量来实现；

第二种方法，利用加减法实现两个变量的交换，如：A=A+B;B=A-B;A=A-B;

第三种方法，上面介绍的利用异或运算符来实现。