Leetcode 136: single number/ Leetcode 137: single numberII

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

本题的做法很巧妙，利用bit operation里面的^异或操作，如果存在数字成对出现，那么异或操作后，成对出现的数字就消除了。 

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

 Single number II
 本题也是利用bit operation来解， 对一个int的每一位进行运算， 分别统计nums中每一个int的每一位出现1的次数，如果该位所有出现1的次数不能被3整除，除3后有数剩余，那么最后的single number 该位为1. 

这题利用位操作（bit operation） 很巧妙， 对于一些number的题目，如果 常见的方法做 不能满足题目要求时，可以考虑用bit operation来试试。 异或，移位， 按位操作等等。
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        //sanity check
        if (nums.size() == 0) return -1;
        int rst = 0;
        for (int i = 0; i < 32; i++) {
            int c = 0;
            int d = 1 << i;
            for (int j = 0; j < nums.size(); j++) {
                if (nums[j] & d) c++;
            }
            if (c % 3) rst |= d;
        }
        return rst;
    }
};