> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/bit-manipulation/total-hamming-distance.md).

# Total Hamming Distance

https\://leetcode.com/problems/total-hamming-distance/description/

> The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
>
> Now your job is to find the total Hamming distance between all pairs of the given numbers.
>
> Example:
>
> Input: 4, 14, 2
>
> Output: 6
>
> Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
>
> showing the four bits relevant in this case). So the answer will be:
>
> HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
>
> Note:
>
> Elements of the given array are in the range of 0 to 10^9
>
> Length of the array will not exceed 10^4.

## Thoughts

一对整数的海明距离定义为它们二进制不一样的位数，给定一组整数，问他们俩俩之间海明距离的总和。根据例子可观察到对每一位，每个1都可以和其它的0形成一个海明距离。因此对整数的32位每位都统计有多少1，count\_1 \* (N - count\_1)就是当前位所增加的海明距离。

## Code

```
/*
 * @lc app=leetcode id=477 lang=cpp
 *
 * [477] Total Hamming Distance
 */

// @lc code=start
class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        const int N = nums.size();
        int res = 0;
        for (int i = 0; i < 32; ++i) {
            int one_c = 0;
            for (auto num : nums) {
                if ((num >> i) & 1 == 1) ++one_c; 
            }
            res += one_c * (N - one_c);
        }
        return res;
    }
};
// @lc code=end


```

```
class Solution {
    public int totalHammingDistance(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int oneCount = 0;
            for (int num : nums) {
                oneCount += (num >> i) & 1;
            }
            res += oneCount * (nums.length - oneCount);
        }
        return res;
    }
}
```

## Analysis

时间O(N).