【java面试题】异或的使用

两个题：
1、给出一个int数组，里面只有一个数出现的次数为奇数次，找出这个数。要求时间复杂度为O(N)。

2、给出一个int数组，里面只有两个数出现的次数为奇数次，找出这两个数。要求时间复杂度为O(N)。

实现代码：

import java.util.Scanner;

public class question {

	//找出唯一一个出现次数为奇数次的数
	public static void seOne(int a[]){
		int e1 = 0;
		for(int i : a){
			e1 = e1^i;
		}
		System.out.println("奇数次的数为："+ e1);
	}
	
	//找出两个出现次数为奇数次的数 c和d
	public static void seTwo(int a[]){
		int e1 = 0;
		for(int i : a){
			e1 = e1^i;
		}
		//此时  e1=c^d ; e1 ！= 0;
		//
		//将数组中的所有数据分为两类，一类是第八位上是0的数据，一类是第八位上是1的数据。（也可以是其他位）
		//那么c和d一定分别在这两类中
		int rightOne = e1 & (~e1 + 1);//提取出最右的1.
		int e2 = 0;
		for(int cur : a){
			if((cur & rightOne) == 0){
				e2 ^= cur;
			}
		}
		//此时，e2为c或d中的一个。
		e1 = e1^e2; //此时，e1为c或d中的另一个。
		System.out.println("两个书分别为："+e1+" "+e2);
		
		
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = {3,2,4,2,4,5,5}; 
		int[] b = {3,2,4,2,4,5,5,7};
		seOne(a);
		seTwo(b);
	}

}