前几天,同事给我秀了一段代码,初看之时,没弄懂其作用。这并不意外,因为我对这段代码所用到的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;

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

» 文章出处: reille博客—http://velep.com , 如果没有特别声明,文章均为reille博客原创作品
» 郑重声明: 原创作品未经允许不得转载,如需转载请联系reille#qq.com(#换成@)
分享到:

  2 Responses to “一段神奇的代码—用异或实现两数据交换”

  1. 我记得谭浩强那本书上有讲这个的。这个算是奇淫技巧吧

 Leave a Reply

(必须)

(我会替您保密的)(必须)

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.

   
© 2012 velep.com | reille blog | 管理| 粤ICP备15065318号-2| 谷歌地图| 百度地图| Suffusion theme|Sayontan Sinha

无觅相关文章插件,快速提升流量