不用中间数交换两个变量的方法 -

标题: 不用中间数交换两个变量的方法 [打印本页]

作者: f556 时间: 2019-11-26 10:49
标题: 不用中间数交换两个变量的方法
本帖最后由 f556 于 2019-11-26 10:50 编辑

再次翻看多年前的日志，看到自己记录的算法，联想到前些天论坛有人问了一个简单的问题：“怎么交换两组数？”
当时有人回答用中间变量，这是一种常用的方法。这个思路好比以下例子：一杯果汁A、一碗牛奶B，现在要互换一下容器，即把A换到碗里，B换到杯里。只有借助第3个容器C。操作是A--->C,B---->A,C----->B,这样才能完成交换。
有人回答用加减法，思路不错：
a=3;b=5;
a=a+b;
b=a-b;
a=a-b;
但当时我提出有溢出问题，如235+122怎么办，设定a、b均为unsigned char；如果均为unsigned int同样有问题，不能用程序来限定a、b值的范围，特别是ADC的值。

我日志记录的不用中间数交换两个变量的方法，均利用C语言的异或运算。
异或逻辑：对应的位相比较，同=0，异=1，实际上可以理解就“按位求异”,即“异为真，同为假”
举例：
xxxx 1001  ^ 0000 1111 = xxxx 0110（后4位翻转）
xxx1 xxxx  ^    1 0000 =xxx0 xxxx
xxx0 xxxx  ^    1 0000 =xxx1 xxxx

程序如下：
unsigned int aa=3456,bb=7890;
void main( void )
{
  aa=aa^bb;
  bb=bb^aa;
  aa=aa^bb;
}
运行结果见图片。

stest.jpg (102.67 KB, 下载次数: 291)

还未运行

stest2.jpg (62.3 KB, 下载次数: 314)

运行完

作者: hi毁人不倦 时间: 2019-11-28 08:36
夭寿，答案确实如此为何脑子还是转不太过来。

作者: hange_v 时间: 2019-11-30 12:33
这个太厉害了，精彩

作者: 15806853199mmm 时间: 2019-12-2 12:35
好厉害，电赛初学者刚好

作者: shibadong 时间: 2019-12-5 09:22
没看懂啊！！！

作者: 欧阳来洪 时间: 2019-12-10 09:49
神仙算法

作者: f556 时间: 2019-12-10 17:07
解释一下，试算：
a=2 ----b 10
b=3 ----b 11          以下用二进制
a=a^b=10^11=01    这个数相当于一个中间值，不是原a，也不是原b
b=b^a=11^01=10  ---->2    使用了中间值01 （a）
a=a^b=01^10=11  ----->3    使用了中间值01 ,也使用了交换好的b

异或象加法一样，不分先后顺序
改程序如下图，也可

sss.jpg (21.03 KB, 下载次数: 271)

作者: lzj527095842 时间: 2019-12-13 17:59
牛逼，学习了

作者: rotga 时间: 2019-12-16 08:51
这种交换方法有一个前提，就是aa和bb不能相等，如果相等，则会得出错误的结果。所以在做异或运算前，需要进行判断。

作者: f556 时间: 2019-12-17 14:13

rotga 发表于 2019-12-16 08:51
这种交换方法有一个前提，就是aa和bb不能相等，如果相等，则会得出错误的结果。所以在做异或运算前，需要进 ...

真的吗？纯属你的主观意断！

作者: f556 时间: 2019-12-17 14:18
否定楼上的想当然，两个相同数的交换。见运行图片
人算：
a=1; b=1;
a=a^b=0;
b=a^b=0^1=1;
a=a^b=0^1=1;
错在哪里！

ssss.jpg (52.97 KB, 下载次数: 225)

作者: 没有你 时间: 2019-12-20 15:56
你这种方法虽然可行，涉及到异或处理，编译出的汇编代码会比中间变量法多一些，这样的话，单片机就需要花更多是时间去处理，可以说效率低。而且这样写，代码的可读性非常差。

