题目分析

这个题目是第461题的扩展，在第461题中，只需要计算两个数之间的汉明距离，这个题目是计算任意两个数之间的汉明距离之和。很简单的思路是遍历两层循环，可是数组长度最大为10000，如果两层循环会超时，会不会有更好的方法呢？

位运算

因为这里元素范围是1e9，因此肯定在int范围之内，而且我们发现汉明距离是衡量每一位之间的差异，汉明距离等于所有数字每一位之间的差异，因此可以按照位来衡量，以第k位为例，如果第k位为1的数字有m个，总数有n个，则第k位为0的数字有n - m个，所以第k位的汉明距离为n x (n - m)，最终的结果只需要遍历32位即可。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(1)$**。
下面是Java语言的题解

class Solution {
    public int totalHammingDistance(int[] nums) {
        int cur_num = 1, length = nums.length, res = 0;
        for (int i = 0; i < 32; i++) {
            int cur = 0;
            for (int x : nums) {
                cur += (cur_num & x) > 0 ? 1 : 0;
            }
            res += cur * (length - cur);
            cur_num <<= 1;
        }
        return res;
    }
}

下面是Python语言的题解

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        length, cur, res = len(nums), 1, 0
        for i in range(32):
            cur_num = 0
            for x in nums:
                cur_num += (x & cur) > 0
            res += cur_num * (length - cur_num)
            cur <<= 1
        return res

对比两种语言，可以发现Python语言中的布尔类型可以直接参与运算，即true为1，false为0。但是Java中的boolean不能直接和int进行运算，只能通过三目运算符进行操作。

刷题总结

这个题目不难，能否想到按位计算是关键步骤。