477. 汉明距离总和

[力扣原题链接](https://leetcode-cn.com/problems/total-hamming-distance/)

## 题目

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

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

**示例 1:**

```
输入: 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的数量，累加即可得到结果。

## 代码

语言：Java

```
public int totalHammingDistance(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = i+1; j < nums.length; j++) {
                result += hammingDistance(nums[i], nums[j]);
            }
        }
        return result;
    }

public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
```

## 力扣官方代码
**思路**
方法一：逐位统计
在计算汉明距离时，我们考虑的是同一比特位上的值是否不同，而不同比特位之间是互不影响的。

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

具体地，若长度为`n`的数组`nums`的所有元素二进制的第`i`位共有`c`个`1`，`n−c`个`0`，则些元素在二进制的第`i`位上的汉明距离之和为

`c⋅(n−c)`

我们可以从二进制的最低位到最高位，逐位统计汉明距离。将每一位上得到的汉明距离累加即为答案。

具体实现时，对于整数`val`二进制的第 ii 位，我们可以用代码 `(val >> i) & 1`来取出其第`i`位的值。此外，由于 `10^9<2^30`，我们可以直接从二进制的第`0`位枚举到第`29`位。

**代码**
```
class Solution {
    public int totalHammingDistance(int[] nums) {
        int ans = 0, n = nums.length;
        for (int i = 0; i < 30; ++i) {
            int c = 0;
            for (int val : nums) {
                c += (val >> i) & 1;
            }
            ans += c * (n - c);
        }
        return ans;
    }
}
```