最近开始刷题，特别喜欢系列的题，明显感觉到思路的循序渐进．

/**
* @file Single_Number.cc
* @brief
* @version 0.1.00
* @date 2015-09-10
*/
#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
using namespace std;
//2*k+1 按位异或，自己与自己异或为0，0与其他数异或是其他数
int singleNumber_1(const vector< int >& nums) {
   int ans = 0;
   for (int i=0; i<nums.size(); i++) {
       ans ^= nums[i];
   }
   //cout<<ans<<endl;
   return ans;
}
//3*k+1　转为２进制，出现３遍的数，对应的二进制数也出现３遍
int singleNumber_2(const vector<int>& nums) {
   assert(nums.size()%3 == 1);
   int ans = 0;
   for (int i=0; i<8*sizeof(i); i++) {
       int MASK = (1<<i);
       int sum_bit = 0;
       for(int j=0; j<nums.size(); j++) {
           sum_bit += ((MASK & nums[j])==0)?0:1;
       }
      // cout<<sum_bit<<"t"<<endl;
       ans |= ((sum_bit%3)==0?0:MASK);
   }
   return ans;
}
//m*k的都可以做,m为偶数用_1,为奇数用_2

//2*k+2 如果能转化为两个2*k'+1就很容易解决了．将所有数异或相当于将两个只出现一次的数异或．必然可以知道，这两个数某一位上不同，按这个位上的不同就可以将问题化为子问题了．
vector <int> singleNumber_3(const vector< int >& nums) {
   
   assert(nums.size()%2 == 0);
   int diff = singleNumber_1(nums);
   int i=0;
   int temp;
   for (; i<sizeof(diff)*8; i++) {
      temp = (1<<i);
      cerr<<temp << "t" << (temp&diff) <<endl;
      if ((temp&diff) > 0)
          break;
   }
   cerr<<"aa"<<temp<<endl;
   //根据i上的bit值分为两组
   vector< int > one;
   vector< int > zero;
   for (int j=0; j<nums.size(); j++) {
       if ((temp&nums[j]) > 0) {        //按位与的优先级特别低
           one.push_back(nums[j]);
           cerr<<"bb"<<nums[j]<<endl;
       } else {
           zero.push_back(nums[j]);
           cerr<<"cc"<<nums[j]<<endl;
       }
   }
   vector< int > ans;
   ans.push_back(singleNumber_1(one));
   ans.push_back(singleNumber_1(zero));
   return ans;
}
//网上找的改进版
vector <int> singleNumber_3_2(const vector<int> & nums) {
   assert(nums.size()%2 == 0);
   int temp = 0;
   for (int i=0; i<nums.size(); i++) {
       temp ^= nums[i];
   }

   int MASK = (temp&(~(temp-1)));//可以找到为１的最低位

   int A=0;
   int B=0;
   for (int i=0; i<nums.size(); i++) {
       if ((MASK&nums[i])==0) {
          A ^= nums[i];
       } else {
          B ^= nums[i];
       }
   }
   cerr << A << "t" << B <<endl;
   vector< int > ans(2);
   ans[0] = A;
   ans[1] = B;
   return ans;
   //return vector<int> ({A,B});

}
//3*k+2 同_3分为两个3*k'+1,用_2找到一个不同bit位
int main() {
   int n;
   //cout<<sizeof(n)<<endl;
     
   while(cin>>n) {
       //cout<<sqrt(n)<<endl;
       vector<int> nums(n);
       for (int i=0; i<nums.size(); i++) {
           cin>>nums[i];
       }
       singleNumber_3_2(nums);
   }

   return 0;
}