tags:
- Bit Manipulation
categories:
- leetcode
題目： 給定兩個(gè)整數(shù) L 和 R ，找到閉區(qū)間 [L, R] 范圍內(nèi)，計(jì)算置位位數(shù)為質(zhì)數(shù)的整數(shù)個(gè)數(shù)汰瘫。
（注意，計(jì)算置位代表二進(jìn)制表示中1的個(gè)數(shù)诉位。例如 21 的二進(jìn)制表示 10101 有 3 個(gè)計(jì)算置位诈闺。還有，1 不是質(zhì)數(shù)厂镇。）
input example1:
輸入: L = 6, R = 10
輸出: 4
解釋:
6 -> 110 (2 個(gè)計(jì)算置位纤壁，2 是質(zhì)數(shù))
7 -> 111 (3 個(gè)計(jì)算置位，3 是質(zhì)數(shù))
9 -> 1001 (2 個(gè)計(jì)算置位剪撬，2 是質(zhì)數(shù))
10-> 1010 (2 個(gè)計(jì)算置位摄乒，2 是質(zhì)數(shù))
input example2:
輸入: L = 10, R = 15
輸出: 5
解釋:
10 -> 1010 (2 個(gè)計(jì)算置位, 2 是質(zhì)數(shù))
11 -> 1011 (3 個(gè)計(jì)算置位, 3 是質(zhì)數(shù))
12 -> 1100 (2 個(gè)計(jì)算置位, 2 是質(zhì)數(shù))
13 -> 1101 (3 個(gè)計(jì)算置位, 3 是質(zhì)數(shù))
14 -> 1110 (3 個(gè)計(jì)算置位, 3 是質(zhì)數(shù))
15 -> 1111 (4 個(gè)計(jì)算置位, 4 不是質(zhì)數(shù))
注意:
-
[L,R]是[L<R]且在【1，10^6]中的整數(shù)残黑。 -
R-L的最大值是10000.
知識(shí)點(diǎn)：
- 位運(yùn)算
- itoa函數(shù)實(shí)現(xiàn)進(jìn)制轉(zhuǎn)化
- __buittin_popcount(i);
代碼實(shí)現(xiàn)1：
class Solution {
public:
int countPrimeSetBits(int L, int R) {
int res=0;
for(int i=L;i<=R;++i){
int cnt=__builtin_popcount(i);
res+=cnt<4 ? cnt>1 :(cnt % 2&& cnt % 3);
}
return res;
}
};
代碼實(shí)現(xiàn)2：
class Solution {
public:
int countPrimeSetBits(int L, int R) {
int res = 0;
unordered_set<int> primes{2, 3, 5, 7, 11, 13, 17, 19};
for (int i = L; i <= R; ++i) {
int cnt = 0;
for (int j = i; j > 0; j >>= 1) {
cnt += j & 1;
}
res += primes.count(cnt);
}
return res;
}
};
