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

异或运算法则

交换率：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

参考

1. http://www.cnblogs.com/kaituorensheng/archive/2013/04/03/2998829.html
2. http://blog.csdn.net/dahlwuyn/article/details/41700489
3. http://blog.csdn.net/hejun_haitao/article/details/52857474