Java 不使用第三方变量交换两个变量值的四种方法详解
目录
- 变量本身交换数值
- 算术运算
- 指针地址操作
- 位运算
- 简单总结
哈喽,大家好,我是阿Q。前几天有个小伙伴去面试,被面试官的一个问题劝退了:请说出几种不使用第三方变量交换两个变量值的方法。
问题有点绕,好不容易缕清了面试官的问题,却发现答不上来。一时间尴尬无比,只能硬着头皮说不会。
遇到交换变量值的问题,通常我们的做法是:定义一个新的变量,借助它完成交换。
代码如下:
t = a; a = b; b = t;
但问题的重点是“不使用第三方变量”,那就变得“可爱”起来了。思考过后,抛出以下四种方法来解决该问题:
- 变量本身交换数值;
- 算术运算;
- 指针地址操作;
- 位运算;
变量本身交换数值
b = (a + b) - (a = b);
首先执行 a + b 操作,然后将 b 赋值给 a,则 b = a + b - b = a
,这就完成了 ab 的互换操作。
算术运算
如图所示:
OA = a;
OB = b;
AB = b - a;
首先我们把 AB 之间的距离 b - a 赋值给 a,此时 AB = a, OB = b 。
由于要达到 ab 交换的目的,所以 OA 要等于 b,而此时 OA 的距离为 b - a ,所以得将 b - a 赋值给 b ,此时 OA = b, AB = a 。
很容易从图中看出,OB 的距离为 b + a,所以我们只需要将 b + a 赋值给 a 就可以完成两者的交换了。
综上所述,我们的步骤为
int a = 10; int b = 15; a = b - a; //b=15;a=5; b = b - a; //b=10;a=5; a = b + a; //b=10;a=15;
该算法只能用于整型类型。
指针地址操作
我们可以把 a 和 b 想象为内存中的地址值,假设 a 为 0x01ff5e70 ,b 为 0x01ff5e90 ,而 b - a 表示两个变量在内存中的储存位置隔了多少个字节。所以我们理论上也可以按算术运算的逻辑来交换两个变量的值。
代码如下(此处是 c 语言):
//其中 a 和 b 都是指针变量,里边存储着10和20的地址 int *a = new int(10); //a=0x01ff5e70 ,此处代表a中存储的地址 int *b = new int(20); //b=0x01ff5e90 ,此处代表b中存储的地址 //指针变量相减得到20和10的地址间隔了多少个字节,然后转为指针变量 a = (int*)(b-a); //b=0x01ff5e90;a=0x8 b = (int*)(b-a); //b=0x01ff5e70;a=0x8 a=(int*)(b+long(a));//b=0x01ff5e70;a=0x01ff5e90
b - a = 0x01ff5e90 - 0x01ff5e70 = 0x20,0x20 转换为十进制为 32 位,因为一个 int 占4位,所以这里是 0x8 。
以上只是理论状态下的执行过程,如果直接执行是不能实现交换的。因为上边的代码忽略了一个问题:代码编译之后,变量都是存在内存中的,而内存区都会存在基地址。
基地址可以理解为某块内存的起点。上边的数据都是在基地址的基础上做了偏移。
变量的地址 = 变量的基地址 + 变量的偏移地址
当我们进行 b - a 操作的时候,得到结果为 8 ,然后转化为指针变量的时候就会给 8 自动添加基地址,此时的结果就不是 0x8 了,所以会导致结果错误。
另外,地址运算不能出现负数,即当 a 的地址大于 b 的地址时,b - a < 0 ,系统自动采用补码的形式表示负的位移,也会产生错误。
为了解决这个问题,我们只需要保证 b - a 得到的结果不受基地址的影响即可,所以给出以下解决方案。
int *a = new int(10); int *b = new int(20); cout << a << "`````"; cout << b << "`````"; if(a < b){ a = (int*)(b-a); cout << a << "`````"; b=(int*)(b-(long(a)&0x0000ffff)); cout << b << "`````"; a=(int*)(b+long(a)); cout << a << "`````"; } else { b = (int*)(a-b); cout << b << "`````"; a=(int*)(a-(long(b)&0x0000ffff)); cout << a << "`````"; b=(int*)(a+long(b)); cout << b << "`````"; }
执行结果:
0x8dbe70`````0x8dbe90`````0x8`````0x8dbe70`````0x8dbe90`````
看到这,不知道大家是否真的看懂了。反正我第一次看到这儿时,感觉非常清晰(其实完全没有理解),第二次看的时候懵逼了,完全不懂,所以还得大家仔细思考一下才行。
b=(int*)(b-(long(a)&0x0000ffff));
指令的精妙之处就在于采用了位运算中的与运算,将 a 和 0x0000ffff
进行与运算后,b - a 的基地址计算结果被屏蔽,只保留了偏移地址的计算结果,也就是我们需要的字节数。
在交换很大的数据类型时,该方法执行速度比算术算法快。因为它交换的是地址,而变量值在内存中是没有移动过的。
位运算
既然上边用到了位运算,那我们再说一种直接通过“异或“完成交换的方法。
简单介绍一下异或的规则:
- 如果a、b两个值不相同,则异或结果为1;
- 如果a、b两个值相同,异或结果为0。
代码如下
int a=10, b=12;//二进制:a=1010;b=1100; a = a^b;//a=0110;b=1100 b = a^b;//a=0110;b=1010 a = a^b;//a=1100;b=1010 System.out.println("a="+ a +",b="+ b);
执行结果
a=12,b=10
异或运算能够使数据中的某些位翻转,其他位不变。这就意味着任意一个数与任意一个给定的值连续异或两次,值不变。
简单总结
以上四种方法均实现了不借助第三方变量来完成两个变量值的交换:
- 算术运算和位运算计算量相当,只能进行整形数据的交换;
- 地址运算中计算较复杂,可以很轻松的实现大类型(比如自定义的类或结构)的交换;
- 理论上重载 “^” 运算符,也可以实现任意结构的交换;
到此这篇关于Java 不使用第三方变量交换两个变量值的四种方法详解的文章就介绍到这了,更多相关Java 变量值交换内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!