Skip to main content

Find Position of Set Bit

Problem​

Given a number N having only one ‘1’ and all other ’0’s in its binary representation, find position of the only set bit. If there are 0 or more than 1 set bit the answer should be -1. Position of set bit '1' should be counted starting with 1 from LSB side in binary representation of the number.

Examples:​

Example 1:

Input:
N = 2
Output:
2
Explanation:
2 is represented as "10" in Binary. As we see there's only one set bit and it's in Position 2 and thus the
Output 2.

Example 2:

Input:
N = 5
Output:
-1
Explanation:
5 is represented as "101" in Binary. As we see there's two set bits and thus the Output -1.

Your task:​

You don't need to read input or print anything. Your task is to complete the function findPosition() which takes an integer N as input and returns the answer.

  • Expected Time Complexity: O(log(N))O(log(N))
  • Expected Auxiliary Space: O(1)O(1)

Constraints:​

  • 0<=N<=1080 <= N <= 10^8

Solution​

Python​

def findPosition(self, N):
if N == 0 or (N & (N - 1)) != 0:
return -1
position = 1
while N:
if N & 1:
return position
N >>= 1
position += 1
return -1

Java​

static int findPosition(int N) {
if (N == 0 || (N & (N - 1)) != 0) {
return -1;
}
int position = 1;
while (N != 0) {
if ((N & 1) != 0) {
return position;
}
N >>= 1;
position++;
}
return -1;
}

C++​

int findPosition(int N) {
if (N == 0 || (N & (N - 1)) != 0) {
return -1;
}
int position = 1;
while (N != 0) {
if ((N & 1) != 0) {
return position;
}
N >>= 1;
position++;
}
return -1;
}

C​

int findPosition(int N) {
if (N == 0 || (N & (N - 1)) != 0) {
return -1;
}
int position = 1;
while (N != 0) {
if ((N & 1) != 0) {
return position;
}
N >>= 1;
position++;
}
return -1;
}
  • Time Complexity: O(log(N))O(log(N))
  • Auxiliary Space: O(1)O(1)