栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

不开额外空间的两数交换

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

不开额外空间的两数交换

两数交换 [不开辟新空间,即额外空间复杂度为O(1)] 1.先上结论

我们采用位运算 按位异或 符号为:“^” 来进行运算

int a=5,b=9;
a=a^b;
b=a^b;
a=a^b;
System.out.println("a="+a);//a=9
System.out.println("b="+b);//b=5
2.按位异或的性质

✔① 0 ^ a = a;

✔② a ^ a = 0;

✔③ 满足交换律、结合律 a ^ b = b ^ a; a ^ b ^ c = a ^ ( b^ c);

✔④ a ^ a ^ …… ^a(n个a异或) 由①②我们不难得出:当n为奇数结果为a; n为偶数结果为0;

3.按位异或的运算过程

设a=5,则a的二进制为0101,则0^a 过程为

0 0 0 0

0 1 0 1          上下对齐,相同为0,不同为1;或者 直接理解成无进位相加

0 1 0 1         (十进制数为5);得到性质①;性质②同理;颠倒前后或者谁先谁会不影响我们最后的无进位相加结果所以性质③成立;


利用性质我们来看这道题:a=5,b=9;

a = a ^ b; b = a ^ b = ( a ^ b) ^ b = a; a = a ^ b = ( a ^ b) ^ a = b;

结果:a与b的值发生了交换;

4.使用范畴

必须保证a和b隶属于不同的空间;比如要交换一维数组中的i,j两个位置的数,我们必须保证 i ! = j,否则异或会把原位置的数变成0;

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/305193.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号