代码人生的小狗窝

一行行枯燥的代码,却描绘出人生的点点滴滴

您现在的位置是:首页>_C++

网络误区:不要中间变量交换2个变量的value,最高效的是异或运算

发布时间:2019-10-14浏览(2323)

    网络误区:不用中间变量交换2个变量的value,最高效的是异或运算.

    本文记录了不使用中间变量交换2个变量的value,很多的网络留言说是直接异或运算就可以了,而且效率很高,是真的吗?

    这里简单的说一下我的环境:Win7 32位,Qt creator 5.4.1 编译器MinGW4.9.2 32bit 调试器:GNU GDB 7.8


    关于这个问题,网络上面有很多的解释,3种方法,我这里给比较一下各自的优缺点,然后简单分析一下汇编代码,分析代码如下:

    #include <stdio.h>
    void swap1(int &a,int &b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
    void swap2(int &a,int &b)
    {
        a += b;
        b = a - b;
        a -= b;
    }
    void swap3(int &a,int &b)
    {
        a ^= b;//使用异或运算符
        b ^= a;
        a ^= b;
    }
    //这是第三种的缺点,不能交换float
    /*void swap3float(float &a,float &b)
    {
        a ^= b;//使用异或运算符
        b ^= a;
        a ^= b;
    }*/
    
    void swap3char(char &a,char &b)
    {
        a ^= b;//使用异或运算符
        b ^= a;
        a ^= b;
    }
    
    int main(void)
    {
        int a1 =1,b1 =2;
        int a2 =3,b2 =4;
        int a3 =5,b3 =6;
        int a = 2147483647,b=1;
        swap1(a1,b1);
        swap2(a2,b2);
        swap3(a3,b3);
        printf("a1 = %d,b1 = %d\n",a1,b1);
        printf("a2 = %d,b2 = %d\n",a2,b2);
        printf("a3 = %d,b3 = %d\n",a3,b3);
    
        swap2(a,b);
        printf("a = %d,b = %d\n",a,b);
    
    //    float a4=1.25,b4=2.51;
    //    swap3float(a4,b4);
    //    printf("a4 = %f,b4 = %f\n",a4,b4);
    
        char a5 = 'a',b5 = 'b';
        swap3char(a5,b5);
        printf("a5 = %c,b5 = %c\n",a5,b5);
        return 0;
    }
    /*
     * 三种交换方式,第一种属于教科书的方式,属于低级的
     * 第二种,加减运算时,可能会导致数据的溢出
     * 第三种方法最优。(但是float类型的不能交换)
    */
    
    /*
    a1 = 2,b1 = 1
    a2 = 4,b2 = 3
    a3 = 6,b3 = 5
    a = 1,b = 2147483647
    a5 = b,b5 = a
    Press <RETURN> to close this window...
    
    */

    通过上面的代码展示,你会发现,啊,原来最高效的运算是异或运算啊。定论别下的太早。看完下面的汇编,我想你心里就有数了。你不必知道汇编的语句,你只要会数代码的行数就OK了。


    方法1,号称最笨的方法。汇编代码如下:

    002


    方法2,使用+-运算解决,汇编如下:

    003


    方法3,直接异或运算,汇编代码如下:

    004


    小结:

    在我没有查看汇编代码以前,我也轻易了相信了网络上的留言,甚至某些书籍。在我写博客以前,我还在相信方法3是最高效的,因为它的思维最接近机器的运算的思维。我还在他人的面前显摆过自己。但是,现在,我明白了,只有代码会说实话。swap2和swap3的有效汇编代码都在21行,而swap1的只有14行,相互差距7行代码,当然了,如果你的变量开销很大的话,那么swap3是很好的,swap2也不错,就是注意一下运算的时候不要溢出就可以了。当然了,算法的好坏,都是相对了,要看具体的环境情况。现在我想说,遇到什么知识,能自己测试的,可以测试一下,实践是检验真理的唯一标准。


    修改日期20150601:

    昨天睡的时候又在想这个问题,谁让咱是强迫症呢,觉得自己的想法太简单了,没有用时间来测试一下。今天看到1楼BYSF-XF的评论,更加让我下定决心用时间来测试一下了。测试的结果更是让我意外。我的环境已经在前面补充出来了。

    首先是1楼的源码测试,结果如下,测试次数:0x7FFFFFFF:

    从结果中,在我的环境上看到:使用swap4异或的效率确实不怎么好。我的机器和我的人一样笨笨的,接下来次数小一点吧,如下:

    我使用了一个const常量来控制次数,这么多次,记得把下面的for循环也修改了。可以看到测试数据还是swap4异或很不理想。


    修改日期20150602:

    今天得到1楼BYSF-XF的测试反馈,测试结果在3楼,我把结果移植到这里了。从下面的结果看,不同的编译器,会产生不同的效果。而且debug和release的区别更是显著,这主要是因为debug是调试用的,编译器没有对程序进行优化处理,而release是发布版本,编译器对程序都做了优化处理,使程序更快更小,所以最后产生0的结果,也就不意外了。

    好了,本人只是闲的没事儿,喜欢纠结。如果您有什么好的发现,还请留言讨论,一起探索。有时候存有一颗质疑的心,还是会发现新东西的。


    1楼BYSF_XF
    我觉得不应该只看汇编代码的行数,因为不同的汇编代码执行时长可能是不同的。,以下是我的测试代码:,#include lt;iostreamgt;#include lt;ctimegt;using namespace std;void swap1(int amp; a, int amp; b){ int temp = a; a = b; b = temp