Find position of the only set bit

Problem Statement

Given a number n that has only one set bit in its binary representation, find the position of that set bit. Positions are counted from the right starting at 1.

If the number has more than one set bit or is 0, return -1.

Example:

Noob-Friendly Explanation

Imagine you have a row of light bulbs, numbered 1, 2, 3... from right to left. Exactly one bulb is turned ON. Your job is to tell which bulb number is glowing.

For example, if the number is 8 (binary: 1000), the ON bulb is at position 4. If the number is 32 (binary: 100000), the ON bulb is at position 6.

But first we need to make sure there's only one bulb ON — if multiple bulbs are ON (like 12 = 1100), we return -1.

Approach 1: Brute Force (Right Shift Until Found)

Intuition

First check if the number has exactly one set bit (power of two). Then keep right-shifting the number until it becomes 1, counting the shifts.

Algorithm

1. Check if n is a power of two using n & (n-1) == 0
2. If not, return -1
3. Keep right-shifting n and counting until n becomes 1
4. Return the count + 1 (1-indexed)

class Solution {
    public static int findPosition(int n) {
        // Must be positive and power of two
        if (n <= 0 || (n & (n - 1)) != 0) {
            return -1;
        }

        int position = 1;
        while (n > 1) {
            n = n >> 1;
            position++;
        }

        return position;
    }

    public static void main(String[] args) {
        System.out.println(findPosition(16)); // 5
        System.out.println(findPosition(2));  // 2
        System.out.println(findPosition(1));  // 1
        System.out.println(findPosition(12)); // -1
        System.out.println(findPosition(0));  // -1
        System.out.println(findPosition(32)); // 6
    }
}

Complexity Analysis

• Time Complexity: O(log N) — We shift at most log₂(N) times
• Space Complexity: O(1) — Only using a counter

Approach 2: Optimal (Using Math / Log)

Intuition

If the number is a power of two, its position is simply log₂(n) + 1. We can compute this directly without any loop.

Algorithm

1. Check if n is a power of two
2. If yes, compute position = log₂(n) + 1
3. We use Integer.numberOfTrailingZeros(n) which gives the exact bit position (0-indexed), so we add 1

class Solution {
    public static int findPosition(int n) {
        // Must be positive and power of two
        if (n <= 0 || (n & (n - 1)) != 0) {
            return -1;
        }

        // numberOfTrailingZeros gives 0-indexed position
        // e.g., for 8 (1000), trailing zeros = 3, position = 4
        return Integer.numberOfTrailingZeros(n) + 1;
    }

    public static void main(String[] args) {
        System.out.println(findPosition(16)); // 5
        System.out.println(findPosition(2));  // 2
        System.out.println(findPosition(1));  // 1
        System.out.println(findPosition(12)); // -1
        System.out.println(findPosition(0));  // -1
        System.out.println(findPosition(32)); // 6
        System.out.println(findPosition(64)); // 7
    }
}

Complexity Analysis

• Time Complexity: O(1) — Direct computation using built-in bit intrinsic
• Space Complexity: O(1) — No extra space

Key Takeaways

1. Only Power of Two: A number with exactly one set bit must be a power of two
2. n & (n-1) == 0: Quick check for power of two
3. Trailing Zeros = Position - 1: The position of the only set bit equals the number of trailing zeros + 1
4. Java Utility: Integer.numberOfTrailingZeros(n) is O(1) and very useful