关于异或的运用问题

020730

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

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

复制代码

jackz007

1. a ^ b 两个数对应二进制位做异或，如果对应位相等得 0，不相等得 1，例如：
   
2. 
   
3. 171 ^ 229 = 0xab ^ 0xe5 = 0x4e = 78
   
4. 
   
5. 1 0 1 0 1 0 1 1   0xab = 171
   
6. 1 1 1 0 0 1 0 1   0xe5 = 229
   
7. ----------------
   
8. 0 1 0 0 1 1 1 0   0x4e =  78

复制代码

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

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

复制代码

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

1. 0 0 0 0 0 0 0 1     1  a[0]
   
2. 0 0 0 0 1 0 0 0     8  a[1]
   
3. ----------------
   
4. 0 0 0 0 1 0 0 1     9  ret
   
5. 0 0 0 0 0 0 1 0     2  a[2]
   
6. ----------------
   
7. 0 0 0 0 1 0 1 1    11  ret
   
8. 0 0 0 0 0 0 1 1     3  a[3]
   
9. ----------------
   
10. 0 0 0 0 1 0 0 0     8  ret
    
11. 0 0 0 0 0 1 0 1     5  a[4]
    
12. ----------------
    
13. 0 0 0 0 1 1 0 1    13  ret
    
14. 0 0 0 0 0 0 1 1     3  a[5]
    
15. ----------------
    
16. 0 0 0 0 1 1 1 0    14  ret
    
17. 0 0 0 0 0 0 1 0     2  a[6]
    
18. ----------------
    
19. 0 0 0 0 1 1 0 0    12  ret
    
20. 0 0 0 0 1 0 0 0     8  a[7]
    
21. ----------------
    
22. 0 0 0 0 0 1 0 0     4  ret
    
23. 0 0 0 0 0 0 0 1     1  a[8]
    
24. ----------------   
    
25. 0 0 0 0 0 1 0 1     5  ret

复制代码

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

一颗yan

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