477. Total Hamming Distance

#### QUESTION:

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:

1. Elements of the given array are in the range of `0 `to `10^9`
2. Length of the array will not exceed `10^4`.

#### EXPLANATION:

4是0100 ，14是1110，2是0010. 那么第一位1的个数是1，那么差别就是1*2，因为14和其他两个是不同的。再算出第二位，只有2是0，与其他两个是不同的，那么也是2，第三位的也是2，第四位全相同就不说了，加起来就是6了。

#### SOLUTION:

``````public class Solution {
public int totalHammingDistance(int[] nums) {
int n = 31;
int len = nums.length;
int[] countOfOnes = new int[n];
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;
}

}
``````
>