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))$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $0 <= 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))$
• Auxiliary Space: $O(1)$