作者: qq923004243 时间: 2019-12-21 12:37
多学一种思路，至少以后看的懂谢谢楼主的讲解楼主说的两种我看过，这个没看过

作者: rotga 时间: 2019-12-22 22:26
如果只是在main中这样做，结果没有问题，但是在实际编程中，以调用函数的方式，那么只能用指针传递实参，如果两个数值相等的话，这样就会出错。你可以试一试。

作者: rotga 时间: 2019-12-22 22:54
#include <stdio.h>
void swap(int *a,int *b)
{
*a^=*b;
*b^=*a;
*a^=*b;

}
void main(void)
{
int test[2] = {21,23};
swap(&test[0],&test[0]);
printf("test[0]=%d test[1]=%d",test[0],test[1]);
}
运行结果：test[0]=0 test[1]=23

作者: 学习使我快乐呢 时间: 2019-12-25 15:29
学到了，很有帮助，这个平台很不错

作者: f556 时间: 2019-12-27 16:31

rotga 发表于 2019-12-22 22:54
#include
void swap(int *a,int *b)
{

你程序有一句明显错误。

作者: 113265 时间: 2019-12-27 22:18
太麻烦了

作者: f556 时间: 2019-12-28 12:36

rotga 发表于 2019-12-22 22:54
#include
void swap(int *a,int *b)
{

有一个语句明显错了，请改正。
另外，我个人非常厌恶printf，这个纯无用的垃圾语句。从你用printf可以看出受了唐大师的毒害，还是重新找本书或者混一下网站、论坛。

作者: rotga 时间: 2019-12-31 10:08
不是明显错了，而是模拟在复杂环境里面，很有可能产生待比较的两个数的指针指向同一地址，而结果你也看到了，是否和你之前想象的结果一致？你的心态很浮躁，我的水平是不高，但三人行必有我师焉。是否你认为给你指出潜在的错误逻辑只能是水平比你高的人才有资格？这个帖子我无意和你扯这些口舌之争。如果技术上还有需讨论的地方，欢迎发表观点。关于用异或交换数字，是个思路，但第一，对于直接交换，如果操作对象是同一个数，会有错误结果。第二，运行效率低，代码可读性差。这个早已是定论。

作者: woxue100 时间: 2019-12-31 10:33
好厉害，初学者刚好

作者: hfj2011 时间: 2020-1-11 12:11
#include <stdio.h>
void swap(int *a,int *b)
{
      *a^=*b;
      *b^=*a;
      *a^=*b;

}
void main(void)
{
      int test[2] = {21,21};
      swap(&test[0],&test[1]);
      printf("test[0]=%d test[1]=%d",test[0],test[1]);
}
运行结果：
test[0]=21 test[1]=21Press any key to continue

作者: qinshuai 时间: 2020-1-17 11:05
感谢，涨知识了

作者: Daniel008 时间: 2020-1-20 16:11
学习了，很有帮助

作者: Daniel008 时间: 2020-1-20 16:30

rotga 发表于 2019-12-16 08:51
这种交换方法有一个前提，就是aa和bb不能相等，如果相等，则会得出错误的结果。所以在做异或运算前，需要进 ...

相等就不用交换了

作者: forpeople 时间: 2020-2-2 20:11
这么好的贴子不顶不行

作者: wodexiang 时间: 2020-2-3 01:00
不具通用性，只能在特殊场景里使用

作者: yk_yyy 时间: 2020-2-15 13:18
这个方法好，学习了

作者: sgb957431795 时间: 2020-2-15 15:07
谢谢大佬学习了

作者: IKNOW 时间: 2020-2-20 13:32
有意思

作者: barlai 时间: 2020-3-11 07:45
过来学习！

作者: hbcqd 时间: 2020-3-15 19:59
先学习这个方法，在实践中运用，感谢大家的分享！

作者: jhy8341 时间: 2020-3-15 21:19
两次对同一个数异或还等于自己

作者: wanghz12 时间: 2020-3-22 13:53
int x,y;
x=x+y;
y=x-y;
x=x-y;

作者: dongqing 时间: 2020-4-12 11:04
学习学习，感谢！

作者: 权威人物 时间: 2020-4-21 13:54

rotga 发表于 2019-12-16 08:51
这种交换方法有一个前提，就是aa和bb不能相等，如果相等，则会得出错误的结果。所以在做异或运算前，需要进 ...

你的基础不行啊，楼主这么详细的说明了你都还没明白么？

作者: 权威人物 时间: 2020-4-21 13:57

wanghz12 发表于 2020-3-22 13:53
int x,y;
x=x+y;
y=x-y;

这个的前提是相加不能超出int范围

作者: 新洲罗远 时间: 2020-4-22 20:26
天才算法！

作者: 1823711995 时间: 2020-4-30 16:52
把加法换为减法不就可以了？减法不会溢出，也比异或效率高

作者: 1823711995 时间: 2020-4-30 16:54
a=3;b=5;
a=a-b;
b=a+b;
a=b-a;

作者: guyunfeng 时间: 2020-5-16 10:48
楼主有点武断了，用加法交换虽然会溢出但结果依然正确。在指出问题之前最少要动手试一试。

作者: guyunfeng 时间: 2020-5-16 10:50
溢出不影响结果，楼主方向错了。

作者: dzbj 时间: 2020-5-20 17:09
请教两个问题如下应该是最傻愣的方法吧第一这样也不限制长度不管是char还是int 因为过程变量的长度是相同的第二不需要运算只是赋值会比你的方法速度快是么

uchar a=123;
uchar b=234;

void swap()
{
uchar c;
c=a;
a=b;
b=c;
}

作者: romking11 时间: 2020-5-25 15:53
好厉害，电赛初学者刚好

作者: luohujiu 时间: 2020-5-27 14:58
好东西值得去想和学习

作者: specialClass 时间: 2020-5-30 17:26
楼主的这个帖子很有意义，用到了异或的性质：
只要有： a^b=c
那么对于（）^（）=（）可以随便填入a、b、c 都成立，交换数来説也就很简单了
MOV A,#33H
MOV 30H,#66H
XRL A,30H
XRL 30H,A
XRL A,30H
在一些寄存器不够的地方用刚刚好，学习了

作者: 塞北江南 时间: 2020-8-29 16:16
有那么点意思，值得发扬光大！

作者: 正规007 时间: 2020-8-29 16:31
顶起！值得推广！

作者: 长风007 时间: 2020-9-23 16:47
你这种方法可行，只是单片机就需要花更多是时间去处理，效率有点低。

作者: passanyworld 时间: 2020-11-6 14:28
你的思路不错

作者: 温xyz 时间: 2020-11-28 07:54

wanghz12 发表于 2020-3-22 13:53
int x,y;
x=x+y;
y=x-y;

x=x+y可能会溢出。

作者: rundstedt 时间: 2021-1-23 18:06

温xyz 发表于 2020-11-28 07:54
x=x+y可能会溢出。

溢出不影响结果的正确性。

作者: zpmpok001 时间: 2021-1-28 13:56

Daniel008 发表于 2020-1-20 16:30
相等就不用交换了

所谓的相等，是认为分析，
在程序运行时 A  B  有时相等，有时不相等
例如  A 是用户指定的数据
      B  是函数得出的返回值

那么：我们控制不了的两个数据，他们有可能相等（作者认为相等的会出错），有时候不相等

作者: 山乌木 时间: 2021-3-24 17:23
不同的思维方式，看了很受益

作者: cfqde 时间: 2021-3-27 15:56
好方法呀！

作者: nakete 时间: 2021-5-12 14:53
方法不错~~不过大型的程序会在意这个小算法吗？

作者: USHODO 时间: 2021-5-25 09:28
讨论热烈拓展思路

作者: yzwzfyz 时间: 2021-6-23 15:42
1、程序运行时间长；
2、占用存储器多；
3、不实用。
将这段程序编译后，看看所用的代码就知道有多蠢了。
比起：A--->C,B---->A,C----->B 的方案差远了。

作者: 单片机爱好者223 时间: 2021-7-14 19:16
时间换空间

作者: 单片机爱好者223 时间: 2021-7-14 19:17
PUSH A
MOV A,B
POP B
最简单

作者: 这个好难啊！ 时间: 2021-7-23 11:28

rotga 发表于 2019-12-16 08:51
这种交换方法有一个前提，就是aa和bb不能相等，如果相等，则会得出错误的结果。所以在做异或运算前，需要进 ...

1.相等了就可以不用交换了；
2.可以加个判断，只有不相等的时候才会有下面的交换

作者: jizhongbiao 时间: 2021-8-2 17:05

rotga 发表于 2019-12-31 10:08
不是明显错了，而是模拟在复杂环境里面，很有可能产生待比较的两个数的指针指向同一地址，而结果你也看到了 ...

你用其它方法指向同一个地址也是会有问题的，这个和楼主的算法无关。

作者: zyluglugl 时间: 2021-8-3 22:26
这是什么原理？可以解释一下吗？

作者: zyluglugl 时间: 2021-8-3 22:29

rotga 发表于 2019-12-16 08:51
这种交换方法有一个前提，就是aa和bb不能相等，如果相等，则会得出错误的结果。所以在做异或运算前，需要进 ...

你是最牛的人，给你点赞先！

作者: 1075402835 时间: 2021-8-3 22:48
初学者的天堂

作者: hhdsdy 时间: 2021-8-4 00:57

单片机爱好者223 发表于 2021-7-14 19:17
PUSH A
MOV A,B
POP B

我也想这样说的，这个占用的是预留的空间，过后归还，不会额外占用空间

作者: lsh04 时间: 2021-8-7 23:56

rotga 发表于 2019-12-22 22:54
#include
void swap(int *a,int *b)
{

这句错了swap(&test[0],&test[0]);
应为 swap(&test[0],&test[1]);

作者: 188610329 时间: 2021-9-24 23:20

specialClass 发表于 2020-5-30 17:26
楼主的这个帖子很有意义，用到了异或的性质：
只要有： a^b=c
那么对于（）^（）=（）可以随便填入a、b、 ...

兄弟，你都用汇编写了……
你直接一个 XCH A,30H 不就换过来了么？还那么几个 XRL 干嘛啊？

作者: 188610329 时间: 2021-9-24 23:27
表面上看，不占用中间变量，实际上至少占用了累加器A，根据不同的编译方式还可能占用寄存器B，一样动用了累加器A，你先移动到累加器A，再互相移位远比反复运算要好得多。

作者: rsx9583 时间: 2021-11-3 11:37

1823711995 发表于 2020-4-30 16:54
a=3;b=5;
a=a-b;
b=a+b;

你这种算法很好。运行效率与可读性应该是比较强的。
不过我觉得还是设个中间数的最简单明了，不用去规避一些未知的坑。

作者: chinomango 时间: 2022-3-19 05:10
异或效率该比加减高吧？这个出来40年了吧？我好奇还有折磨多人发帖

作者: zhaobolove 时间: 2022-3-19 09:28
#include <stdio.h>

int main(void)
{
unsigned int a=65530;
unsigned int b=65535;

printf("交换前a,b的值分别为:\n");
printf("a=%d\n",a);
printf("b=%d\n",b);

a=a+b; //a=a*b;

b=a-b; //b=a/b;

a=a-b; //a=a/b;

printf("交换前a,b的值分别为:\n");
printf("a=%d\n",a);
printf("b=%d\n",b);

return 0;
}

已经测试了，没有问题，不会溢出问题

作者: wukouyyq 时间: 2022-4-16 14:43
就用一下一个中间变量又能咋滴？

　想起了一个笑话，3个专家和一个农民在说下雨时雨滴的问题，这个故事　就不在这里说了。

原来这个笑话是说我们程序猿的。。。。。。。

作者: 鹈鹕 时间: 2022-6-11 20:02

zyluglugl 发表于 2021-8-3 22:26
这是什么原理？可以解释一下吗？

有两条：
1是，异或运算既满足交换律也满足结合律；
2是，与自己异或结果是0且0与一个值异或结果就是那个值。

作者: 鹈鹕 时间: 2022-6-11 20:17

dzbj 发表于 2020-5-20 17:09
请教两个问题如下应该是最傻愣的方法吧第一这样也不限制长度不管是char还是int 因为过程变量的长度是相 ...

异或运算是CPU最拿手的运算之一，与赋值也不相上下，都可以是单周期单字节指令，速度上差不了多少只是程序的可读性差点。赋值的方法要开辟第三个变量并也是要对其操作的，时间上不见得有多少优越性。

作者: 鹈鹕 时间: 2022-6-11 20:40

guyunfeng 发表于 2020-5-16 10:50
溢出不影响结果，楼主方向错了。

溢出的确不影响结果，但楼主的方向哪里错了？他这个方法的结果不对吗？这两种方法都有可读性问题，但相比之下很显然楼主的更专业，可读性、严格性要好得多，常用C语言尤其是汇编语言的都对溢出、反码补码很在乎，这是习惯。我还是第一次看到这么做，看到加减法时也立即想到了有溢出问题，假如是别人写的程序要我来检查的话，我肯定要多花时间精力甚至询问编程者来肯定它的正确性，而楼主的方法严格明了，不必跟任何人商量，可读性、专业性楼主的要好得多，何来“方向错误”？

作者: 鹈鹕 时间: 2022-6-11 20:49

单片机爱好者223 发表于 2021-7-14 19:17
PUSH A
MOV A,B
POP B

你这是汇编语言，你这么做恰恰是舍近求远，微处理器、单片机都有交换指令，一条指令即可，早年的Z80是XCHG，86处理器也是，51的汇编写法好像是XCH，当目标和原都是寄存器时，交换指令是典型的单周期单字节指令。

作者: 鹈鹕 时间: 2022-6-11 21:05

1823711995 发表于 2020-4-30 16:52
把加法换为减法不就可以了？减法不会溢出，也比异或效率高

换为减法也可以，但也有问题，小减大会得到补码，这个你想过没有？但是，也不影响结果，也行得通，可读性那就比加法还差。。。。“减法比异或效率高”——这个是错的，【异或】运算是CPU最拿手的指令，无出其右，你大概不太熟悉数字电路，加法电路就是异或电路，如果是单纯的异或那就连进位都不需要，完整的加法电路就是带进位的异或电路。

作者: 鹈鹕 时间: 2022-6-11 21:19
这个方法不会比更流行的赋值方法慢，异或运算是CPU上处理起来最快的指令，不会比赋值慢,更不会比加减法慢，它们都可以是单字节单周期指令，楼主的方法比加减法要好得多，相比之下严格、明了得多，老手都会用楼主的方法而不会去用加减法的虽然它也正确，加减法明显的很笨拙、不专业。

作者: 鹈鹕 时间: 2022-6-11 21:56

yzwzfyz 发表于 2021-6-23 15:42
1、程序运行时间长；
2、占用存储器多；
3、不实用。

不会的，如果是汇编语言，这个算法只快不会慢，它少用了一个变量怎么会“占用存储器多”呢？

作者: f556 时间: 2023-9-23 12:08

鹈鹕发表于 2022-6-11 21:56
不会的，如果是汇编语言，这个算法只快不会慢，它少用了一个变量怎么会“占用存储器多”呢？

高手！谢谢你的多个回复，分析的到位、专业！

欢迎光临 (http://www.51hei.com/bbs/)