LeetCode Total Hamming Distance 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.

---

本题要求数组中所有数两两之间的汉明距离之和，最笨的方法就是两层循环，然后调用LeetCode Hamming Distance的方法计算每两个数之间的汉明距离。 网上还有一种更巧妙的方法，仔细观察下面三个数的二进制表示，我们可以位的角度计算所有汉明距离，而不是每次针对两个完整的数。比如最低位，三个数都是0，则任意两个数之间不会贡献汉明距离；次低位有一个为0，两个为1，要产生汉明距离，必须一个为0，一个为1，也就是(4,14)和(4,2)才能产生次低位的汉明距离，而(14,2)因为都是1没有汉明距离。所以我们可以统计每一位中0和1的个数zero[i]和one[i]，在第i位上所有数的两两汉明距离之和为zero[i]*one[i]。所以总的汉明距离就是ans=Σ zero[i]*one[i]。

• 4:  0100
• 14:1110
• 2:  0010

完整代码如下： [cpp] class Solution { public: int totalHammingDistance(vector<int>& nums) { int bit_len = sizeof(int) * 8; vector<int> one(bit_len, 0), zero(bit_len, 0); for (int i = 0; i < bit_len; ++i) { for (int j = 0; j < nums.size(); ++j) { if (nums[j] & 1)++one[i]; else ++zero[i]; nums[j] >>= 1; } } int ans = 0; for (int i = 0; i < bit_len; ++i) { ans += one[i] * zero[i]; } return ans; } }; [/cpp] 本代码提交AC，用时112MS。]]>