Last Updated: 16 Mar, 2022
Two Zeroes
Moderate
A number ‘X’ is interesting if the binary representation of ‘X’ (without leading zeroes) has exactly two zeroes.
You are given two positive integers, ‘L’ and ‘R’. Your task is to count the number of values ‘X’, such that ‘L’ ≤ ‘X’ ≤ ’R’ and ‘X’ is interesting (i.e., it has exactly two zeroes in its binary representation).
Example :
L = 2, R = 9
All the numbers between L and R and their binary representations are:
X = 2 => 10
X = 3 => 11
X = 4 => 100
X = 5 => 101
X = 6 => 110
X = 7 => 111
X = 8 => 1000
X = 9 => 1001
As 4 and 9 are the only numbers with two zeroes in their binary representations, hence the answer is 2.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then the test case follows.
The first line of each test case contains two space-separated integers, ‘L’ and ‘R’, denoting the range in which you have to find interesting integers.
Output Format :
For each test case, count the number of values ‘X’, such that ‘L’ ≤ ‘X’ ≤ ’R’ and ‘X’ has exactly two zeroes in its binary representation.
Output for each test case will be printed on a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ T ≤ 30
1 ≤ L ≤ R ≤ 10^9
Time limit: 1 sec
Approaches
Approach:
- We can try all possible integers ‘X’ such that ‘L’ ≤ ‘X’ ≤ ’R’ and then check if it has exactly two zeroes in its binary representation or not.
- See the algorithm section below to find out how to check if ‘X’ has exactly two zeroes.
Algorithm:
- Declare and initialize a variable ‘ans’ to ‘0’.
- Iterate over all the integers from ‘L’ to ‘R’. Let the iterating variable be ‘i’.
- Declare and initialize a boolean variable ‘st’ to ‘false’.
- Declare and initialize an integer variable ‘cnt’ to ‘0’.
- Iterate over bit position from 30 to 0.
- Check if the bit is high. If it’s high, set ‘st’ to ‘true’.
- Now, if ‘st’ is ‘true’, and the current bit is not high, increment ‘cnt’ by 1.
- If the value of ‘cnt’ is 2, then increment ‘ans’ by 1.
- Finally, return the answer ‘ans’.
Approach:
- One important observation is all the integers can have at most 30 bits high. And since we are interested in the integers having exactly two bits zero. There are approximately (30 C 2) possible integers that are interesting.
- We will exploit the above fact. We will iterate over all the pairs of positions at which we will place 0 bits, and for the rest of the positions, we will keep the bits high. In this way, we can find all the interesting numbers and then check if it’s in the range [‘L’, ‘R’].
- See the algorithm section for implementation details.
Algorithm:
- Declare and initialize a variable ‘ans’ to ‘0’.
- Iterate over the bit position from 0 to 30. Let the iterating variable be ‘i’.
- Then iterate over the two positions where we would place 0 bits. Let the iterating variables be ‘j’ and ‘k’.
- Calculate the number ‘num’ = ((1 << ‘i’) - 1) ^ (1 << ‘j’) ^ (1 << ‘k’)) and check if it’s in the range [‘L’, ‘R’]. If yes, then increment ‘ans’ by 1. Here, << is the bitwise left-shift operator.
- Finally, return the answer ‘ans’.