# \[477]\[中等] 汉明距离总和

## 题目描述

[477. 汉明距离总和](https://leetcode-cn.com/problems/total-hamming-distance/)

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

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

示例:

```
输入: 4, 14, 2

输出: 6

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

注意:

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

## 解题思路

如果将数组中的数字两两计算汉明距离, 然后加和, 时间复杂度为$$O(n^2)$$, 太高.

一个$$O(n)$$的解决方法是, 从位的角度切入, 指定一个位, 例如所有数字最低的一位, 如果这个位为1的数字共有$$x$$个, 为0的数字共有$$y$$个, 而只有两个数字在此位上不同时才会产生汉明距离, 因此纵观数组中所有的数字, 此位的汉明距离之和为$$x \times y$$.

由于位与位之间的汉明距离没有关系, 因此遍历所有位即可. 而python中的int是32位的整数, 因此遍历这32位, 求出每个位上数组中所有数字的汉明距离之和, 然后总计在一起即可.

```python
class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        n = len(nums)

        final = 0
        for i in range(32):
            count1 = 0
            p = 1 if i == 0 else p << 1
            for num in nums:
                if num & p != 0:
                    count1 += 1
            final += count1 * (n - count1)
        return final
```

## 参考资料

[汉明距离总和](https://leetcode-cn.com/problems/total-hamming-distance/solution/yi-ming-ju-chi-zong-he-by-leetcode/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/wei-yun-suan/477-han-ming-ju-li-zong-he.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.