当前位置：首页 > news >正文

LeetCode 762.二进制表示中质数个计算置位：位运算（mask O(1)判断）

news 2026/4/4 10:37:05

【LetMeFly】762.二进制表示中质数个计算置位：位运算（mask O(1)判断）

力扣题目链接：https://leetcode.cn/problems/prime-number-of-set-bits-in-binary-representation/

给你两个整数left和right，在闭区间[left, right]范围内，统计并返回计算置位位数为质数的整数个数。

计算置位位数就是二进制表示中1的个数。

例如，21的二进制表示10101有3个计算置位。

示例 1：

输入：left = 6, right = 10输出：4解释：6 -> 110 (2 个计算置位，2 是质数) 7 -> 111 (3 个计算置位，3 是质数) 9 -> 1001 (2 个计算置位，2 是质数) 10-> 1010 (2 个计算置位，2 是质数) 共计 4 个计算置位为质数的数字。

示例 2：

输入：left = 10, right = 15输出：5解释：10 -> 1010 (2 个计算置位, 2 是质数) 11 -> 1011 (3 个计算置位, 3 是质数) 12 -> 1100 (2 个计算置位, 2 是质数) 13 -> 1101 (3 个计算置位, 3 是质数) 14 -> 1110 (3 个计算置位, 3 是质数) 15 -> 1111 (4 个计算置位, 4 不是质数) 共计 5 个计算置位为质数的数字。

提示：

1 <= left <= right <= 10⁶
0 <= right - left <= 10⁴

解题方法：预处理

写个脚本，计算10 6 10^6106范围内二进制下最多有多少个1：1 20 = 1048576 1^{20}=1048576120=1048576

再算出来其中都有哪些是质数：[ 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 ] [2, 3, 5, 7, 11, 13, 17, 19][2,3,5,7,11,13,17,19]

再使用一个整数二进制下的每一位代表一个数是否是质数。

''' LastEditTime: 2026-02-21 12:22:44 '''max_length=0while1<<max_length<1000000:max_length+=1print(f'max_length:{max_length}, 1 <<{max_length}={1<<max_length}')primes=[]foriinrange(2,max_length+1):isnot=Falseforjinrange(2,i):ifi%j==0:isnot=Truebreakifnotisnot:primes.append(i)print(f'primes:{primes}')mask=0forpinprimes:mask|=1<<pprint(f'mask:{mask}')""" max_length: 20, 1 << 20 = 1048576 primes: [2, 3, 5, 7, 11, 13, 17, 19] mask: 665772 """

时间复杂度O ( r i g h t − l e f t ) O(right - left)O(right−left)
空间复杂度O ( N log ⁡ N ) O(N\log N)O(NlogN)

AC代码

C++

/* * @LastEditTime: 2026-02-21 12:28:09 */classSolution{private:constexprstaticintmask=665772;public:intcountPrimeSetBits(intleft,intright){intans=0;for(inti=left;i<=right;i++){if(mask&(1<<__builtin_popcount(i))){// printf("i = %d, cnt1 = %d\n", i, __builtin_popcount(i));ans++;}}returnans;}};