题目描述

两个整数的 Hamming 距离 指的是这两个数字的二进制数对应位不同的数量。

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

样例

输入：4, 14, 2

输出：6

解释：在二进制表示中，4 表示为 0100，14 表示为 1110，2 表示为 0010。
这样表示是为了体现后四位之间关系。

所以答案为：
HammingDistance(4, 14) 
    + HammingDistance(4, 2)
    + HammingDistance(14, 2)
    = 2 + 2 + 2 = 6。

说明

• 数组中元素的范围为从 0 到 10^9。
• 数组的长度不超过 10^4。

算法

(按位统计) $O(31n)$

1. 将所有数对距离的计算过程按位分离，固定第 $i$ 个二进制位，统计数组中数字 $i$ 位为 1 的个数 $ones$，则第 $i$ 位贡献的答案为 $ones * (n - ones)$。

时间复杂度

• 枚举 31 个数位，每次枚举会遍历整个数组，故时间复杂度为 $O(31n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {

        int n = nums.size();
        int ans = 0;

        for (int i = 0; i < 31; i++) {
            int ones = 0;

            for (int &x : nums) {
                if (x & 1)
                    ones++;
                x >>= 1;
            }
            ans += ones * (n - ones);
        }

        return ans;
    }
};