BYR Achieve · 镜像论坛

有趣算法--“异或” 原理及应用

2017/10/1镜像同步2 回复

异或运算法则交换率：a^b=b^a 结合率：(a^b)^c=a^(b^c) 自反性：a^b^a=b 其它：a^0=a a^a=0 应用case 1、2n+1个整数中只有一个单着，求出这个单着的数。如：1，2，3，2，1 单着的数为3 思路：利用异或运算的几个法则： a^a=0 , 0^a=a, 结合 “结合律”，直接将2n+1个数进行异或运算，结果即为要找的单着的数 int[] arr = new int[]{1, 2, 3, 2, 1}; int result = arr[0]; for (int i = 1; i < arr.length; i++) { result ^= arr[i]; } System.out.println(result); 2、1到1000连续整数额外加入一个数x，其中 1<=x<=1000, 求x 思路一：先求出所有1001个数组成的和sum1001, 然后求出1到1000连续整数的和sum1000, 两者的差值即为所求的数sum1001-sum1000 思路二：利用异或运算的法则：(T^a)^T=a , 先求出1001个数的异或结果R1001, 然后求出1到1000连续整数的异或结果R1000,两者再进行一次疑惑即为所求的数R1001^R1000 思路二 VS 思路一: 前者运算速度更快，当数据量很大时思路一可能存在溢出的可能 3、从1到10w连续的整数中剔除两个整数，并打乱顺序，求出被剔除的两个整数参考：http://blog.csdn.net/dahlwuyn/article/details/41700489 参考 http://www.cnblogs.com/kaituorensheng/archive/2013/04/03/2998829.html http://blog.csdn.net/dahlwuyn/article/details/41700489 http://blog.csdn.net/hejun_haitao/article/details/52857474 转自：http://www.k6k4.com/blog/show/aaakwrjab1506833809900

订阅后，新回复会通过你的通知中心匿名送达。