Log inSign up
easyGeeksforGeeksNot Started

Find the Only Set Bit

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an integer n, find the 1-based position of its only set bit (i.e., position from the right starting from 1).

If the number has zero set bits, negative values, or more than one set bit, return -1.

Example 1 · Example 1: Power of Two (16):

Input: n = 16
Output: 5
Explanation: 16 in binary is 10000. It has only one set bit at position 5.

Example 2 · Example 2: Multiple Set Bits (12):

Input: n = 12
Output: -1
Explanation: 12 in binary is 1100. It has two set bits, which violates the single-bit condition. Returns -1.

Example 3 · Example 3: Zero Input:

Input: n = 0
Output: -1
Explanation: 0 has no set bits. Returns -1.

Constraints:

  • -109 <= n <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Combine bitwise validation (n & (n - 1) == 0) with logarithmic indexing.
  • Understand why powers of two represent solitary set bits in binary.
  • Guard against non-positive inputs and overflow conditions.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find the position of the single 1-bit.
  • Validate single-bit exclusivity.
  • Power-of-two index decoding.

Algorithmic Decision Tree:

  • If n <= 0 or (n & (n - 1)) != 0, return -1.
  • Otherwise return log2(n) + 1.

Connected Patterns:

Power of TwoFind Position of Rightmost Set BitCount Set Bits

1. Popcount followed by Linear Scan

Intuition

If n <= 0, return -1. Count set bits by checking n & 1 and shifting right. If total set bits is not equal to 1, return -1. Otherwise, run a second loop to find which position held the 1.

When to apply: Basic demonstration of independent verification and scanning.

Algorithm

  1. Step 1: If n <= 0, return -1.
  2. Step 2: Count bits in n. If count != 1, return -1.
  3. Step 3: Scan bit positions 1 to 32: return position where bit is set.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int findPositionBrute(int n) {
6 if (n <= 0) return -1;
7 int count = 0;
8 int temp = n;
9 while (temp > 0) {
10 count += (temp & 1);
11 temp >>= 1;
12 }
13 if (count != 1) return -1;
14
15 int pos = 1;
16 while ((n & 1) == 0) {
17 n >>= 1;
18 pos++;
19 }
20 return pos;
21}
22
23int main() {
24 cout << "Brute (16): " << findPositionBrute(16) << endl; // 5
25 cout << "Brute (12): " << findPositionBrute(12) << endl; // -1
26 cout << "Brute (0): " << findPositionBrute(0) << endl; // -1
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(log n)
  • Space complexity: O(1)

2. Power of Two Check with Shift Loop

Intuition

First, verify that n > 0 && (n & (n - 1)) == 0. If invalid, return -1. Otherwise, loop i from 0 to 30: if (1 << i) == n, return i + 1.

When to apply: When avoiding floating point math functions like log2.

Algorithm

  1. Step 1: If n <= 0 || (n & (n - 1)) != 0, return -1.
  2. Step 2: Loop i from 0 to 30.
  3. Step 3: If (1 << i) == n, return i + 1.
  4. Step 4: Return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int findPositionShiftLoop(int n) {
6 if (n <= 0 || (n & (n - 1)) != 0) return -1;
7 for (int i = 0; i <= 30; ++i) {
8 if ((1 << i) == n) {
9 return i + 1;
10 }
11 }
12 return -1;
13}
14
15int main() {
16 cout << "Better (16): " << findPositionShiftLoop(16) << endl; // 5
17 cout << "Better (12): " << findPositionShiftLoop(12) << endl; // -1
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(log n)
  • Space complexity: O(1)

3. Power of Two & Log2 (Constant Time)

Intuition

Check n > 0 && (n & (n - 1)) == 0. If false, return -1. If true, the bit index is given directly by log2(n) + 1.

When to apply: Optimal for production and competitive programming.

Algorithm

  1. Step 1: If n <= 0 or (n & (n - 1)) != 0, return -1.
  2. Step 2: Return log2(n) + 1.

Single Set Bit Validation Trace: n = 16

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Check n > 0
Visual state
Values and pointers at this exact step
pointers
S
10000
0
↑ valid single bit
Check / comparison
16 & 15 == 0
Decision / next transition
Valid power of two. Exactly one set bit exists.
Why this step matters

Step 1: Check n > 0. 16 > 0 is true. Check 16 & (16 - 1) = 16 & 15 = 0.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <cmath>
3
4using namespace std;
5
6class Solution {
7public:
8 int findPosition(int n) {
9 if (n <= 0 || (n & (n - 1)) != 0) return -1;
10 return (int)log2(n) + 1;
11 }
12};
13
14int main() {
15 Solution sol;
16 cout << "Optimal (16): " << sol.findPosition(16) << endl; // 5
17 cout << "Optimal (12): " << sol.findPosition(12) << endl; // -1
18 cout << "Optimal (0): " << sol.findPosition(0) << endl; // -1
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(1)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Full Popcount and Linear ScanO(log n)O(1)Count total 1s. If not equal to 1, return -1. Otherwise, shift right to locate index.Two loops over bits.
2.Better — Power of 2 Check + Shift LoopO(log n)O(1)Check n & (n - 1) == 0. If valid, loop with 1 << i to match n.Linear bit shift comparisons.
3.Optimal — Power of 2 Check + Constant Log2OptimalO(1)O(1)Verify n > 0 && (n & (n - 1)) == 0. Compute position in O(1) via log2(n) + 1.Single math/bitwise instruction.

Common Pitfalls & Crucial Edge Cases

Assuming every input has only one set bit

You MUST validate that n is a power of two using (n & (n - 1)) == 0 first.

Forgetting n <= 0 check

For n = 0, 0 & -1 is 0, but 0 has no set bits.

Off-by-one indexing

Forgetting to add 1 when converting 0-indexed log2(n) to 1-indexed position.

Crucial Edge Cases to Validate:

  • n = 0 — No set bits; returns -1.
  • n is negative — In standard unsigned contexts or signed integers, negative numbers either have multiple set bits or sign bit set; returns -1.
  • n is not a power of 2 (e.g. n = 6 = 110_2) — Multiple set bits; returns -1.
  • n = 1 (2^0) — Returns 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the two-step solution: (1) Validate n > 0 && (n & (n - 1)) == 0, (2) Compute log2(n) + 1.
  2. Mention that log2 can be computed with bit shifts, binary search, or the hardware instruction __builtin_ctz.
  3. Point out that checking (n & (n - 1)) == 0 is identical to checking if n is a power of 2.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How do you verify that an integer n contains exactly ONE set bit?

2.If n does not have exactly one set bit (e.g. n = 0, or n has multiple set bits), what should be returned?

3.What is the 1-indexed position of the set bit in n = 16?

Back to DSA Sheet