LeetCode 762 题解（Go）：统计二进制表示中置位数为质数的整数个数

LeetCode 762 题解Go统计二进制表示中置位数为质数的整数个数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇基于 LeetCode-Go 仓库中 762. Prime Number of Set Bits in Binary Representation 的题解文档 展开结合仓库内完整的 Go 源码与测试用例拆解统计区间内二进制置位数为质数的整数个数这一经典位运算 数论组合题。读完本文你将掌握bits.OnesCount统计二进制 1 个数的用法、利用数据范围上界枚举质数的优化思路以及如何在 LeetCode-Go 仓库中运行该题的测试用例验证结果。题目描述给定两个整数L和R统计闭区间[L, R]范围内二进制表示中置位set bits个数为质数的整数个数。所谓置位个数即整数写成二进制后1的个数。例如21的二进制是10101含有 3 个置位同时约定1 不是质数。示例 1Input: L 6, R 10 Output: 4 Explanation: 6 - 110 (2 set bits, 2 is prime) 7 - 111 (3 set bits, 3 is prime) 9 - 1001 (2 set bits , 2 is prime) 10 - 1010 (2 set bits , 2 is prime)区间[6, 10]内6、7、9、10四个数的置位个数分别为 2、3、2、2均为质数因此结果为 4。注意8的二进制为1000置位数为 1而 1 不是质数故不计入。示例 2Input: L 10, R 15 Output: 5 Explanation: 10 - 1010 (2 set bits, 2 is prime) 11 - 1011 (3 set bits, 3 is prime) 12 - 1100 (2 set bits, 2 is prime) 13 - 1101 (3 set bits, 3 is prime) 14 - 1110 (3 set bits, 3 is prime) 15 - 1111 (4 set bits, 4 is not prime)区间[10, 15]内前 5 个数的置位个数为 2 或 3均为质数只有15的置位个数为 4非质数所以结果为 5。数据约束L, R满足L R且均在[1, 10^6]范围内R - L最大为 10000。解题思路这一题是一个典型的位运算 数学组合题整体思路分两步统计每个整数的二进制置位个数——判断一个数二进制有多少位 1正是 LeetCode 191. Number of 1 Bits 的核心问题判断置位个数是否为质数——利用题目给定的区间上限将质数集合有限枚举出来避免每次做通用质数判定。关键洞察区间上限决定质数枚举范围题目限定L, R最大不超过10^6。由于2^19 524288 10^6 2^20 1048576区间内任意整数的二进制表示最多只有19 位因此置位个数最大也就是 19。这意味着质数只需要在[1, 19]内枚举即可2, 3, 5, 7, 11, 13, 17, 19由于 1 不是质数最小的质数是 2。这样就把判断任意整数是否为质数这一通用问题退化成了8 个固定值的常量比较判断成本为 O(1)。Go 实现与源码解析仓库中的完整实现位于 762. Prime Number of Set Bits in Binary Representation.gopackage leetcode import math/bits func countPrimeSetBits(L int, R int) int { counter : 0 for i : L; i R; i { if isPrime(bits.OnesCount(uint(i))) { counter } } return counter } func isPrime(x int) bool { return x 2 || x 3 || x 5 || x 7 || x 11 || x 13 || x 17 || x 19 }主函数countPrimeSetBits主函数用一个简单的for循环遍历闭区间[L, R]i R保证右端点包含在内对每个数执行两步判断bits.OnesCount(uint(i))调用 Go 标准库math/bits包以一条 CPU 指令级别的内置函数返回i的二进制中 1 的个数即 popcountisPrime(...)判断该置位个数是否落在枚举出的质数集合中。只有两步都为真时counter加一。整体逻辑与 README 文档 中最后按照题目的意思累积结果的描述完全一致。isPrime的枚举式判断由于置位个数被限制在[0, 19]之间isPrime直接对 8 个质数做等值比较没有引入任何循环、取模或开方运算置位个数是否为质数说明0否0 不是质数也不会有正整数的二进制全为 01否题目明确约定 1 不是质数2, 3, 5, 7, 11, 13, 17, 19是均落在枚举集合内4, 6, 8, 9, 10, 12, 14, 15, 16, 18否合数或非质数这种写法的好处是单次判断固定为常数次比较且代码可读性极高判定结果一眼可查。复杂度分析时间复杂度O(R - L 1)。对区间内每个整数各执行一次 O(1) 的 popcount 与 O(1) 的质数比较整体与区间长度线性相关。由于R - L最大为 10000最坏也只需约一万次循环。空间复杂度O(1)。除计数器外不申请任何与输入规模相关的额外空间。在仓库的 位运算分类表 中本题被归类为Bit Manipulation位运算类目难度 Easy标注复杂度即为O(n)时间、O(1)空间与上述分析吻合。测试与验证仓库为本题提供了完整的单元测试文件 762. Prime Number of Set Bits in Binary Representation_test.go采用 LeetCode-Go 仓库统一的question/para/ans表驱动测试结构func Test_Problem762(t *testing.T) { qs : []question762{ { para762{6, 10}, ans762{4}, }, { para762{10, 15}, ans762{5}, }, } ... }两个用例与题目给出的示例完全对应countPrimeSetBits(6, 10) 4、countPrimeSetBits(10, 15) 5。在仓库根目录执行以下命令即可验证go test ./leetcode/0762.Prime-Number-of-Set-Bits-in-Binary-Representation/... -v测试同时会打印【input】与【output】的对照输出便于直观核对结果。关联题目191. Number of 1 Bits 的两种置位统计方式README 文档明确指出判断一个数的二进制位有多少位 1是第 191 题。仓库中 191. Number of 1 Bits.go 给出了两种经典实现// 解法一 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 }两种方式对比解法一库函数bits.OnesCount直接调用硬件支持的 popcount 指令实现最简洁这也是 762 题官方实现采用的方案解法二布莱恩·克尼根算法利用num (num - 1)每轮清除最低位的 1循环次数等于 1 的个数本身不依赖标准库是面试中常被要求手写的经典位运算技巧。对 762 题而言若题目环境不允许使用math/bits将bits.OnesCount(uint(i))替换为上述解法二的内联写法即可获得等价的正确结果。延伸与变体变体一通用质数判断不依赖区间上界如果题目去掉10^6的上限置位个数可能超出枚举集合此时可以把isPrime换成通用质数判定试除法遍历到sqrt(x)func isPrime(x int) bool { if x 2 { return false } for d : 2; d*d x; d { if x%d 0 { return false } } return true }由于 64 位整数的置位个数最多为 64通用判断的试除范围也非常有限性能影响可忽略。变体二多次查询加速如果需要对多个[L, R]区间重复查询可以预先计算1到10^6每个数的置位个数是否为质数再做前缀和。这样单次区间查询可降到 O(1)属于空间换时间的经典优化方向。小结LeetCode 762 是一道难度 Easy 的位运算组合题解题的关键在于两点一是熟练掌握 popcount 统计二进制 1 的个数可参考 191. Number of 1 Bits二是敏锐地利用10^6这一数据边界将质数判断收敛为 8 个固定值的常量枚举从而得到 O(R - L 1) 时间、O(1) 空间的简洁实现。仓库中的 题解文档、实现源码 与 测试用例 三者互相印证可作为同类二进制 质数题目的直接参考模板。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考