Last Updated: 21 Nov, 2020
Position of Right Most Set Bit
Easy
Asked in companies
You are given a number N. You need to return the position of the rightmost set bit.
For example:
If the given number is 10 with the binary representation: 1010
The rightmost set bit would be 2 (counted from right).
Input Format:
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the T test cases follow.
The first line of each test case contains a single integer N.
Output Format:
For each test case, print the position of the rightmost set bit.
Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 10^9
Time Limit : 1 sec
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Approaches
- Check each bit starting from right to left.
- Return the first bit you encounter which is 1.
- The given number is <= 10^9. The maximum number of bits can be 32.
- We can make a loop of 32 and check each bit if it is on or off.
- This can be done by left shifting 1 with i (in the loop) and taking AND of this with the given number.
- Check if the current number has 1 in its right most position.
- Divide N by 2 until it has 1 in its right most position.
- Simultaneously, increase the value of position, and finally return the position when the right most position has 1.
- This method has a drawback since it modifies the original number.
- Take two’s complement of the number. It can be calculated by inverting all the bits and adding 1 to it.
- For example if the given number is 5 with binary representation 101. Its two’s complement would be: 011. (first we invert the bits to get 010. Now we add 1 to it, and get 011)
- All bits will be reversed except for the first 1 from right.
- Take bitwise and of the two’s complement with the original number.
- Take log to the base 2 of this number to get the position.
- Add 1 to get the answer in 1 indexing.
Similar problems
Pair Product Div by K
Moderate
Posted: 15 May, 2022
Pair Product Div by K
Moderate
Posted: 15 May, 2022
Merge Two Sorted Arrays Without Extra Space
Moderate
Posted: 19 Nov, 2022
Merge Two Sorted Arrays Without Extra Space
Moderate
Posted: 19 Nov, 2022
Co-Prime
Hard
Posted: 14 Dec, 2022
First Digit One
Moderate
Posted: 14 Oct, 2025
Special Digit Numbers
Hard
Posted: 31 Oct, 2025