位运算之两个孤立的数问题（hihocoder）

题目：

一个整型数组里除了两个数字（互不相同）之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

输入

第一行：数组的长度N(1<n<100000)

第二行：N个整数，空格隔开

输出

只出现了1次的那两个数，小的在前大的在后，空格隔开

样例输入

10

5 5 6 7 9 9 7 3 3 2

样例输出

2 6

思路：

1.已知把一个数组内元素遍历异或运算后，会消去里面相同的数（之前解释过），显然

当数组里有两个单独的数时，遍历异或肯定得不到两个解，但会得到一个不为零的解。

2.易知该解的二进制一定至少有一位为1，即可用这一位来控制将原数组分开做异或运算，

最终将得到这两个孤立的数。

3.与一个数二进制第一个1做比较操作，可以简单设置一个flag 整型标记，初值为1，通过

while循环 不断进行 flag >>= 1，操作找到该位置。在通过flag将数组分开运算。

（Java语言描述）

import java.util.Scanner;

public class Main{

public static void main(String[] args) {

int min = 0;

int max = 0;

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int[] arr = new int[n];

for(int i = 0; i < arr.length; i++) {

int num = sc.nextInt();

arr[i] = num;

}

int temp = 0;//遍历异或 后那个标尺数

for(int i = 0; i < arr.length; i++) {

temp = temp^arr[i];

}

int flag = 1;//第一个不同的1

while((flag&temp) == 0) {

flag = flag << 1;

}

for(int i = 0; i < arr.length; i++) {

if((flag & arr[i]) == 0) {//表示在该位置上二者不同

min = min^arr[i];

}else {

max = max^arr[i];

}

}

int temp1 = 0;

if(max < min) {

temp1 = max;

max = min;

min = temp1;

}

System.out.println(min+" "+max);

}

}