[leetcode_260]Single Number III

给定数组中，所有数都是成对出现，但是只有两个数，不成对，求出这两个数。
相信一个数的情况大家都知道，使用异或即可解决问题，两个数的话，异或了之后得到的是a^b，但是如何找出a与b呢，从a^b可以得，该值一定不为0，只需要取任何一个位数上不为0的数，将数组分为两类，在异或即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int ab = 0;
        for (int i = 0; i < nums.size(); i++) {
            ab ^= nums[i];
        }

        int pos = 0;
        while(0 == ab % 2) {
            pos++;
            ab /= 2;
        }

        int a = 0;
        int b = 0;
        int tmp = (int)pow(2.0, pos);

        for (int i = 0; i < nums.size(); i++) {
            if ((nums[i]^tmp) == (nums[i] - tmp)) {
                a ^= nums[i];
            }
            else {
                b ^= nums[i];
            }
        }

        vector<int> ans(0);
        ans.push_back(a);
        ans.push_back(b);
        return ans;
    }
};