位运算------找出唯一成对的数

 1 package com.java.test;
 2 
 3 
 4 import java.util.Arrays;
 5 import java.util.Random;
 6 
 7 public class D1 {
 8     public static void main(String[] args) {
 9         int N = 1001;
10         int[] arr = new int[N];
11         for (int i = 0; i < arr.length - 1; i++) {
12             arr[i] = i + 1;
13         }
14         //最后一个数，是随机数
15         Random r = new Random();
16         arr[arr.length - 1] = r.nextInt(N - 1) + 1;
17 
18         //随机下标
19         int index = new Random().nextInt(N);
20         //调用方法，将随机数放到随机下标处
21         swap(arr, index, arr.length-1);
22         //打印数组方便观察
23         System.out.println(Arrays.toString(arr));
24         //开始找出唯一成对的数
25         /*
26         相当于将数组中的内容和1-1000连续异或
27         即重复的那个数会有三个，其他的数有两个
28         因为一个数异或他本身等于0，所以最后只剩下重复的那个数
29         异或，可以理解为不进位加法:1 +1=0 , 0+0=0 , 1+0=1 .
30         a^b^b=a
31          */
32         //存储结果
33         int x1 = 0;
34         //第一遍异或，1-1000的连续异或
35         for(int i = 1; i <= N-1; i++){
36             x1 = (x1^i);
37         }
38         //此时x1为1-1000连续异或的结果，用于在下面的循环中消除重复
39 
40         //第二遍异或
41         for(int i = 0;i){
42             x1 = x1^arr[i];
43         }
44         //数组中只有重复的数是两个，其他数字均为1个
45         //与第一遍的结果进行连续异或，相当于不重复的数各有两个，而重复的数会出现三个
46         //所以重复的数会剩最后一个
47 
48         System.out.println(x1);
49     }
50 
51     private static void swap(int[] arr, int index, int i) {
52     }
53 }

------------恢复内容开始------------

1-1000这1000个数放在含有1001个元素的数组中，只有唯一的个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间,能否设计一个算法实现?

------------恢复内容结束------------