Last Updated: 3 Jan, 2021

Find the lone set bit

Easy

Asked in companies

Solve now

Problem statement

You are given a single non-negative integer ‘N’ who’s binary representation consists of a single ‘1’ digit and the rest of the digits are ‘0’s. Your task is to find the position of the only ‘1’ digit. In other words, your task is to find the position of the only set bit in the binary representation of the input integer ‘N’.

The position of the set bit must be counted from the LSB (Least Significant Bit) end of the Binary number. If the count of set bits in the Binary number is not equal to 1, then your function should return ‘-1’ as output.

Example:-

INPUT   : N = 4
OUTPUT  : 3

In the above example, N = 4, whose Binary representation is “0100”. It is clearly visible that the binary number contains a single set bit, at a position 3 from the LSB end. Hence the output is 3

INPUT : N = 8
OUTPUT: 4

In the above example, N = 8, whose Binary representation is “1000”. It is clearly visible that the binary number contains a single set bit, at a position 4 from the LSB end. Hence the output is 4

INPUT   : N = 9
OUTPUT  : -1

In the above example, N = 9, whose Binary representation is “1001”.  Now, the binary number contains 2 set bits, at a position 4 and 1 from LSB end. Hence the output is -1.

INPUT   : N = 0
OUTPUT  : -1

In the above example, N = 0, whose Binary representation is “0000”.  Now, the binary number contains no set bits at all. Hence the output will be -1.

Input Format

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.

The first and the only line of each test case contains a single integer ‘N’.

Output Format:

For every test case, print a single integer, which is the position of the lone set bit in the binary representation of the input integer ‘N’.

Note:

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100    
0 <= N <= 10^5

Time limit: 1 second

Solve now

Approaches

01 Approach

If we observe a little, we can clearly see that only those integers, which can be represented as a power of 2 have a single set bit in their binary equivalent, and rest either have 0 or more than 1 set bits. Now, we only have to work on the integers which are a power of 2. We will start from the LSB end or the rightmost bit, and check every bit one by one.

We are given a function findSetBit(), which takes a single integer ‘N’ which is our input integer as the parameter, and returns a single integer.
To check if the input integer ‘N’ is a power of 2 or not, we create another function isPower2(), which takes a single integer as the parameter and returns either true or false. This function is based on the logic that an integer ‘N’ will be a power of 2 if the bitwise AND of N and N - 1 will be zero.
We call the function isPower2() on our input integer ‘N’, to check whether it can be represented as a power of 2. If it is not a power of 2, we return -1.
If ‘N’ is a power of 2, we proceed by declaring two variables, ‘J’ as our loop variable and ‘P’ which will store the position of the set bit. Initialize both of them as 1.
In the loop, we perform bitwise AND operation of integer ‘J’ and ‘N’. If the operation returns TRUE, it means that the current bit ‘P’ is a set bit, hence we break the loop and return ‘P’.
If the operation returns FALSE, we set the next bit in ‘J’ by doing a left shift on ‘J’ by 1. Along with that, we increment ‘P’ by 1 to move to the next position from LSB. The loop keeps on repeating the procedure until it encounters a set bit and returns ‘P’ as the answer.

Solve now

02 Approach

We know that the only set bit will always be the leftmost bit or the MSB (Most Significant Bit). So in this approach, we will perform the right shift operation on the only set bit of ‘N’ by 1, until it becomes ‘0’ also keeping the count of each shift. The final value of the count will be the position of the set bit.

We are given a function findSetBit(), which takes a single integer ‘N’ which is our input integer as the parameter, and returns a single integer.
To check if the input integer ‘N’ is a power of 2 or not, we create another function isPower2(), which takes a single integer as the parameter and returns either true or false. This function is based on the logic that an integer ‘N’ will be a power of 2 if the bitwise AND of N and N - 1 will be zero.
We call the function isPower2() on our input integer ‘N’, to check whether it can be represented as a power of 2. If it is not a power of 2, we return -1.
If it is a power of 2, we proceed by declaring a variable “COUNTER” and initializing it with 0.
In the loop, right shift N by 1, and simultaneously increment the “COUNTER”, until N becomes 0.
After the loop breaks, return “COUNTER” which contains our final answer.

Solve now

03 Approach

If the integer is the power of 2, then finding the Log of the base 2, of the input integer N, and incrementing it by 1 will give the position of its set bit. If the integer is a power of two, then its log to the base 2 will give the count of 0s in its binary representation. Hence incrementing it by 1 will be the position of the set bit.

We are given a function findSetBit(), which takes a single integer ‘N’ which is our input integer as the parameter, and returns a single integer.
To check if the input integer ‘N’ is a power of 2 or not, we create another function isPower2(), which takes a single integer as the parameter and returns either true or false. This function is based on the logic that an integer ‘N’ will be a power of 2 if the bitwise AND of N and N - 1 will be zero.
To find the log to the base 2 of N, we create another function log2N() which takes an integer as the only parameter and returns another integer. This function will recursively compute the log to the base 2 and return it.
We call the function isPower2() on our input integer ‘N’, to check whether it can be represented as a power of 2. If it is not a power of 2, we return -1.
If it is a power of 2, we proceed by calling our function log2N() and return it by incrementing by 1. It is our final answer.

Solve now