477. 汉明距离总和

一开始暴力了，想想就不行，立方级别的时间复杂度肯定不行的。
不用两两异或，通过统计这个数组中每一位的1的个数和0的个数即可。因为是有范围不大于10^9也就是2 ^30，所以我们只要遍历0到30位就行，用每一位上的1的个数和0的个数相乘，就是这一位上能提供的所有汉明距离的和。
1就是(val>>i)&1，0的个数就是n-c。为什么是0和1的相乘，就相当于做一个组合运算，用这一位是1的数字和另一个这一位是0的数字异或才能提供11的汉明距离，所以只要0的个数1的个数就是这一位所能提供的汉明距离和。

class Solution {
    
public:
    int totalHammingDistance(vector<int>& nums) {
    
        // int res = 0;
        // int a = 0;
        // for(int i = 0; i < nums.size(); ++i){
    
        // for(int j = i + 1; j < nums.size(); ++j){
    
        // a = nums[i] ^ nums[j];
        // while(a != 0){
    
        // a &= (a-1);
        // res++;
        // }
        // }
        // }
        // return res;

        //不用两两异或，通过统计这个数组中每一位的1的个数和0的个数即可
        //
        int res = 0, n = nums.size();
        for(int i = 0; i < 30; ++i){
    
            int c = 0;
            for(int val : nums){
    
                c += (val >> i) & 1;
            }  
            res += c * (n-c);
        }
        return res;
    }
};