find unique num.cpp

#include <vector>
#include <iostream>
#include <cstdio>
using namespace std;

pair<int, int> findNumber(const vector<int>& vec) {
  int xsum = 0;
  int sz = vec.size();

  // calc for total arrary
  for (int i = 0; i < sz; ++i)
    xsum ^= vec[i];

  // find the bit to distinguish
  int flag = 0;
  for (int i = 0; i < sizeof(int) && !(xsum & (1 << i)); ++i)
    ++flag;

  int num1 = 0;
  int num2 = 0;
  for (int i = 0; i < sz; ++i) {
    if (vec[i] & (1 << flag)) {
      num1 ^= vec[i];
    } else {
      num2 ^= vec[i];
    }
  }
  if (num1 > num2)
    swap(num1, num2);
  return make_pair(num1, num2);
}

void test(vector<int> vec) {
  pair<int, int> pint = findNumber(vec);
  for (auto item : vec) cout << item << ' ';
  cout << endl;
  cout << pint.first << ' ' << pint.second << endl;
  cout << endl << endl;
}

int main() {
  test({1, 2});
  test({1, 2, 3, 3});
  test({2, 3, 2, 3, 4, 5, 4, 7});
  test({1, 3, 4, 4, 5, 5});
  test({1, 4, 5, 5, 7, 7, 8, 8});

  return 0;
}