Day36汉明距离总和

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
给你一个整数数组 nums，请你计算并返回 nums 中任意两个数之间 汉明距离的总和 。

按照之前求海明码的做法做，暴力解超时。

class Solution {
    public int totalHammingDistance(int[] nums) {
        int distance = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int a = nums[i];
                int b = nums[j];
                while (Math.max(a, b) != 0) {
                    if ((a & 1) != (b & 1)) {
                        distance++;
                    }
                    a = a >> 1;
                    b = b >> 1;
                }
            }
        }
        return distance;
    }
}

class Solution {
    public int totalHammingDistance(int[] nums) {
        int ans = 0, n = nums.length;  // 初始化答案为0，n为数组长度
        for (int i = 0; i < 30; ++i) {  // 对于每一位（假设数字不超过30位二进制数）
            int c = 0;  // 统计当前二进制位为1的数字个数
            for (int val : nums) {  // 遍历所有数字
                c += (val >> i) & 1;  // 将每个数字右移i位，检查第i位是否为1
            }
            ans += c * (n - c);  // 对于当前位，计算汉明距离的贡献：有c个数字在该位是1，剩下(n - c)个是0
        }
        return ans;  // 返回总的汉明距离
    }
}

时间复杂度：O(nL)，空间复杂度：O(1)。