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的个数

代码

1
2
3
4
5
6
7
8
9
10
11
12
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;
}