https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/description/
https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/113232/665772
0b10100010100010101100 is the bit wise representation of 665772.
Here 2nd,3rd,5th,7th,11th,13th,17th,19th,23rd and 29th bits are 1 and rest are 0s.
What do all these positions have in common? they are prime numbers!
Example:
-Let say a number has 5 bits set, (calculated by using __builtin_popcount(L)).
-To check if 5 is prime shift 0b10100010100010101100 by 5
-This gives you 0b00000101000101000101,
-When you & it with 0b1 you get 1, hence 5 is prime number!
public int countPrimeSetBits(int L, int R) {
int ans = 0;
for (int x = L; x <= R; ++x)
if (isSmallPrime(Integer.bitCount(x)))
ans++;
return ans;
}
public boolean isSmallPrime(int x) {
return (x == 2 || x == 3 || x == 5 || x == 7 ||
x == 11 || x == 13 || x == 17 || x == 19);
}
http://www.cnblogs.com/grandyang/p/8642157.html
由于题目中给了数的大小范围 R <= 106 < 220，那么我们统计出来的非零位个数cnt只需要检测是否是20以内的质数即可，所以我们将20以内的质数都放入一个HashSet中，然后统计出来cnt后，直接在HashSet中查找有没有即可
https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/113227/JavaC++-Clean-Code
X. DP
https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/113248/Easy-O(n)-Java-solution-using-DP
https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/113232/665772
https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-762-prime-number-of-set-bits-in-binary-representation/
Given two integers
L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.
(Recall that the number of set bits an integer has is the number of
1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)
Example 1:
Input: 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)
Example 2:
Input: 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)
Note:
L, Rwill be integersL <= Rin the range[1, 10^6].R - Lwill be at most 10000.
0b10100010100010101100 is the bit wise representation of 665772.
Here 2nd,3rd,5th,7th,11th,13th,17th,19th,23rd and 29th bits are 1 and rest are 0s.
What do all these positions have in common? they are prime numbers!
Example:
-Let say a number has 5 bits set, (calculated by using __builtin_popcount(L)).
-To check if 5 is prime shift 0b10100010100010101100 by 5
-This gives you 0b00000101000101000101,
-When you & it with 0b1 you get 1, hence 5 is prime number!
public int countPrimeSetBits(int L, int R) {
return IntStream.range(L, R+1).map(i -> 665772 >> Integer.bitCount(i) & 1).sum();
}
public int countPrimeSetBits(int L, int R) {
int ans = 0;
for (int x = L; x <= R; ++x)
if (isSmallPrime(Integer.bitCount(x)))
ans++;
return ans;
}
public boolean isSmallPrime(int x) {
return (x == 2 || x == 3 || x == 5 || x == 7 ||
x == 11 || x == 13 || x == 17 || x == 19);
}
http://www.cnblogs.com/grandyang/p/8642157.html
由于题目中给了数的大小范围 R <= 106 < 220，那么我们统计出来的非零位个数cnt只需要检测是否是20以内的质数即可，所以我们将20以内的质数都放入一个HashSet中，然后统计出来cnt后，直接在HashSet中查找有没有即可
https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/113227/JavaC++-Clean-Code
public int countPrimeSetBits(int l, int r) {
Set<Integer> primes = new HashSet<>(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19 /*, 23, 29 */ ));
int cnt = 0;
for (int i = l; i <= r; i++) {
int bits = 0;
for (int n = i; n > 0; n >>= 1)
bits += n & 1;
cnt += primes.contains(bits) ? 1 : 0;
}
return cnt;
}
public int countPrimeSetBits(int L, int R) {
Set<Integer> primes = new HashSet<>(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19));
return (int)IntStream.range(L, R + 1).map(Integer::bitCount).filter(primes::contains).count();
}
https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/113248/Easy-O(n)-Java-solution-using-DP
public int countPrimeSetBits(int L, int R) {
int cnt = 0;
Set<Integer> listPrimes = new HashSet<>(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ));
int[] res = countBits(R);
for(int i=L;i<=R;i++){
if(listPrimes.contains(res[i])){
cnt++;
}
}
return cnt;
}
public int[] countBits(int num) {
if(num == 0)
return new int[1];
int[] dp = new int[num+1];
dp[0] = 0;
dp[1] = 1;
for(int i=2;i<=num;i++){
dp[i] = dp[i >> 1] + dp[i & 1]; // i >> 1 is i / 2 and i & 1 is i % 2
}
return dp;
}https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/113232/665772
The prime+1 digits of binary 665772 are all 1 until the 18th digit.
public int countPrimeSetBits(int L, int R) {
int count = 0;
while (L <= R)
count += 665772 >> Integer.bitCount(L++) & 1;
return count;
}https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-762-prime-number-of-set-bits-in-binary-representation/
public int countPrimeSetBits(int L, int R) {
int ans = 0;
for (int n = L; n <= R; ++n)
if (isPrime(bits(n))) ++ans;
return ans;
}
private boolean isPrime(int n) {
if (n <= 1) return false;
if (n == 2) return true;
for (int i = 2; i <= (int)Math.sqrt(n); ++i)
if (n % i == 0) return false;
return true;
}
private int bits(int n) {
int s = 0;
while (n != 0) {
s += n & 1;
n >>= 1;
}
return s;
}
https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/158109/A-fast-algorithm-utilizing-Pascal's-Triangle
Let's observe first, how we may count the total number of set bits from
(L,0]. We start with "simple numbers", e.g. 0b10000, with a 1 at position n followed by n-1 0s:| n | L | Possible bit combos within (L,0] | 0 set bits | 1 set bits | 2 set bits | 3 set bits |
|---|---|---|---|---|---|---|
| 1 | 0b1 | 0b0 | 1 | |||
| 2 | 0b10 | 0b1, 0b0 | 1 | 1 | ||
| 3 | 0b100 | 0b11, 0b10, 0b1, 0b0 | 1 | 2 | 1 | |
| 4 | 0b1000 | 0b111, 0b110, 0b101, 0b100, 0b11, 0b10, 0b1, 0b0 | 1 | 3 | 3 | 1 |
* It can be proven easily using combinatorics, that the number of set bits of such a "simple number" follows the Pascal's Triangle.
More complex scenarios
Given a more complex number, such as
Given more comples numbers and you may need to divide it into several ranges and use a similar procesure to get the number of set bits.
0b1100, the number of set bits within (0b1100,0] can be obtained by combining the set bits in two ranges: 1) (0b1100,0b1000] and 2) (0b1000,0]. The set bits of range 2 can be directly looked up in our Pascal Triangle. The set bit of range 1 is a bit tricky. You look up 0b100 in the triangle, which gives you {0:1,1:2, 2:1} and then you shift the set bit by 1 to obtain {1:1, 2:2, 3:1}. This is to accomodate the fact that there is a bit 1 ahead of 0b100.Given more comples numbers and you may need to divide it into several ranges and use a similar procesure to get the number of set bits.
So that is the idea of using Pascal Triangle to obtain set bits in range
(L,0]. With a little modification, one can get the prime number of set bits in range [L,R].Time complexity
The time complexity is in the order of
O(N^2) where N is the position of the most significant bit in R.Sample Code
Python for expresiveness.
class Solution:
def getMostSignificantBitPosition(self,num):
"""
param: A *positive* number
return: The position of the most significant bit
Example:
Given 0b101001
Return 6
"""
return len(bin(num))-len("0b")
def getPascalTriangle(self, num):
"""
param: The desired triangle level
return: A pascal triangle of desired leven
Example
Given 4
Return [[1] index:0 level:1
[1,1]
[1,2,1]
[1,3,3,1]
]
#bit set 0 1 2 3 ...
"""
# Assume num>=1
ret = [[1]]
for i in range(1,num):
tmp=[1]
for m,n in zip(ret[i-1][1:],ret[i-1][:-1]):
tmp.append(m+n)
tmp.append(1)
ret.append(tmp)
return ret
def getPrimeBitSets(self,num,PascalTriangle):
"""
param: a positive number smaller than 2^32
param: a pascal triangle of enough level
return: the number of prime bit sets in range (num,0]
Example
Given 0b1001
Return
"""
# Prime table
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
# 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
isPrime = [0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0,
1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0]
primeCount = 0
prevBitCount = 0
pos = self.getMostSignificantBitPosition(num)
for p in range(pos,0,-1): # p for position
mask = 1 << (p-1)
if mask & num == 0:
continue
# Encountered bit '1'
# Loop up the triangle for prime bit sets
for n,v in enumerate(PascalTriangle[p-1]): # n for bit sets
if isPrime[n+prevBitCount]:
primeCount+=v
# END FOR
prevBitCount+=1
# END FOR
return primeCount
def countPrimeSetBits(self, L, R):
"""
:type L: int
:type R: int
:rtype: int
"""
# To obtain prime number of bit sets in range [R,L]
# We opt to obtain prime number of bit sets
# in range (R+1,0] and (L,0] and use subtraction to
# obtain that in range [R,L]
# Needed to run getPrimeBitSets(R+1,trangle)
triangle = self.getPascalTriangle(
self.getMostSignificantBitPosition(R+1) )
return self.getPrimeBitSets(R+1,triangle)-self.getPrimeBitSets(L,triangle)