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.

Brute force: time limit exceed

思路：integer一共32位, int[] count = new int[32]记录每个bit一共在几个数字中on（一共n = nums.length个数字）。对于一个bit，on的次数 k 次，off的次数 n-k 次，则对于total distance的贡献是 k * (n-k)，因为每一个(on, off)的组合都会给total distance加1.

public int totalHammingDistance(int[] nums) {
int N = nums.length;
int[] count = new int[32]; // count for when the bit is on
for (int n : nums) {
int i = 0;
while (n > 0) {
count[i++] += n & 1;
n >>= 1;
}
}
int total = 0;
for (int i = 0; i < 32; i++) {
total += count[i] * (N - count[i]);
}
return total;
}

### Like this:

Like Loading...