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:

1
2
3
4
5
6
7
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.

思路

经过一番思考之后，可以发现如下规律。

1
2
3
4
0100
1110
0010
0010

竖着看，每一列都是一个bit的汉明距离，和1的个数有关。

如果没有1，这四个数在这一位的汉明距离就是0。

如果有一个1，汉明距离就是3，2个1，汉明距离就是4，3个1，汉明距离还是3，全是1，汉明距离就是0

可以总结，每一位的汉明距离就是（1的个数）×（总数-1的个数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def totalHammingDistance(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        stats = []
        for i in range(36):
            stats.append(0)
        for k in nums:
            count = 0
            while k:
                if (k & 1):
                    stats[count] += 1
                k = k >> 1
                count += 1
        ans = 0
        length = len(nums)
        for j in stats:
            ans += j * (length - j)
            
        return ans