477. Total Hamming Distance

https://leetcode.com/contest/leetcode-weekly-contest-13/problems/total-hamming-distance/

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Solution:
May use the bitwise operation to reduce the time complexity. All the numbers can be viewed as 32 bits with 0s and 1s. So for each bit, we just need to count the total number of 1s, then the total number of 0s will be (total numbers - the numbers of 1s). And the contribution to the Hamming distance will be count of 1s times the count of 0s. Similar argument can be applied to all the rest bits.

Code:

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int res = 0;
        for(int i=0; i<32; ++i){
            int one = 0;
            for(int j=0; j<nums.size(); ++j){
                if((1<<i) & nums[j]) ++one;//one is the numbers of 1s;
            }
            res += one*(nums.size()-one);// nums of 1s x nums of 0s
        }
        return res;
    }
};