Count the no of Set Bits between L and R for only prime positions in Python

You are given two integers- lower limit(L) and upper limit(R). You have to find the no of set bits in the binary representation of the numbers between L and R (both inclusive) for only prime positions.

Eg. L=0, R=7

Output:

8

The explanation is for only 9 bits. But we will implement for 32 bits. So, now we will see how to solve the problem.

Counting the no of Set Bits between L and R for only prime positions

We will see the algorithm, program and time complexity of the program.

Algorithm for optimal solution:

• Take the prime positions up to 32 in a list.
• You can notice that for position 2, for every 4 (i.e 2^2) numbers there are 2 (i.e 2^1) set bits. Similarly,  for position 3, for every 8 (i.e 2^3) numbers there are 4 (i.e 2^2) set bits and so on. So, for the position n, for every 2^n numbers, there are 2^(n-1) set bits.
• Following the above logic, you have to calculate the total no of set bits for every prime position from 0 to R and 0 to (L-1).
• Now, Subtract the two results to get the actual output.

Python Program for the problem:

prime_pos=[2,3,5,7,11,13,17,19,23,29,31] #List of prime positions
lower=int(input("Enter lower limit: ")) #Take Lower limit from user
upper=int(input("Enter upper limit: "))#Take Upper limit from user
def calculate(n):
    tot_set_bit=0
    for i in prime_pos: #Iterate for every prime position
        cycle=2**i 
        set_bit=cycle//2
        tot_set_bit+=((n+1)//cycle)*set_bit
        if((n+1)%cycle>set_bit):
            tot_set_bit+=(n+1)%cycle-set_bit
    return tot_set_bit
''' Call the function for R(upper) and for (L-1)(lower) and subtract the result'''
print("The no of set bits:",calculate(upper)-calculate(lower-1)) 

Input/Output:

1.

Enter lower limit: 0
Enter upper limit: 7
The no of set bits: 8

2.

Enter lower limit: 4
Enter upper limit: 20
The no of set bits: 22

The code is only the implementation of the above algorithm. In the above code, tot_set_bit counts the total no of set bits. For every 2^n numbers (denoted by the variable cycle) there are 2^(n-1) set bits (denoted by set_bit) where n denotes the prime position.

Time Complexity:

O(1)

You may also read:

• Find the parity of a number using Python