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.
Return the answer modulo 1000000007.

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

一个一个pair算。

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

数32个bit中,每个bit有几个1和0,乘一下就是这个bit有几个不同的pair。

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

比如最后一个bit, [1, 2], [1, 4], [2, 3], [3, 4] 是符合要求的,就是有2 * 2 = 4个pair,因为我们也要算[2, 1], [4, 1], [3, 2], [4,3] 所以还要再乘以2.

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);
    }
}