[Jianzhi offer] 56 - ii Number of occurrences of numbers in the array II

The finger of the sword Offer 56 - II. The number of occurrences of numbers in an array II

subject

In an array nums Except that a number appears only once , The other numbers appear three times . Please find the number that only appears once

Ideas

  Add up every bit of the binary representation of all the numbers in the array , If someone's sum can be 3 Right place , Then the corresponding bit in the binary representation of the number that only appears once is 0 Otherwise, it would be 1.

Code

class Solution {
    
public:
    int singleNumber(vector<int>& nums) {
    
        int bits[32] = {
    0};
        for(int i = 0; i < nums.size(); i++)
        {
    
            int j = 0;
            while(nums[i])
            {
    
                //  Each binary bit is 1 How many 
                bits[j] += nums[i] % 2; 
                nums[i] /= 2;
                j++;
            }
        }

        int ans = 0;
        for(int i = 0; i < 32; i++)
        {
    
            //  utilize %3  Is there any corresponding position of Lai Qiu 1  If yes, multiply by the corresponding 2 Of i Power 
            ans += (1 << i) * (bits[i] % 3);
        }
        return ans;
    }
};