LeetCode 477 题解：用 Go 按位统计 Total Hamming Distance，O(n) 一行公式算完所有数对-编程实验室

LeetCode 477 题解：用 Go 按位统计 Total Hamming Distance，O(n) 一行公式算完所有数对

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

LeetCode 477（Total Hamming Distance）要求计算一个数组中所有数对汉明距离的总和。本文以 LeetCode-Go 仓库中该题的官方 Go 实现为主线，讲解"按位拆分 + 组合计数"的 O(32n) 解法，推导出k * (n - k)的核心公式，并对照仓库中注释为"暴力解法超时！"的 O(n²) 写法，分析为什么必须绕开两两枚举。读完本文，你将掌握汉明距离类题目的通用思考路径，并能直接复用仓库内的可运行源码与测试用例。

题目描述

两个整数之间的汉明距离定义为：这两个数字的二进制表示中，对应位不同的位置数量。

本题的任务是：给定一个整数数组，计算其中任意两个数之间汉明距离的总和。

题目原文见 leetcode/0477.Total-Hamming-Distance/README.md。

示例

Input: 4, 14, 2 Output: 6

计算过程如下（只展示相关的四位二进制）：

4 的二进制：0100
14 的二进制：1110
2 的二进制：0010

两两之间的汉明距离：

HammingDistance(4, 14) = 2 HammingDistance(4, 2) = 2 HammingDistance(14, 2) = 2

总和：2 + 2 + 2 = 6。

约束条件

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

10^9 < 2^30，再加上符号位，用 32 位二进制即可完整表示所有元素，这正是下文算法按 32 位扫描的依据。

前置知识：单对数字的汉明距离

在进入本题前，先回顾单对数字的汉明距离。仓库中 0461.Hamming-Distance 一题给出了最直接的思路：对x与y做异或，异或结果的二进制中，为1的位就是两数对应位不同的位置，因此数出异或结果里1的个数即可。

LeetCode-Go 仓库在本题的源码中同样保留了这一工具函数，用于暴力解法，见 477. Total Hamming Distance.go：

func hammingDistance(x int, y int) int { distance := 0 for xor := x ^ y; xor != 0; xor &= (xor - 1) { distance++ } return distance }

这里用到经典的位操作技巧xor &= (xor - 1)：每执行一次，就把xor最低位的1清零（该技巧与 Bit Manipulation 专题中总结的X &= (X - 1) 将最低位(LSB)的 1 清零完全对应），所以循环次数就是1的个数，即两数的汉明距离。

核心思路：按位统计，而不是按数对统计

如果直接套用上面的单对函数去枚举所有数对，复杂度是 O(n²)，在n = 10^4时约需要计算10^8次数对，必然超时。仓库源码中的暴力写法totalHammingDistance1就注释着"暴力解法超时！"。

正确的思路是把"数对维度"的统计，拆解为"位维度"的统计，这正是原 README 解题思路的核心：

把数组中的每个元素 32 位的二进制位依次扫一遍，当扫到某一位的时候，有k个元素在这个位上的值是 1，n - k个元素在这个位上的值是 0，那么在这一位上所有两两元素的海明距离是k * (n - k)。当把 32 位全部扫完以后，累加出来的海明距离就是所有两两元素的海明距离。

为什么某一位的贡献是 k × (n − k)

这一结论的推导非常直观：

两个数在某一位上的汉明距离贡献为 1，当且仅当这两个数在这一位上一个是1、另一个是0；
假设这一位上值为1的元素有k个，值为0的元素有n - k个；
那么"一个取 1、一个取 0"的数对数量正好是k × (n - k)；
因此这一位对总和的贡献就是k × (n - k)。

由于每一位的贡献只取决于该位上1的个数k，与具体是哪些数对无关，不同位之间的贡献又可以独立累加，最终答案就是 32 位贡献之和。整个过程只需扫描32 × n次，时间复杂度 O(32n) ≈ O(n)。

Go 源码实现解读

仓库给出的最优解实现非常精简，完整代码如下（477. Total Hamming Distance.go）：

