汉明距离之和

Question

我开始准备面试，遇到了这个问题:

• 给定一个整数数组
• 现在计算数组中所有整数的二进制表示中对应位不同的数量之和（汉明距离）。

示例：

given {1,2,3} or {001,010,011} (used 3 bits just to simplify)
result= HD(001,010)+HD(001,011)+HD(010,011)= 2+1+1=4;

---

从纯暴力解决方案的角度来看，我知道我可以在这里使用的唯一优化是在计算汉明距离时进行个体计算，如下所示：

int hamming_distance(unsigned x, unsigned y)
{
    int       dist;
    unsigned  val;

    dist = 0;
    val = x ^ y;    // XOR

    // Count the number of bits set
    while (val != 0)
    {
        // A bit is set, so increment the count and clear the bit
        dist++;
        val &= val - 1;
    }

    // Return the number of differing bits
    return dist;
}

最好的解决这个问题的方法是什么？

- RoadToAnInternship

Answer 1

这是我的C++实现，复杂度为O(n)，空间复杂度为O(1)。

int sumOfHammingDistance(vector<unsigned>& nums) {
    int n = sizeof(unsigned) * 8;
    int len = nums.size();
    vector<int> countOfOnes(n, 0);
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < n; j++) {
            countOfOnes[j] += (nums[i] >> j) & 1;
        }
    }
    int sum = 0;
    for (int count: countOfOnes) {
        sum += count * (len - count);
    }
    return sum;
}

- Chuiwen Ma

Answer 2

您可以分别考虑每个比特位。这给了您32（或其他一些数字）个更简单的问题，其中您仍然必须计算所有汉明距离对的总和，但现在它是针对1比特数字的。

两个1比特数字之间的汉明距离是它们的XOR。

现在它已经成为此问题的最简单情况 - 它已经按比特位拆分。

因此，重申对该问题的答案，您需要取一个比特位，计算0的数量和1的数量，将它们相乘以获取该比特位的贡献。将所有比特位的贡献相加即可。这比链接问题还要简单，因为该问题中每个比特位的贡献权重都为1。

- harold

---

哦，哇，如此简单而又如此有效，我从未想到求和部分会有这么大的帮助！谢谢。 - RoadToAnInternship