汉明距离总和

题目

计算一个数组中，任意两个数之间汉明距离的总和。

思路

汉明距离等于两个数二进制表示中对应位置不同的数量。假设数组中的每个数都表示为 k 位的二进制数（高位补 0），那么我们可以发现，要计算数组中任意两个数的汉明距离的总和，可以先算出数组中任意两个数二进制第 i 位的汉明距离的总和，再将所有的 k 位之和相加。也就是说，二进制中的每一位都是可以独立计算的。

代码

    // 2020-09-07 10:12:43
    public int totalHammingDistance(int[] nums) {
        if (nums.length == 0) return 0;
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int zero = 0, one = 0;
            for (int num : nums) {
                if ((num & 1 << i) == (1 << i)) one++;
                else zero++;
            }
            ans += zero * one;
        }
        return ans;
    }