Problem Statement
Given an integer n:
Return the position of the only set bit (1) in its binary representation.
Position starts from 1 at the Least Significant Bit (LSB).
If:
then return:
-1
Understanding the Concept
A number has exactly one set bit only if it is a power of 2.
Examples:
| Number | Binary | One Set Bit? |
|---|
| 1 | 0001 | Yes |
| 2 | 0010 | Yes |
| 4 | 0100 | Yes |
| 8 | 1000 | Yes |
| 5 | 0101 | No |
| 10 | 1010 | No |
Important Bit Trick
A number has exactly one set bit if:
n & (n - 1) == 0
Why?
Because powers of 2 look like:
1000
0100
0010
Subtracting 1 flips all lower bits:
1000 -> 0111
AND operation becomes:
1000 & 0111 = 0000
Algorithm
Step 1
Check:
n == 0
OR (n & (n - 1)) != 0
If true → return -1.
Step 2
Find position of the set bit.
Keep shifting right until bit becomes 1.
Dry Run
Example 1
Input:
n = 2
Binary:
10
Only one set bit exists.
Counting from right:
Answer:
2
Example 2
Input:
n = 5
Binary:
101
Two set bits exist.
Answer:
-1
Java Solution
class Solution {
public int findPosition(int n) {
// Check if n has exactly one set bit
if (n == 0 || (n & (n - 1)) != 0) {
return -1;
}
int position = 1;
// Find position of set bit
while ((n & 1) == 0) {
n = n >> 1;
position++;
}
return position;
}
}
Complexity Analysis
Time Complexity
O(log n)
Because we may shift bits up to the number of bits in n.
Space Complexity
O(1)
No extra space used.
Alternative Mathematical Insight
If n is a power of 2:
Position = log2(n) + 1
Example:
n = 8
log2(8) = 3
Position = 4
But using bit manipulation is preferred in interviews.
Key Interview Concepts
Power of Two Check
n & (n - 1) = 0
This is one of the most important bit manipulation tricks.
Edge Cases
Case 1
n = 0
Output:
-1
No set bits.
Case 2
n = 1
Binary:
1
Set bit at position:
1
Final Takeaway
To solve this efficiently:
Main trick:
n & (n - 1)
This makes the solution elegant and interview-friendly.
Join the conversation! Your thoughts help the community grow.