Reset All Bits

Easy
0/40
Average time to solve is 15m
4 upvotes
Asked in companies
IxigoCommvault

Problem statement

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).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
9
6
Sample Output 1:
8
4
Explanation For Sample Output 1:
In the first test case, the given integer is 9 (1001). Thus by changing every bit to zero to the right of MSB, it becomes 8 (1000).

In the second test case, the given integer is 6 (110). Thus by changing every bit to zero to the right of MSB, it becomes 4 (100).
Sample Input 2:
2
15
25
Sample Output 2:
8
16
Explanation For Sample Output 2:
In the first test case, the given integer is 15 (11111). Thus by changing every bit to zero to the right of MSB, it becomes 8 (1000).

In the second test case, the given integer is 25 (11001). Thus by changing every bit to zero to the right of MSB, it becomes 16 (10000).
Hint

Can you think of iterating the bits?

Approaches (2)
Brute Force

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:

 

  1. Run a loop for ‘i’ from 31 to 0:
    • If  (1<<i) & ‘N’ is not equal to 0:
      • Return 2 ^ ‘i’.
Time Complexity

O(1), 

Because constant time operations are used.

Space Complexity

O(1),

 

Because we are not using any extra space for finding our answer.

 

Code Solution
(100% EXP penalty)
Reset All Bits
Full screen
Console