Last Updated: 8 Dec, 2020
Reset All Bits
Easy
Asked in companies
You are given an integer ‘N’ (32 bits). Your task is to make all the bits to the right of the most significant set bit as zero (0).
Example:
If the input integer is 45 i.e ‘101101’. Then after resetting the bits, it will be ‘100000’. Here The MSB set bit is 3rd from left and hence only the 3rd bit from the left will be set and the rest all the bits will be zero (0).
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first and the only line of each test case contains an Integer ‘N’ denoting the 32-bit integer whose bits need to be altered.
Output Format:
For each test case, return the integer after making all the bits to the right of the most significant set bit as zero (0).
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. Just implement the given function.
Follow Up:
Can you solve this using O(1) time complexity.
Constraints:
1 <= T <= 10^2
1 <= N <= 10^5
Time Limit: 1 sec
Approaches
The basic idea of the approach is that we will iterate each bit starting from the left and when we find any set bit, we return 2^i where ‘i’ is the first 1st set bit from the left and thus we will get every bit zero except for the MSB in the integer.
Here is the algorithm:
- Run a loop for ‘i’ from 31 to 0:
- If (1<<i) & ‘N’ is not equal to 0:
- Return 2 ^ ‘i’.
- If (1<<i) & ‘N’ is not equal to 0:
The basic idea of the approach is that first we need to make all the bits as 1 from the Most Significant Bit to the right till Least Significant Bit i.e. 0th bit. For this we will do the process of ‘SHIFT’ and ‘OR’ with the current integer. Starting with the 1 bit shifting, make the temporary integer by shifting 1 bit to the right in the current integer and adding the resulting temporary number to the current number. Then from the new updated current number again form a new temporary number by shifting 2 bits to the right in the current number and adding that temporary number to the current number. Similarly, do the process of shifting for 4,8,16 bits. Thus by this process the entire 32-bit integer will be covered and all the bits starting from MSB to the right will be 1.
Now add 1 to the current number which will make the current number as 1 followed by zeros. But what we obtained is 1 more zero bit to the right and hence shift again the current number by 1 and we obtain our answer.
Here is the algorithm:
- ‘N’ = ‘N’ | ‘N’ >> 1
- ‘N’ = ‘N’ | ‘N’ >> 2
- ‘N’ = ‘N’ | ‘N’ >> 4
- ‘N’ = ‘N’ | ‘N’ >> 8
- ‘N’ = ‘N’ | ‘N’ >> 16
- ‘N’ = ‘N’ + 1
- ‘N’ = ‘N’ >> 1
- Return ‘N’