interchange 2 variables without temp by 3 XORs

在baidu搜索“不使用第三个变量交换两个变量的值”,会发现找到相关结果约827,000个。基本上讨论的最终结果都是使用3次异或。

在此,与大家讨论一下的我的感受。

传统方法:3次赋值操作

定义一个相同类型的临时变量

顺次使用3次赋值完成交换。

int a=12,b=34;
int temp;
temp=a; a=b; b=temp;

优点是:

代码易读,便于维护,且最为稳妥。
 此方法有些人称作“标准方法”,也有道理。

缺点是:

需要第三个变量。增加了代码长度。

 

 

 

引导方法:利用加减运算(可能溢出,不建议采用)

再次贴出此方法是为了下文的异或方法做铺垫。

int a=12,b=34;
a=a+b;
b=a-b;
a=a-b;

先保存两者之和

用和减去自己就得到了对方

同理,完成交换

此方法挺巧妙,没有采用临时变量就交换了2个变量的值。但是最大的隐患就是可能溢出,仅此一缺点足以使之被排除。

异或方法:(3次异或)

真值表先附上异或与加减的真值表。(左边的单引号表示进退位)

在没有进退位的情况下(或称为模2运算),可以发现三者的真值表是相同的。

也就是说异或操作可以理解为相加,也可以理解为相减,因此不难有:

int a=12,b=34;
a=a^b; 
b=a^b;
a=a^b;

先用异或保存两者之和

用异或从“和”中剥离自己得到对方

同理,完成交换

 

 

 

因为

a^b == b^a;

所以

int a=12,b=34;
a^=b; 
b^=a;
a^=b;


进一步简化,有

int a=12,b=34;
a^=b^=a^=b; 

优点:

未使用临时变量,直接交换2个变量的值。代码量少,运行效率高。

缺点:

可读性差,难于测试维护。

引申:使用宏定义

#define swap(a,b) ((a)^=(b)^=(a)^=(b))

只要是再出现想交换2变量的情况,就像使用函数一样直接使用该宏定义即可。

而且我们可以发现,要交换的变量只要是类型相同均可,可以是字符,整数,浮点数,甚至指针,数组元素,结构体中的分量。

比如需要交换2个结构体中的每个分量,而结构体又有5个分量,更糟的是类型还不同。如果是使用传统方法,需要5个临时变量(或者1个结构体做临时变量,但是还是有5个单元),交换一组需要3条语句,代码量可想而知。而是用上面这个宏定义的话,如果分量不是数组,结构体的话,只要5个swap即可。

注意事项:有2点需要注意(暂时发现这2点,有新见解大家可以发表)。

1.上面的swap宏只能用于基本变量的交换。意思就是说,不能直接交换整个数组,只能交换数组中的某个元素,而且还必须是相同类型。

2.不能出现类似于这样的语句:

swap(Array[left++],Array[right--]);

因为宏定义中每个变量出现两次,这样使用宏会导致变量本身自加或者自减2次,而预期效果是只有1次,所以需要注意。

3.(2011年9月6日)刚刚又发现一个bug,若swap的两个量是相同值时?!由于异或的特性,相同值异或结果为0!就会出现将两个变量之一置为0的结果。试想一想,如果用在排序算法中,全部记录中没有相同值才可以用这个宏。

4.将上面一点改进,在swap之前先进行一次比较判断,值不同时再使用,就可以解决此问题。

 

 

结束语: 以上是最近对变量交换的一些感觉和认知过程,特与大家分享,有赞同反对见解均可留言,欢迎至极!

相关文章
相关标签/搜索
每日一句
    每一个你不满意的现在,都有一个你没有努力的曾经。
公众号推荐
   一个历史类的公众号,欢迎关注
一两拨千金