程序员面试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;}