Home | Projects | Notes > Problem Solving > LC - E - 762. Prime Number of Set Bits in Binary Representation (bit manipulation)

LC - E - 762. Prime Number of Set Bits in Binary Representation (bit manipulation)

Solutions in C

Solution 1

This solution uses bitwise operations.

Complexity Analysis:

• $T=O(mn)$$T = O(mn)$, where $m$$m$ is the number of numbers in the inclusive range [left, right], and $n$$n$ is the average number of set bits in the numbers

  $\to$$\to$ Not sure! Need to double-check!

• $S=O(1)$$S = O(1)$

Solution:

xxxxxxxxxx
46
1
bool isPrime(int n);
2
int countBits(int n);
3

4
int countPrimeSetBits(int left, int right){
5
    int count = 0;
6

7
    while (left <= right)
8
    {
9
        if (isPrime(countBits(left)))
10
            count++;
11

12
        left++;
13
    }
14

15
    return count;
16
}
17

18
int countBits(int n)
19
{
20
    int count = 0;
21

22
    while (n)
23
    {
24
        n &= (n - 1);   // clear lowest set bit
25
        count++;
26
    }
27

28
    return count; 
29
}
30

31
bool isPrime(int n)
32
{
33
    int i;
34

35
    // 1 is not a prime number
36
    if (n == 1)
37
        return false;
38

39
    for (i = 2; i < n; i++)
40
    {
41
        if (n % i == 0)
42
            return false;
43
    }
44

45
    return true;
46
}