共有回帖数 0 个
-
刚在网上找了一下关于2数不借助第3个数互换的问题,竟然没找到,可能是我方法不对,然后自己想了会,这里我将我自己的思路说一下:
两数如何不借助第三者进行互换呢？公式可能网上都查的到，这里就不太啰嗦。我这里主要是想对这个问题进行分析，在你第一次接触到这个问题时，你该如何下手去思考。
在这里我举一个例子，然后针对这个例子进行讲解；
说明2个数
A:76H 01110110B
B:58H 01011000B
我们来分析这两个数是如何互换的。
1。〉两数不依靠第三个数进行互换，无外乎就是其自身的一些位运算，如下：
A 与 B ：50H 01000000B
A 或 B : 7EH 01111110B
A 异或 B : 2EH 00101110B
2。〉我们反过来推。AB能否一次就互换过来呢？实践告诉我们是不可能的，要不也不会在一些经典的算法中还要借助第三者来做桥梁。那么，我们只能成功将其中一个换到另一个(A换到B)上，在将另一个放到第一个(B到A)上。好像有点啰嗦，其实不然，你有没有想过，既然B已经被换掉了，那我们如何将B放到A上呢？那我们仔细想想，有没有一个什么数，能使A通过和它经过某种运算就得到B，同理，也可以使B通过它经过某种运算就得到A？也就是说A，B能通过它达到互换？哈哈。。 说了这么多，这个数才是我们的主题。整篇的核心就是如何找到这个数。
3。〉那么我们如何找到这个数呢？不忙，我们来分析一下1。〉中的各位运算规律。对于各位的操作如下：
A 与 B ：相同不变，不同为0
A 或 B : 相同不变，不同为1
A 异或 B : 相同为0，不同为1
看到上面的规律了吗？第一感觉是什么？异或运算很有特点，完全就是1==0的转换，没错！就是这样，我在上面把互换的数全部写成了二进制的形式，原因就在这里。核心思想也在这里。
A，B通过某中介数可进行互换。而异或运算的特点不是正好可以帮助我们实现这一点吗？我们能否把AB两数中相同的位提出。结果如下：
AB相同的部分：01_1___0B 中间不同部分我用底横线替代了。到这里你有没有想到点什么？没错！这个数就是我们要找的中介数。规律如下：
中介数 ：01_1___0B
A数不同位：__1_011_B
B数不同位：__0_100_B
中介数 或运算 A =〉A
中介数 或运算 B =〉B
那么，我们将中介数中间的不同位全部补上1,相同的位换上0看看:
真中介数:00101110B
哈哈.. 这个才是我们真正的中介数.看看我们下面的运算.
B = A 异或 B
A = B 异或 A
4.好了,我们只要知道这个真中介数,就可以利用它进行互换了.那么我们如何得到这个中介数呢?上面的思路搞通了,这个中介数的得来就不费什么功夫了.
真中介数 = A 异或 B
哈哈..,就这么简单.我们将得到的真中介数放到其中一个数中,然后就可以运算得到了.
5.公式如下:
A = A 异或 B ;A已被改变,不过没关系,我们可以获取它
B = A 异或 B ;把A换到B上来了
A = A 异或 B ;我们已经把B也拿回来了.
6.全文到此完! 顺便说一句,我这里只是利用单字节的两数互换,起始对于多字节的两数互换也是一样的道理.大家没事无聊闲着荒可以自己试着写写看.
楼主 2016-02-12 15:17 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
