woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

不用临时变量也可以交换变量的值

当要交换两个数的值时,通常的做法是定义一个临时变量,然后再进行交换。那么能不能不用临时变量而交换两个数的值呢?可以的!C语言提供的异或运算就可以实现这样的操作。

异或运算符^也称XOR运算符,它的规则是若参加运算的两个二进位同号,则结果为0(假);异号为1(真)。即0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0 

例:

#include <stdio.h>

int main(int argc, char *argv[])
{
   
int a = 2, b = 6;

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

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

   
return 0;
}

结果如下:

a = 6 b = 2

分析:

前两个赋值语句:“a = a ^ b“b = b ^ a相当于b = b ^ (a ^ b),而b ^ a ^ b等于a ^ b ^ bb ^ b的结果为0,因为同一个数与相向相^,结果必为0。因此b的值等于a ^ 0,即a,其值为2

再执行第三个赋值语句:“a = a ^ b”。由于a的值等于(a ^ b)b的值等于(b ^ a ^ b),因此,相当于a = a ^ b ^ b ^ a ^ b,即a的值等于a ^ a ^ b ^ b ^ b,等于b

今天又发现另外两种方法,特补上。 

方法一

void swap(int *p, int *q)
{
   
*p = *p + *q;
   
*q = *p - *q;
   
*p = *p - *q;
}

方法二

void swap(int *p, int *q)
{
   
*p = *p + *q - (*q = *p);
}

原理为算术运算符的结合顺序为自左至右。

2007.06.18

 

可以把异或的三条语句压缩为一条: 

a ^= b ^= a ^= b;

要交换三个变量的值,可以用以下语句:

c = a + c - (a = b, b = c);

2007.09.11

谢谢网友cool8jay指出上面红色部分的错误,下面来分析一下,先看一个示例程序,如下:

#include <stdio.h>

int main(int argc, char *argv[])
{
   
int a = 1;
   
int b = 2;
   
int c = 3;

    c
= a + c - (a = b, b = c);

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

   
return 0;
}

编译运行,结果如下:

a = 2 b = 3 c = 2

可见,最初目标中的c = 1部分没能实现。于是分析原因:

The C Programming Language·Second EditionP205介绍说,“The additive operators + and - group left-to-right”,即附加运算符加号和减号的结合顺序是自左向右;P209介绍说,“A pair of expressions separated by a comma is evaluated left-to-right, and the value of the left expression is discarded. The type and value of the result are the type and value of the right operand”,即逗号表达式的计算顺序是从左向右,逗号左边表达式的值被舍弃,表达式结果的类型和数值是逗号右边表达式的类型和数值。

既然如此,那结果应该是正确的,为什么还会出错呢?再来看一下VC6.0下编译产生的汇编代码:

7: int a = 1;
00401028
mov dword ptr [ebp-4],1
8
: int b = 2;
0040102F
mov dword ptr [ebp-8],2
9
: int c = 3;
00401036
mov dword ptr [ebp-0Ch],3
10
:
11
: c = a + c - (a = b, b = c);
0040103D
mov eax,dword ptr [ebp-8]
00401040
mov dword ptr [ebp-4],eax
00401043
mov ecx,dword ptr [ebp-4]
00401046
add ecx,dword ptr [ebp-0Ch]
00401049
mov edx,dword ptr [ebp-0Ch]
0040104C
mov dword ptr [ebp-8],edx
0040104F
sub ecx,dword ptr [ebp-8]
00401052
mov dword ptr [ebp-0Ch],ecx

可以看到,第11行代码的执行过程如下:

先把b的值赋给a,再把ac的值相加,结果放在寄存器ecx中,然后把c的值赋给b,最后再把ecxb的值相减,结果赋给c。分解为C语句为:

a = b; /* a = 2, b = 2 */
ecx
= a + c; /* ecx = 5, a = 2, c = 3 */
b
= c; /* b = 3, c = 3 */
c
= ecx - b; /* c = 2, ecx = 5, b = 3 */

这下就清楚了,原来程序运行时先把逗号左边表达式的值计算出来丢弃掉,然后再做其它的运算,最开始的错误也就错在了这里。

