# Sum of pairwise Hamming Distance

Hamming distance between two non-negative integers is defined as the number of positions at which the corresponding bits are different.

For example,

HammingDistance(2, 7) = 2, as only the first and the third bit differs in the binary representation of 2(010) and 7 (111).

Given an array of N non-negative integers, find the sum of hamming distances of all pairs of integers in the array.

Example

```Let f(x, y) be the hamming distance defined above.

A=[2, 4, 6]

We return,
f(2, 2) + f(2, 4) + f(2, 6) +
f(4, 2) + f(4, 4) + f(4, 6) +
f(6, 2) + f(6, 4) + f(6, 6) =

0 + 2 + 1
2 + 0 + 1
1 + 1 + 0 = 8```
###### 思路1

Solution:

Time: O(n^2)
Space: O(1)

public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public int hammingDistance(final List<Integer> A) {
int d = 0;
for (int i = 0; i < A.size(); i ++) {
int a = A.get(i);
for (int j = i + 1; j < A.size(); j ++) {
int b = A.get(j);
d += countSetBits(a ^ b);
}
}
return (d * 2) % 1000000007;
}

private int countSetBits(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>= 1;
}
return count;
}
}

###### 思路2

1 | 0 0 1
2 | 0 1 0
3 | 0 1 1
4 | 1 0 0

Solution:

Time: O(n)
Space: O(1)

public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public int hammingDistance(final List<Integer> A) {
long d = 0;
long n = A.size();
for (int i = 0; i < 32; i ++) {
long ones = 0;
for (int j = 0; j < n; j ++) {
int v = A.get(j);
ones += (v >> i) & 1;
}
d += ones * (n - ones) * 2;
}
return (int) (d % 1000000007);
}
}