137. Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

class Solution {
public:
    //利用一个32位bit数组来处理，数组中所有的数都是int，32位表示
    //所有数的第i位的1的个数应该是(3*k+1)或者0。
    int singleNumber(vector<int>& nums) {
        int bit[32]={0};
        int res=0;
        for(int i=0;i<32;i++){
            for(int j=0;j<nums.size();j++){
                bit[i]+=(nums[j]>>i)&1;//取第i位
            }
            res+=bit[i]%3<<i;
        }
        return res;
    }
};