所有数对的汉明距离总和如何优化？（LeetCode 477）

简化版

所有数对的汉明距离不能暴力枚举数对再异或，应该按位统计。对每一位，假设数组中有 c 个数该位为 1，有 n-c 个数该位为 0，那么这一位对总答案贡献 c * (n-c)，因为只有 0 和 1 配对时才产生 1 个距离。遍历 32 位累加即可，时间 O(32n)，空间 O(1)。

详细版

int totalHammingDistance(int[] nums) {
    int ans = 0;
    int n = nums.length;
    for (int bit = 0; bit < 32; bit++) {
        int ones = 0;
        for (int x : nums) {
            ones += (x >>> bit) & 1;
        }
        ans += ones * (n - ones);
    }
    return ans;
}

单个数对的汉明距离是逐位不同数量。
所有数对求和可以交换求和顺序：先看每一位贡献多少，再累加所有位。
某一位上，1 的数量为 ones，0 的数量为 n-ones，不同配对数量就是 ones*(n-ones)。
固定 32 位下复杂度 O(n)，更严谨写作 O(32n)，额外空间 O(1)。

完整版教学

一、暴力为什么会超时

如果数组长度为 n，暴力做法会枚举每一对 (i,j)，计算 nums[i] ^ nums[j] 后统计 1 的个数。数对数量是 n*(n-1)/2，当 n=10000 时约为 49995000 对，再乘上每次最多 32 位统计，成本很高。

这类题的优化方向通常是“不要按数对看，改按位看”。汉明距离本来就是每一位是否不同的总和，所以可以把二维的数对枚举拆成 32 个独立的位贡献。

二、交换求和顺序是核心

单个数对 (a,b) 的汉明距离可以写成：

dist(a,b) = 第0位是否不同 + 第1位是否不同 + ... + 第31位是否不同

所有数对的总和就是：

sum over pairs dist(a,b)
= sum over bit positions (该位在所有数对中不同的次数)

这个转换把问题从“多少对数字”变成“每一位有多少个 0 和 1”。只要某一位一个数是 0、另一个数是 1，这一对就在该位贡献 1。

三、为什么贡献是 c*(n-c)

假设某一位上有 c 个数为 1，那么剩下 n-c 个数为 0。能形成不同位的配对必须从 1 组拿一个、从 0 组拿一个，所以数量是 c*(n-c)。

以 nums=[4,14,2] 为例：

4  = 0100
14 = 1110
2  = 0010

bit	这一位的值	ones	zeros	贡献
0	0,0,0	0	3	0
1	0,1,1	2	1	2
2	1,1,0	2	1	2
3	0,1,0	1	2	2

总贡献是 0+2+2+2=6。暴力数对也会得到 (4,14)=2、(4,2)=2、(14,2)=2，总和 6。

记忆钩子：总汉明距离别先配人，先按座位看；每一位上 1 组和 0 组两两握手，握手次数就是贡献。

四、代码里为什么用无符号右移

Java 中 >>> 是无符号右移，>> 是算术右移。原题通常给非负整数，二者在高位补符号的问题上不容易触发错误；但写成 >>> 更能表达“我在看固定 32 位模式，而不是做有符号数除以 2”。

核心取位公式是：

int bitValue = (x >>> bit) & 1;

它表示把第 bit 位移到最低位，再用 & 1 取出。这个公式也能复用到位掩码、状态压缩和权限标记类问题里。

五、复杂度为什么可以说是线性

外层循环固定 32 次，内层扫描 n 个数，因此是 O(32n)。在固定宽度整数模型下，32 是常数，所以也可以说 O(n)。空间上只维护 ans、ones、循环变量，额外空间 O(1)。

如果题目扩展到 64 位整数，外层改成 64；如果语言使用任意精度整数，还要根据最大值位长决定扫描范围。面试时说明“本题按 32 位非负整数处理”即可。

六、和两两异或的结果为什么一致

按位统计不是近似，它和暴力完全等价。暴力对每个数对统计该数对的不同位；按位统计则对每个位统计有多少数对在该位不同。它们只是遍历顺序不同。

暴力顺序：pair1 的所有位 + pair2 的所有位 + ...
按位顺序：bit0 的所有 pair + bit1 的所有 pair + ...

因为加法满足交换律，所有“某对某位是否不同”的小贡献最终都会被加一次，不会漏也不会重。这个解释比只背 c*(n-c) 更有说服力。

七、常见误区与追问

误区：先求所有数字的异或再数 1。 总汉明距离不是所有数字整体异或的汉明重量，数对贡献不能这样合并。
误区：每一位贡献写成 c*(c-1)/2。 那是 1 与 1 的配对数，而汉明距离需要 1 与 0 配对。
误区：忘记扫描足够位数。 对 32 位整数通常扫描 0 到 31；只扫描到当前最大值位长也可以，但要先求最大值。
追问：为什么没有除以 2？ c*(n-c) 已经是在无序数对里从 1 组和 0 组各选一个，不存在重复计数。
追问：如果数组里有重复数字怎么办？ 没问题，重复值作为不同下标的元素参与配对，按位计数天然包含它们。
追问：能不能用内置 bitCount？ 暴力加 bitCount 仍是 O(n^2)，按位统计才是关键优化。

八、加强记忆

总汉明距离 = 每一位独立贡献之和。某一位有 c 个 1 和 n-c 个 0，这一位贡献 c*(n-c)；遍历 32 位累加即可。它的本质是交换求和顺序：从“逐数对看所有位”换成“逐位看所有数对”，因此把 O(n^2*32) 降到 O(32n)。

简化版

详细版