尧图网站建设 
LeetCode-Go 题解 191Number of 1 Bits汉明重量——位运算与 bits.OnesCount 双解法剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文是 LeetCode-Go 开源仓库对 LeetCode 第 191 题「Number of 1 Bits」的完整题解指南。题目要求统计一个 32 位无符号整数的二进制表示中1的个数即汉明重量Hamming Weight。读完本文你将掌握两种 Go 实现方案直接调用标准库math/bits.OnesCount的一行解法以及利用X X (X-1)位运算逐次清除最低位 1 的手写解法并能在仓库中定位到对应源码、测试用例与运行方式。题目原文编写一个函数输入是一个无符号整数返回其二进制表达式中数字位数为1的个数该数值也被称为汉明重量Hamming weight。示例 1Input: 00000000000000000000000000001011 Output: 3 Explanation: 输入二进制串 00000000000000000000000000001011 中共有 3 个 1 位。示例 2Input: 00000000000000000000000010000000 Output: 1 Explanation: 输入二进制串 00000000000000000000000010000000 中只有 1 个 1 位。示例 3Input: 11111111111111111111111111111101 Output: 31 Explanation: 输入二进制串 11111111111111111111111111111101 中共有 31 个 1 位。注意事项在 Java 等语言中不存在无符号整数类型。此时输入会以有符号整数类型给出但这不应影响实现因为整数的内部二进制表示在有符号与无符号两种解读下是完全一致的。在 Java 中编译器使用补码2s complement表示有符号整数。因此上述示例 3的输入在有符号解读下表示整数-3。题目大意求uint32数的二进制位中1的个数。这个统计结果在信息论与编码理论中称为汉明重量其数学本质是向量中非零分量的个数在密码学、纠错码、布隆过滤器位图统计等场景中都有直接应用。解题思路本题的解法完全建立在二进制位操作之上核心有两条路线手写位运算解法二利用公式X X (X - 1)。该操作的效果是清除当前数二进制表示中最低位的那个1。循环执行该操作直到数值被清零为止操作执行的次数就是二进制位中1的个数。例如对0b1011执行一次0b1011 0b1010 0b1010再执行一次0b1010 0b1001 0b1000再执行一次0b1000 0b0111 0共 3 次与示例 1 的输出一致。调用标准库解法一直接调用 Go 标准库函数bits.OnesCount(uint(num))一行即可完成统计。math/bits包在底层会映射到 CPU 提供的 POPCNT 类指令在支持的架构上时间开销为常数级是工程实践中最推荐的方式。两种解法的源码实现仓库中 leetcode/0191.Number-of-1-Bits/191. Number of 1 Bits.go 完整给出了两个版本package leetcode import math/bits // 解法一 func hammingWeight(num uint32) int { return bits.OnesCount(uint(num)) } // 解法二 func hammingWeight1(num uint32) int { count : 0 for num ! 0 { num num (num - 1) count } return count }对应英文站题解文档 website/content.en/ChapterFour/0100~0199/0191.Number-of-1-Bits.md 与中文版 leetcode/0191.Number-of-1-Bits/README.md 中的代码完全一致可直接对照阅读。为什么X (X-1)能清除最低位的 1对任意正整数XX - 1的二进制变化规律是X的最低非零位即最低位的那个1变成0而其右侧所有更低位的0全部变成1更高位保持不变。两者做按位与后最低位的1所在位置X中是1X-1中是0与运算结果为0该位被清除更低位的所有位置X中是0X-1中是1与运算结果仍为0更高位两者完全相同与运算后保持不变。因此每执行一次X X (X-1)二进制表示中恰好减少一个1。循环到X为0时循环次数即等于1的个数。复杂度分析方案时间复杂度空间复杂度bits.OnesCount解法一O(1)底层为常数级硬件指令O(1)X (X-1)循环解法二O(k)k 为二进制中1的个数最坏 O(32)O(1)解法二的最坏情况出现在输入为0xFFFFFFFF时示例 3 中 31 个1此时需要循环 31 次但平均而言它只迭代「1 的个数」次优于逐位移位检测的固定 32 次迭代方案。测试用例与运行验证仓库为该题配套了完整的测试文件 leetcode/0191.Number-of-1-Bits/191. Number of 1 Bits_test.go。测试通过表驱动table-driven风格组织用例qs : []question191{ { para191{5}, ans191{1}, }, { para191{13}, ans191{2}, }, }输入5二进制101期望输出1输入13二进制1101期望输出2。测试中还将输入格式化打印为固定 32 位的二进制字符串以便人工核对input : strconv.FormatUint(uint64(p.one), 2) // 32位无符号整数转换为二进制字符串 input fmt.Sprintf(%0*v, 32, input) // 格式化输出32位,保留前置0 fmt.Printf(【input】:%v 【output】:%v\n, input, hammingWeight(p.one)) hammingWeight1(p.one)strconv.FormatUint将uint32转为二进制字符串fmt.Sprintf(%0*v, 32, input)则用0补足 32 位宽度直观展示前导零。hammingWeight与hammingWeight1在同一用例下被同时调用测试两者的输出一致性。运行单个题目的测试命令go test -v ./leetcode/0191.Number-of-1-Bits/若要验证仓库整体覆盖率仓库通过 gotest.sh 以-covermodeatomic模式对全部 leetcode 包统一收集覆盖率并生成 coverage.txt可执行./gotest.sh # 等价于: go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...边界情况与语言差异由于本仓库以 Go 实现见 go.modmodule 为github.com/halfrost/LeetCode-GoGo 版本 1.19uint32天然是无符号类型不存在 Java 中的有符号问题但在其他语言中需要特别注意Java / C 的有符号解读补码表示下0xFFFFFFFD被解读为-3但其二进制位模式与无符号解读完全一致因此按位统计1的结果不受符号类型影响实现无需为符号做特殊处理。Go 类型转换bits.OnesCount接受uint平台相关位宽64 位平台上为 64 位因此源码中先执行uint(num)再传入。由于num的高 32 位为 0统计结果与直接统计 32 位的结果一致。输入为 0 的情况num 0时循环不执行解法二直接返回0bits.OnesCount(0)同样返回0两种实现行为一致。延伸思考掌握汉明重量的统计方法后可以顺带攻克仓库中的一系列位运算问题190. Reverse Bits反转一个 32 位无符号整数的二进制位同样基于位运算与uint32类型338. Counting Bits计算0到n每个数字的二进制1个数可利用bits.OnesCount或动态规划递推461. Hamming Distance两个整数对应二进制位不同的个数即XOR结果的汉明重量可直接复用bits.OnesCount(x ^ y)477. Total Hamming Distance数组中所有数对汉明距离之和属于按位贡献的统计问题。这些题目与本题共用同一套位运算思维是巩固位操作技巧的最佳实践组合。本仓库 README.md 中对整套 LeetCode 题解目录有系统性的组织说明可按题目编号定位到对应章节继续学习。【免费下载链接】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-Go 题解 191：Number of 1 Bits（汉明重量）——位运算与 bits.OnesCount 双解法剖析
LeetCode-Go 题解 191Number of 1 Bits汉明重量——位运算与 bits.OnesCount 双解法剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文是 LeetCode-Go 开源仓库对 LeetCode 第 191 题「Number of 1 Bits」的完整题解指南。题目要求统计一个 32 位无符号整数的二进制表示中1的个数即汉明重量Hamming Weight。读完本文你将掌握两种 Go 实现方案直接调用标准库math/bits.OnesCount的一行解法以及利用X X (X-1)位运算逐次清除最低位 1 的手写解法并能在仓库中定位到对应源码、测试用例与运行方式。题目原文编写一个函数输入是一个无符号整数返回其二进制表达式中数字位数为1的个数该数值也被称为汉明重量Hamming weight。示例 1Input: 00000000000000000000000000001011 Output: 3 Explanation: 输入二进制串 00000000000000000000000000001011 中共有 3 个 1 位。示例 2Input: 00000000000000000000000010000000 Output: 1 Explanation: 输入二进制串 00000000000000000000000010000000 中只有 1 个 1 位。示例 3Input: 11111111111111111111111111111101 Output: 31 Explanation: 输入二进制串 11111111111111111111111111111101 中共有 31 个 1 位。注意事项在 Java 等语言中不存在无符号整数类型。此时输入会以有符号整数类型给出但这不应影响实现因为整数的内部二进制表示在有符号与无符号两种解读下是完全一致的。在 Java 中编译器使用补码2s complement表示有符号整数。因此上述示例 3的输入在有符号解读下表示整数-3。题目大意求uint32数的二进制位中1的个数。这个统计结果在信息论与编码理论中称为汉明重量其数学本质是向量中非零分量的个数在密码学、纠错码、布隆过滤器位图统计等场景中都有直接应用。解题思路本题的解法完全建立在二进制位操作之上核心有两条路线手写位运算解法二利用公式X X (X - 1)。该操作的效果是清除当前数二进制表示中最低位的那个1。循环执行该操作直到数值被清零为止操作执行的次数就是二进制位中1的个数。例如对0b1011执行一次0b1011 0b1010 0b1010再执行一次0b1010 0b1001 0b1000再执行一次0b1000 0b0111 0共 3 次与示例 1 的输出一致。调用标准库解法一直接调用 Go 标准库函数bits.OnesCount(uint(num))一行即可完成统计。math/bits包在底层会映射到 CPU 提供的 POPCNT 类指令在支持的架构上时间开销为常数级是工程实践中最推荐的方式。两种解法的源码实现仓库中 leetcode/0191.Number-of-1-Bits/191. Number of 1 Bits.go 完整给出了两个版本package leetcode import math/bits // 解法一 func hammingWeight(num uint32) int { return bits.OnesCount(uint(num)) } // 解法二 func hammingWeight1(num uint32) int { count : 0 for num ! 0 { num num (num - 1) count } return count }对应英文站题解文档 website/content.en/ChapterFour/0100~0199/0191.Number-of-1-Bits.md 与中文版 leetcode/0191.Number-of-1-Bits/README.md 中的代码完全一致可直接对照阅读。为什么X (X-1)能清除最低位的 1对任意正整数XX - 1的二进制变化规律是X的最低非零位即最低位的那个1变成0而其右侧所有更低位的0全部变成1更高位保持不变。两者做按位与后最低位的1所在位置X中是1X-1中是0与运算结果为0该位被清除更低位的所有位置X中是0X-1中是1与运算结果仍为0更高位两者完全相同与运算后保持不变。因此每执行一次X X (X-1)二进制表示中恰好减少一个1。循环到X为0时循环次数即等于1的个数。复杂度分析方案时间复杂度空间复杂度bits.OnesCount解法一O(1)底层为常数级硬件指令O(1)X (X-1)循环解法二O(k)k 为二进制中1的个数最坏 O(32)O(1)解法二的最坏情况出现在输入为0xFFFFFFFF时示例 3 中 31 个1此时需要循环 31 次但平均而言它只迭代「1 的个数」次优于逐位移位检测的固定 32 次迭代方案。测试用例与运行验证仓库为该题配套了完整的测试文件 leetcode/0191.Number-of-1-Bits/191. Number of 1 Bits_test.go。测试通过表驱动table-driven风格组织用例qs : []question191{ { para191{5}, ans191{1}, }, { para191{13}, ans191{2}, }, }输入5二进制101期望输出1输入13二进制1101期望输出2。测试中还将输入格式化打印为固定 32 位的二进制字符串以便人工核对input : strconv.FormatUint(uint64(p.one), 2) // 32位无符号整数转换为二进制字符串 input fmt.Sprintf(%0*v, 32, input) // 格式化输出32位,保留前置0 fmt.Printf(【input】:%v 【output】:%v\n, input, hammingWeight(p.one)) hammingWeight1(p.one)strconv.FormatUint将uint32转为二进制字符串fmt.Sprintf(%0*v, 32, input)则用0补足 32 位宽度直观展示前导零。hammingWeight与hammingWeight1在同一用例下被同时调用测试两者的输出一致性。运行单个题目的测试命令go test -v ./leetcode/0191.Number-of-1-Bits/若要验证仓库整体覆盖率仓库通过 gotest.sh 以-covermodeatomic模式对全部 leetcode 包统一收集覆盖率并生成 coverage.txt可执行./gotest.sh # 等价于: go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...边界情况与语言差异由于本仓库以 Go 实现见 go.modmodule 为github.com/halfrost/LeetCode-GoGo 版本 1.19uint32天然是无符号类型不存在 Java 中的有符号问题但在其他语言中需要特别注意Java / C 的有符号解读补码表示下0xFFFFFFFD被解读为-3但其二进制位模式与无符号解读完全一致因此按位统计1的结果不受符号类型影响实现无需为符号做特殊处理。Go 类型转换bits.OnesCount接受uint平台相关位宽64 位平台上为 64 位因此源码中先执行uint(num)再传入。由于num的高 32 位为 0统计结果与直接统计 32 位的结果一致。输入为 0 的情况num 0时循环不执行解法二直接返回0bits.OnesCount(0)同样返回0两种实现行为一致。延伸思考掌握汉明重量的统计方法后可以顺带攻克仓库中的一系列位运算问题190. Reverse Bits反转一个 32 位无符号整数的二进制位同样基于位运算与uint32类型338. Counting Bits计算0到n每个数字的二进制1个数可利用bits.OnesCount或动态规划递推461. Hamming Distance两个整数对应二进制位不同的个数即XOR结果的汉明重量可直接复用bits.OnesCount(x ^ y)477. Total Hamming Distance数组中所有数对汉明距离之和属于按位贡献的统计问题。这些题目与本题共用同一套位运算思维是巩固位操作技巧的最佳实践组合。本仓库 README.md 中对整套 LeetCode 题解目录有系统性的组织说明可按题目编号定位到对应章节继续学习。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考