学步园

#include <iostream>
using namespace std;
/**
 * 题目：有N＋2个数，N个数出现了偶数次，2个数出现了奇数次（这两个数不相等），
 * 问用O（1）的空间复杂度，找出这两个数，不需要知道具体位置，只需要知道这两个值。
 * */

/**
* 假设不相同的两个数字是x和y。他们的异或结果一定不是0，假设为xor。
* xor的最低位1就是他们不相同的其中一位，比如是第lowbit位。
* 那么x的lowbit位为1，y的lowbit位为0，或者相反。
* 
* 我们将所有a[]中第lowbit位为1的所有元素异或起来，这些元素中一定有x没有y
* 其他出现两次的异或都为0抵消了。所以最后结果就是xor ^ x = y这样就求出y了
* x = xor ^ y
*/
void findTwoNumber(int a[], int n){
	int xor = a[0];
	for(int i=1;i<n;i++)
		xor = xor^a[i];

	int lowbit = xor & ~(xor-1);	//利用这个操作可以进保留最低位1，其他全部清零
	int x = 0;
	for(int j=0;j<n;j++){
		if(a[j] & lowbit){			//查看lowbit位是否是1
			x = x^a[j];
		}
	}
	int y = xor ^ x;			

	cout<<x<<endl;
	cout<<y<<endl;

}

int main(){
	int a[] = {1,4,3,1,5,2,2,4,7,3};
	findTwoNumber(a, 10);
	return 0;
}