软件工程师面试100题(算法)之找出数组中两个只出现一次的数字(位运算实现)

程序员面试100题(算法)之找出数组中两个只出现一次的数字(位运算实现)

// 程序员面试100题(算法)之找出数组中两个只出现一次的数字 

#include "stdafx.h"  
#include<iostream>  

using namespace std;  

bool Is1(int data,  unsigned int location)
{
	data = data >> location;

	return (data & 1);
}

int FindFirst1(int num)
{
	int indexBit = 0; 

	while (((num & 1) == 0) && (indexBit < 32)) 
	{ 
		num = num >> 1; 
		++ indexBit; 
	} 

	return indexBit; 
}

void FindNum(int data[], unsigned int length, int &num1, int &num2)
{
	if(0 == length || 1 == length)
		return;

	int resultExclusiveOR = 0; 
	for (int i = 0; i < length; ++ i) 
		resultExclusiveOR ^= data[i]; 

	unsigned int indexOf1 = FindFirst1(resultExclusiveOR); 
	num1 = num2 = 0;
	int j = 0;

	for (int j = 0; j < length; ++ j) 
	{ 
		if(Is1(data[j], indexOf1)) 
			num1 ^= data[j]; 
		else 
			num2 ^= data[j]; 
	} 
}

int _tmain(int argc, _TCHAR* argv[])
{
	int data[12] = {1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 4, 3};
	int num1 = 0, num2 = 0;

	FindNum(data, 12, num1, num2);
	cout << num1 << endl << num2 << endl;

	return 0;
}