Position of Right Most Set Bit

Easy

0/40

Average time to solve is 10m

2 upvotes

Asked in companies

Problem statement

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).

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

Sample Output 1:

2
1
4

Explanation of Input 1:

For the first test case, the binary representation of 10 is 1010. So answer is 2
For the second test case, the binary representation of 3 is 11. So answer is 1
For the third test case, the binary representation of 8 is 1000. So answer is 4

Sample Input 2:

Sample Output 2

3
2
4

Hint 1

Hint 2

Hint 3

Check each bit from right to left

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

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.

Time Complexity

O(log2(N))

As in the worst case, all the bits would be checked. This is because the number of bits in the binary representation of N would be log2(N)

Space Complexity

O(1)

In the worst case, no extra constant space is required.

(100% EXP penalty)

Position of Right Most Set Bit

Console