25.汉明距离总和

题目

解析

1. 以第k位为例
2. 假设所有数字的第k位为：1 0 1 0
3. 汉明距离与 0 1的个数有关
4. 第k位汉明距离总和为 $num_0 * num_1$

   【其中】：
   1. $num_0$：数字0的个数
   2. $num_1$：数字1的个数

代码

int totalHammingDistance(vector<int>& nums) {
    int res = 0;
    for(int i = 0; i < 31; i++) {
        int ones = 0;
        for(auto x : nums) {
            if(x >> i & 1)
                ones++;
        }
        res += ones * (nums.size() - ones);
    }
    return res;
}