好了,既然上面的式子有问题,那有没有其它正确的方法能一条语句实现三个变量的值的交换呢?恕本人愚钝,还没有想出来。如果谁知道,请给我留言。在此先致谢!

还有一个问题,也是网友cool8jay提出来的,就是交换三个变量的值(每个变量值都要改变)应该有两种情况,123可以变为231312。我当时想到过,只是觉得可以类比就没有说明,现在看来可能会误导读者,这里说明一下。

不用临时变量顺次交换N个变量的值

 

 

NN>=2)个变量,不使用临时变量,如何顺次交换它们的值?能否只用一条语句实现?如

 

+---+---+---+---+---+
| a | b | c | d | e |
+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+

 

要把它变为

 

+---+---+---+---+---+
| a | b | c | d | e |
+---+---+---+---+---+
| 2 | 3 | 4 | 5 | 1 |
+---+---+---+---+---+

 

怎样实现?

 

首先,我们考虑用异或实现两个变量的交换,可参考我的这篇文章《不用临时变量交换两个数的值》。用C++写函数如下:

 

int &swap(int &a, int &b)
{
    b
= b ^ a;
    a
= a ^ b;
    b
= b ^ a;

   
return b;
}

然后可以把代码优化为:

int &swap(int &a, int &b)
{
    b ^
= a;
    a ^
= b;
    b ^
= a;

   
return b;
}

继续优化,把三句压缩为一句,如下:

int &swap(int &a, int &b)
{
    b ^
= a ^= b ^= a;
   
   
return b;
}

还可再优化,如下:

int &swap(int &a, int &b)
{
   
return (b ^= a ^= b ^= a);
}

现在来顺次交换5个变量的值,如下:

swap(a, b);        //返回b

swap(b, c);        //返回c

swap(c, d);        //返回d

swap(d, e);       

既然有返回值,那么可以写成链式的,如下:

swap(a, b);                                 //返回b

swap(swap(a, b), c);                        //返回c

swap(swap(swap(a, b), c), d);               //返回d

swap(swap(swap(swap(a, b), c), d), e);       

现在,让我们来把swap函数依次用相应的函数体替换掉,如下:

e ^= d ^= e ^= swap(swap(swap(a, b), c), d);

e ^
= d ^= e ^= d ^= c ^= d ^= swap(swap(a, b), c);

e ^
= d ^= e ^= d ^= c ^= d ^= c ^= b ^= c ^= swap(a, b);

e ^
= d ^= e ^= d ^= c ^= d ^= c ^= b ^= c ^= b ^= a ^= b ^= a;

好了,最后一个语句就实现了顺次交换五个变量的值,写程序验证如下:

/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
*
文件名称:xor.c
*
简要描述:实现五个变量的顺次交换
*
*
当前版本:1.0
*
作 者:raincatss
*
完成日期:2007-10-18
* 开发环境:Windows XP Sp2 + VC6.0
*
个人博客:http://raincatss.cublog.cn/
******************************************************************/


#include <stdio.h>

#define PRINT(A) do {\
   
printf("%d\n", A);\
   
} while (0)

int main()
{
   
int a = 1;
   
int b = 2;
   
int c = 3;
   
int d = 4;
   
int e = 5;

//    b ^= a ^= b ^= a;        // swap(a, b)

//    c ^= b ^= c ^= b;        // swap(b, c)

//    d ^= c ^= d ^= c;        // swap(c, d)

//    e ^= d ^= e ^= d;        // swap(d, e)


    e ^
= d ^= e ^= d ^= c ^= d ^= c ^= b ^= c ^= b ^= a ^= b ^= a;

    PRINT
(a);
    PRINT
(b);
    PRINT
(c);
    PRINT
(d);
    PRINT
(e);

   
return 0;
}

运行结果如下:

2 3 4 5 1

测试结果正确,达到预定目标。

 

posted on 2008-11-07 23:06 肥仔 阅读(1861) 评论(1)  编辑 收藏 引用 所属分类: C++ 基础

评论

# re: 不用临时变量也可以交换变量的值  回复  更多评论   

c = a + c - (a = b, b = c);

改成c = a + b- (a = b, b = c);看可不可以
2008-11-18 10:16 | qun454

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理