汉明距离之和

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;
}

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

Answer 1

你可以单独考虑位的位置。这给了你 32（或其他一些数量）更简单的问题，你仍然需要计算所有海明距离对的总和，除了现在它超过 1 位数字。

两个1位数字之间的汉明距离就是它们的异或。

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

因此，为了重申该问题的答案，您取一个位位置，计算 0 的数量和 1 的数量，将它们相乘以获得该位位置的贡献。对所有位位置求和。比连环问题还要简单，因为在这个问题中每一位的贡献权重都是1

Answer 2

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

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;
}

汉明距离之和

Sum of Hamming Distances

optimization

hamming-distance