leetcode-477

477. 汉明距离总和

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。

计算一个数组中，任意两个数之间汉明距离的总和。

示例:

输入: 4, 14, 2

输出: 6

解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

注意:

1. 数组中元素的范围为从 0到 10^9。
2. 数组的长度不超过 10^4。

解法

解法1

暴力题解，但是这样会超时

官方题解

在计算汉明距离时，我们考虑的是同一比特位上的值是否不同，而不同比特位之间是互不影响的。

对于数组$nums$中的某个元素$val$，若其二进制位为1，我们只需统计$nums$中有多少元素的第$i$位为0，既计算出了$val$与其他元素在第$i$位上的汉明距离之和。

具体地，若长度为$n$的数组$nums$的所有元素二进制的第$i$位共有$c$个1，$n-c$个0，则这些元素在二进制的第$i$位上的汉明距离之和为
$$
c*(n-c)
$$
我们可以从二进制的最低位到最高位，逐位统计汉明距离。将每一位上得到的汉明距离累加即为答案。

具体实现时，对于整数$val$二进制的第$i$位，可以用 (val>>i)&1获得第$i$位的值。此外，由于$10 ^ { 9 } < 2 ^ { 30 }$，可以直接从二进制的第0位枚举到第29位。

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        # 二进制的第 0 位枚举到第 29 位，遍历数组元素的每一位
        for i in range(30):
            c = sum((val>>i)&1 for val in nums)
            ans += c *(n-c)
        
        return ans