题目
计算一个数组中,任意两个数之间汉明距离的总和。
思路
汉明距离等于两个数二进制表示中对应位置不同的数量。假设数组中的每个数都表示为 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; }