leetcode477-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.

计算 N 个数字之间的汉明码距离之和。
汉明码是指两个数字的二进制表示形式中，在对应位置上值不同的数量总和。如 2 和 4，4 的二进制表达式为100，2 的二进制表达式010，则二者在第二位和第三位的值不同，因此汉明码值为 2。

思路和代码

如果直观的采用两两比较来得出任意两个数字之间的汉明码值，再将汉明码值的和进行累加，得出最终的汉明码值总和，则需要 O(n^2)的时间复杂度。除此以外，还要乘上数字二进制的平均长度。

那么有没有方法能够尽可能的减少重复比较的场景。既然水平的以两个数字直接开始比较会超时，不如垂直的进行比较，即每次都比较同一位置上的所有二进制数值，假设一共有 n 个数字，其中有 m 个数字在第 i 上值为 1，则剩下的 n - m 个数字在第 i 上的值为 0。由此可知，在第 i 为上存在的 (m-n)*n 个数值不同的情况。对 32 位整数重复执行这个过程并累加即可得出最终的汉明码和。

代码如下：

    public int totalHammingDistance(int[] nums) {
         int count = 0;
         int length = nums.length;
         for(int i = 0 ; i<32 ; i++) {
               int countOfOne = 0;
               for(int j = 0 ; j < length ; j++) {countOfOne += (nums[j] >> i) & 1;
               }
               count += countOfOne * (length - countOfOne);
         } 
         return count;
     }