func totalHammingDistance(nums []int) int { total, n := 0, len(nums) for i := 0; i < 32; i++ { bitCount := 0 for j := 0; j < n; j++ { bitCount += (nums[j] >> uint(i)) & 1 } total += bitCount * (n - bitCount) } return total }

逐行拆解：

total, n := 0, len(nums)：total累加每一位的贡献；n为数组长度，用于计算n - bitCount。
外层for i := 0; i < 32; i++：遍历 32 个二进制位。取 32 位是因为元素最大值10^9 < 2^30，32 位足够覆盖（含符号位），多出的高位全为 0，bitCount恒为 0，不影响结果。
内层for j := 0; j < n; j++：统计第i位上值为1的元素个数。
- nums[j] >> uint(i)：把第i位移到最低位；
- & 1：取出该位，得到 0 或 1；
- bitCount += ...：累加得到k。
total += bitCount * (n - bitCount)：套用公式，累加该位对总汉明距离的贡献。

值得注意的细节：源码中对外层位索引i做了uint(i)转换，这是因为 Go 语言中移位操作的右操作数要求是无符号整数（或能被隐式转换为无符号整数），这也是 Go 位运算题目中常见的写法。

复杂度分析

时间复杂度：O(32n) = O(n)，只需扫描 32 次数组，与数对数量无关；
空间复杂度：O(1)，仅使用total、bitCount等常数个变量，不依赖输入规模。

对比暴力解法 O(n²) 的时间复杂度，当n = 10^4时两者相差约 3 个数量级，这就是本题必须按位统计的根本原因。

暴力解法对照：为什么它超时

仓库源码中保留了暴力解作为对照，明确标注"暴力解法超时！"：

// 暴力解法超时！ func totalHammingDistance1(nums []int) int { res := 0 for i := 0; i < len(nums); i++ { for j := i + 1; j < len(nums); j++ { res += hammingDistance(nums[i], nums[j]) } } return res }

它枚举所有下标对(i, j)（i < j），对每对数调用hammingDistance逐位统计差异，总复杂度为：

C(n, 2) × 位数 ≈ n² / 2 × 32

当n = 10^4时约为1.6 × 10^9次位操作，在 LeetCode 的时间限制下必然超时。这两版代码同处一个文件中，恰好构成"错误思路 vs 正确思路"的直观对比：暴力版逻辑正确但不可行，按位统计版才是本题的标准解。

测试用例与运行验证

仓库为该题提供了完整的单元测试，见 477. Total Hamming Distance_test.go。测试框架沿用 LeetCode-Go 仓库统一的"参数 + 期望答案"结构：

type para477 struct { one []int } type ans477 struct { one int }

测试主体Test_Problem477使用的用例与题目示例一致：

qs := []question477{ { para477{[]int{4, 14, 2}}, ans477{6}, }, }

即输入[4, 14, 2]，期望输出6。测试同时调用totalHammingDistance与totalHammingDistance1两个版本，既验证了最优解的正确性，也验证了暴力解在逻辑上无误（只是性能不达标）。

运行测试的命令如下（仓库根目录执行）：

go test ./leetcode/0477.Total-Hamming-Distance/...

LeetCode-Go 仓库对全部题解执行统一测试并生成覆盖率文件，相关脚本见 gotest.sh（使用-covermode=atomic与-coverprofile=coverage.txt一次性覆盖./leetcode/...全部包）。

解题要点小结

变换统计维度：把"数对之间逐位比较"转换为"每一位上统计 1 的个数"，是本题破题的关键；
组合计数公式：某一位上k个 1、n - k个 0 时，该位贡献k × (n - k)；
扫描范围：元素最大10^9 < 2^30，因此扫描 32 位即可覆盖全部有效位；
Go 移位细节：移位操作数需为无符号类型，源码中用uint(i)完成转换；
复杂度优势：O(32n) 时间、O(1) 空间，轻松应对n = 10^4的输入规模。

LeetCode 477 题解：用 Go 按位统计 Total Hamming Distance，O(n) 一行公式算完所有数对