LeetCode 762. 二进制表示中质数个计算置位详细解析多解法实现在LeetCode题目中“二进制表示中质数个计算置位”是一道融合了二进制操作与质数判断的基础算法题难度为简单但核心在于高效实现“计算置位统计”和“质数校验”尤其适配题目给定的边界条件。本文将从问题拆解、解题思路、代码实现、优化技巧到易错点分析完整覆盖该题的解决流程适合算法入门者巩固基础也可作为面试中的基础算法复习参考。一、题目核心解析1. 题目描述简化版给定两个整数 left 和 right统计闭区间 [left, right] 内二进制表示中1的个数计算置位位数为质数的整数个数。关键定义计算置位位数一个整数的二进制表示中数字“1”的个数例如21 → 10101 → 3个置位质数大于1的自然数除了1和它本身外不能被其他自然数整除例如2、3、5、7等。2. 示例拆解以示例1为例输入 left6、right106 → 二进制 110 → 置位个数22是质数计数17 → 二进制 111 → 置位个数33是质数计数18 → 二进制 1000 → 置位个数11不是质数不计数9 → 二进制 1001 → 置位个数22是质数计数110 → 二进制 1010 → 置位个数22是质数计数1最终结果为4与题目输出一致核心是“先统计置位个数再判断是否为质数”。3. 边界条件与约束题目给出的约束的关键的是1 ≤ left ≤ right ≤ 10⁶0 ≤ right - left ≤ 10⁴区间内最多有10⁴1个数字遍历压力小。隐藏约束10⁶的二进制表示最多有20位2²⁰ 1048576因此置位个数的最大值为20。这一隐藏条件是后续优化质数判断的核心依据。二、解题思路拆解两步核心本题的解题流程可拆解为两个独立的子问题顺序执行即可步骤1计算一个整数的二进制置位个数1的个数计算二进制中1的个数常用的3种方法按效率从高到低排序位运算优化法推荐利用 n (n-1) 操作每次清除二进制中最右侧的1直到n变为0操作次数即为1的个数。原理n-1会将n最右侧的1变为0右侧的0变为1与n进行与运算后最右侧的1及右侧所有位都会变为0示例n6110n-15101n(n-1)4100清除1次再执行n4n-13n(n-1)0共2次即置位个数为2。Python内置函数法利用 bin(n).count(‘1’)bin(n) 会将n转为二进制字符串前缀为’0b’count(‘1’) 直接统计1的个数代码最简洁。遍历判断法通过循环遍历二进制的每一位判断是否为1适合新手理解但效率最低。步骤2判断一个数是否为质数结合隐藏约束置位个数最大为20质数判断可针对性优化置位个数的可能取值范围020因此只需判断“020中的质数”即可0~20中的质数列表{2, 3, 5, 7, 11, 13, 17, 19}优化方案将质数列表存入集合判断时直接通过“元素是否在集合中”实现O(1)查询比传统质数判断遍历试除效率更高。传统质数判断补充适用于置位个数不确定的场景对于一个数x若x≤1则不是质数若x2则是质数若x为偶数则不是质数否则遍历3到√x判断是否能整除x能则不是质数否则是质数。整体解题流程初始化计数变量result0遍历区间 [left, right] 中的每一个整数n计算n的二进制置位个数count判断count是否为质数若是则result 1遍历结束后返回result。三、代码实现多解法对比本文按照“简洁版→优化版→新手版”的顺序实现均严格遵循题目要求的Solution类结构可直接复制提交到LeetCode。解法1简洁版Python内置函数质数集合推荐提交核心优势代码简洁效率满足题目要求区间最大10⁴1个数字内置函数执行速度快适合实际提交。classSolution:defcountPrimeSetBits(self,left:int,right:int)-int:# 0~20中的质数集合O(1)查询prime_set{2,3,5,7,11,13,17,19}result0# 遍历区间内每一个数字forninrange(left,right1):# 计算二进制置位个数bin(n)转为二进制字符串count(1)统计1的个数countbin(n).count(1)# 判断置位个数是否为质数ifcountinprime_set:result1returnresult解法2优化版位运算计算置位个数效率更高核心优势位运算比内置函数更底层在海量数据场景下效率更优适合理解二进制操作的核心逻辑。classSolution:defcountPrimeSetBits(self,left:int,right:int)-int:prime_set{2,3,5,7,11,13,17,19}result0# 辅助函数计算一个数的二进制置位个数位运算版defcount_set_bits(n):count0whilen0:# 清除最右侧的1每次操作count1nn-1count1returncountforninrange(left,right1):ifcount_set_bits(n)inprime_set:result1returnresult解法3新手版遍历判断置位传统质数判断核心优势逻辑最直观适合新手理解“置位统计”和“质数判断”的底层逻辑不依赖内置函数和优化技巧。classSolution:defcountPrimeSetBits(self,left:int,right:int)-int:result0# 辅助函数1计算置位个数遍历判断版defcount_set_bits(n):count0whilen0:# 判断最右侧一位是否为1countn1# 右移一位继续判断下一位n1returncount# 辅助函数2判断一个数是否为质数传统试除版defis_prime(x):ifx1:returnFalseifx2:returnTrueifx%20:returnFalse# 遍历3到√x步长为2只判断奇数foriinrange(3,int(x**0.5)1,2):ifx%i0:returnFalsereturnTrueforninrange(left,right1):ifis_prime(count_set_bits(n)):result1returnresult四、代码执行效率分析针对题目约束right-left ≤ 10⁴三种解法的执行效率差异不大均能在1ms内完成LeetCode提交结果具体对比如下解法核心实现时间复杂度空间复杂度优势简洁版bin(n).count(‘1’) 质数集合O((right-left1) * 20)每个数最多20位二进制O(1)质数集合固定大小代码简洁提交速度快优化版位运算 质数集合O((right-left1) * k)k为置位个数最多20O(1)效率最高适合海量数据新手版遍历判断置位 传统质数判断O((right-left1) * 20 * √20)质数判断最多到√20O(1)逻辑直观适合新手理解实际开发中优先选择简洁版代码简洁易维护若追求极致效率可选择优化版新手学习时建议从新手版入手理解底层逻辑。五、易错点与注意事项质数判断的边界错误容易将1判断为质数1不是质数将2判断为非质数2是唯一的偶质数规避方法牢记0~20的质数列表或在质数判断函数中明确处理x1和x2的情况。置位个数计算错误使用位运算时容易忘记“n (n-1)”的循环终止条件n0导致少统计或多统计置位规避方法循环条件严格设为n0每次循环后n会逐步减小直到变为0时终止。区间遍历错误range(left, right) 会遗漏right需改为 range(left, right 1)确保闭区间全覆盖。性能冗余无需使用复杂的质数判断算法如埃氏筛法因为置位个数最大为20直接用集合查询效率最高过度优化反而增加代码复杂度。六、拓展延伸进阶思考1. 若约束扩大right ≤ 10⁹如何优化当right扩大到10⁹时区间内数字个数可能达到10⁹直接遍历会超时可结合“二进制置位个数的规律”和“埃氏筛法”优化第一步用埃氏筛法预处理出0~30的所有质数因为2³⁰ 10⁹置位个数最大为30第二步使用“数位DP”统计区间[left, right]内置位个数为质数的数字总数时间复杂度可优化到O(log right)。2. 相关类似题目推荐LeetCode 191. 位1的个数单独练习“二进制置位个数统计”巩固位运算技巧LeetCode 204. 计数质数单独练习“质数判断”掌握埃氏筛法等高效质数筛选技巧LeetCode 338. 比特位计数统计0~n中每个数的置位个数可进一步巩固位运算优化思路。七、总结本题的核心是“拆分问题”将复杂问题拆解为“置位个数统计”和“质数判断”两个简单子问题再结合题目约束进行针对性优化。对于简单算法题“拆解优化”是核心解题思路——无需追求复杂的算法先保证逻辑正确再根据约束条件优化效率既能快速解题又能兼顾代码的简洁性和可读性。三种解法中简洁版最适合实际提交优化版适合理解底层逻辑新手版适合入门学习。建议读者先掌握简洁版再逐步深入理解位运算和质数判断的细节为后续更复杂的二进制算法题打下基础。