Total Hamming Distance–LeetCode#477

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.

计算一个整型数组中的Hamming distance之和

/**
 * @Author: Poldi
 * @Date: 2018/3/30 下午3:17
 * @Description:
 */
public class TotalHammingDistance {
    public int totalHammingDistance(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] != nums[j]){
                    res += HammingDistance(nums[i], nums[j]);
                }
            }
        }
        return res;
    }
    int HammingDistance(int a, int b) {
        int xor = a ^ b;
        int count = 0;
        while (xor > 0) {
            count += xor & 1;
            xor = xor >> 1;
        }
        return count;
    }
    public static void main(String[] args) {
        TotalHammingDistance totalHammingDistance = new TotalHammingDistance();
        int[] nums = {4, 14, 4};
        System.out.println(totalHammingDistance.totalHammingDistance(nums));
    }
}

用了最最最无脑的思路，两次循环计算每组数字之间的Hamming distance求和，超时…时间复杂度为O(n²)
借鉴大神的思路，计算所有数字同一个bit位上1出现的次数count，这一位上的Hamming distance为 count * (nums.length – count)，然后计算所有bit位上的1数量求和。

/**
 * @Author: Poldi
 * @Date: 2018/3/30 下午3:17
 * @Description:
 */
public class TotalHammingDistance {
    private int totalHammingDistance(int[] nums) {
        int total = 0, n = nums.length;
        for (int j=0;j<32;j++) {
            int bitCount = 0;
            for (int i=0;i<n;i++)
                bitCount += (nums[i] >> j) & 1;
            total += bitCount*(n - bitCount);
        }
        return total;
    }
    public static void main(String[] args) {
        TotalHammingDistance totalHammingDistance = new TotalHammingDistance();
        int[] nums = {4, 14, 4};
        System.out.println(totalHammingDistance.totalHammingDistance(nums));
    }
}