关于异或的运用问题

020730

问题：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
疑问：这个代码是正确的，但是自己不太理解

public class Test06 {
    //这是一个main方法，是程序的入口：
    public static void main(String[] args) {
        //给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
        int[] arr = {1,8,2,3,5,3,2,8,1};
        int cnt = findNum(arr);
        System.out.println("只出现了一次的元素为："+arr[cnt]);
    }
    //老师的代码--->还未懂
    public static int findNum(int[] a){
        int ret = a[0];
        for(int i=1;i<a.length;i++){
            ret ^= a[i];
        }
        return ret;
    }
}

jackz007

 a ^ b 两个数对应二进制位做异或，如果对应位相等得 0，不相等得 1，例如：

171 ^ 229 = 0xab ^ 0xe5 = 0x4e = 78

1 0 1 0 1 0 1 1   0xab = 171
1 1 1 0 0 1 0 1   0xe5 = 229
----------------
0 1 0 0 1 1 1 0   0x4e =  78

        两个相同的数作异或，得到的值一定是 0，二进制位的异或是有累积效应的
        所以，55 ^ 127 ^ 8 ^ 55 ^ 127 = 8
        对于

        int[] a = {1,8,2,3,5,3,2,8,1} ;
        int ret = a[0];
        for(int i=1;i<a.length;i++){
            ret ^= a[i];
        }

        就是 a 的 8 个元素连续做异或：ret = a[0] ^ a[1] ^ a[2] ^ a[3] ^ a[4] ^ a[5] ^ a[6] ^ a[7] ^ a[8]

0 0 0 0 0 0 0 1     1  a[0]
0 0 0 0 1 0 0 0     8  a[1]
----------------
0 0 0 0 1 0 0 1     9  ret
0 0 0 0 0 0 1 0     2  a[2]
----------------
0 0 0 0 1 0 1 1    11  ret
0 0 0 0 0 0 1 1     3  a[3]
----------------
0 0 0 0 1 0 0 0     8  ret
0 0 0 0 0 1 0 1     5  a[4]
----------------
0 0 0 0 1 1 0 1    13  ret
0 0 0 0 0 0 1 1     3  a[5]
----------------
0 0 0 0 1 1 1 0    14  ret
0 0 0 0 0 0 1 0     2  a[6]
----------------
0 0 0 0 1 1 0 0    12  ret
0 0 0 0 1 0 0 0     8  a[7]
----------------
0 0 0 0 0 1 0 0     4  ret
0 0 0 0 0 0 0 1     1  a[8]
----------------   
0 0 0 0 0 1 0 1     5  ret

        最后结果 ret = 5 ，说明 a 的 9 个元素中，只有 5 是单次出现的。

一颗yan

二楼神解，谢谢知识分享。楼主这里打印错了  System.out.println("只出现了一次的元素为："+cnt);