Last Updated: 7 Dec, 2020
Reset in Range
Easy
You are given a number. You need to reset the bits from Lth position to Rth position. LSB is at first position (R = 1).
Example: Given number is 94 (1011110), L = 5 and R = 2. If we reset bits from L to R in the number, then the resultant number would be 64 (1000000).
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain a single integer ‘N’ which denotes the input number whose ‘L’th to ‘R’th bit needs to be reset.
The second line of each test case will contain two space separated integers ‘L’ and ‘R’, where ‘L’ denotes the left bound of the range of bits to be reset and ‘R’ denotes the right bound of the range of bits to be reset.
Output Format:
For each test case, print the number after resetting the Lth to Rth bit in the number.
Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of.
Follow up:
Can you solve it in O(1) time and space complexity?
Constraints:
1 <= T <= 10
1 <= N <= 10^9
1 <= R <= L <= 31
Time Limit: 1 sec
Approaches
The basic idea of this approach is to iterate from ‘L’th to ‘R’th bit in the number and reset every bit in the iteration. In each index ‘i’ of the iteration, we first assign the value (1<<’i’) to the variable ‘temp’, where ‘temp’ will store the value of integer whose only ‘i’th bit is set. Then reverse all the bits of ‘temp’ and store again in ‘temp’, which will make every bit set except the ‘i’th bit. Now perform the Bitwise AND of the number ‘N’ with ‘temp’ and store it again and update ‘N’. Thus after iterating the through the required bits i.e. ‘L’th to ‘R’th, we get the updated number ‘N’ as the answer and we return it.
Algorithm:
- Run a loop for ‘i’ from ‘L’-1 to ‘R’-1:
- Declare a variable ‘temp’ and assign the value (1<<’i’) to it, where ‘temp’ will store the value of integer whose only ‘i’th bit is set.
- ‘temp’ = ~’temp’.
- ‘N’ = ‘N’ & ‘temp’.
- Finally, return ‘N’.
The basic of this approach is to first perform the Bitwise XOR of (1<<(‘R’-1)) - 1 and (1<<’L’) - 1 and store it in the integer ‘range’, where ‘range’ will store the value of the integer whose only set bits are from ‘L’ to ‘R’ which we need to reset. Now reverse each bit of the integer ‘range’ and store it back in ‘range’. Thus now ‘range’ will store the value of the integer whose all the bits are set except from ‘L’th to ‘R’th. Now perform the Bitwise AND of the number ‘N’ and ‘range’ and store it back in ‘N’ to get the required answer where ‘L’th to ‘R’th bits are reset in the number.
Algorithm:
- Declare an integer ‘range’ and assign the value ((1<<(‘R’-1)) - 1) to it, where ‘range’ will store the value of the integer whose only set bits are from ‘L’ to ‘R’ which we need to reset.
- ‘range’ = ‘range’ ^ ((1<<’L’) - 1).
- ‘range’ = ~’range’.
- ‘N’ = ‘N’ & ‘range’.
- Finally, return ‘N’.