 一行公式算完所有数对)
LeetCode 477 题解用 Go 按位统计 Total Hamming DistanceO(n) 一行公式算完所有数对【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-GoLeetCode 477Total 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 的二进制010014 的二进制11102 的二进制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.gofunc 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个元素在这个位上的值是 1n - 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.gofunc 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^3032 位足够覆盖含符号位多出的高位全为 0bitCount恒为 0不影响结果。内层for j : 0; j n; j统计第i位上值为1的元素个数。nums[j] uint(i)把第i位移到最低位 1取出该位得到 0 或 1bitCount ...累加得到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使用-covermodeatomic与-coverprofilecoverage.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的输入规模。延伸阅读汉明距离的基础版本单对数对461. Hamming Distance 题解掌握X (X - 1)与异或计数技巧仓库的 Bit Manipulation 位运算专题 系统性总结了异或特性、特殊 Mask 构造以及各类经典位操作本题使用的(x n) 1取位技巧即出自该专题仓库根 README.md 中 Bit Manipulation 分类已全部完成✅可按编号检索更多位运算题目进行配套练习。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 477 题解：用 Go 按位统计 Total Hamming Distance，O(n) 一行公式算完所有数对
LeetCode 477 题解用 Go 按位统计 Total Hamming DistanceO(n) 一行公式算完所有数对【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-GoLeetCode 477Total 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 的二进制010014 的二进制11102 的二进制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.gofunc 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个元素在这个位上的值是 1n - 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.gofunc 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^3032 位足够覆盖含符号位多出的高位全为 0bitCount恒为 0不影响结果。内层for j : 0; j n; j统计第i位上值为1的元素个数。nums[j] uint(i)把第i位移到最低位 1取出该位得到 0 或 1bitCount ...累加得到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使用-covermodeatomic与-coverprofilecoverage.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的输入规模。延伸阅读汉明距离的基础版本单对数对461. Hamming Distance 题解掌握X (X - 1)与异或计数技巧仓库的 Bit Manipulation 位运算专题 系统性总结了异或特性、特殊 Mask 构造以及各类经典位操作本题使用的(x n) 1取位技巧即出自该专题仓库根 README.md 中 Bit Manipulation 分类已全部完成✅可按编号检索更多位运算题目进行配套练习。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考