Log inSign up
easyGeeksforGeeksNot Started

Find Position of Rightmost 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 index position of the rightmost set bit (first 1 bit starting from the least significant bit) in its binary representation.

If there are no set bits (i.e., n == 0), return 0.

Example 1 · Example 1: Even Number:

Input: n = 18
Output: 2
Explanation: 18 in binary is 10010. The first set bit from right is at position 2.

Example 2 · Example 2: Odd Number:

Input: n = 19
Output: 1
Explanation: 19 in binary is 10011. The least significant bit is set, which is at position 1.

Example 3 · Example 3: Zero Input:

Input: n = 0
Output: 0
Explanation: 0 has no set bits in binary. Returns 0.

Constraints:

  • 0 <= n <= 109

What You'll Learn

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

  • Master the fundamental two's complement identity n & (-n).
  • Convert an isolated power-of-two bit into its 1-based column position.
  • Apply rightmost bit extraction to advanced tree algorithms like Fenwick Trees.

Pattern Recognition Trigger

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

Signals to Look For:

  • Identify index or position of the least significant 1-bit.
  • Find first set bit from the right.
  • Subroutine in Fenwick trees and binary indexed trees.

Algorithmic Decision Tree:

  • If n == 0, return 0.
  • Isolate bit using n & (-n).
  • Compute log2(isolatedBit) + 1.

Connected Patterns:

Find the Only Set BitCount Set BitsFenwick Tree (BIT)

1. Linear Bit Scan

Intuition

If n == 0, return 0. Initialize pos = 1. In a while loop, test if (n & 1) == 1. If yes, return pos. Otherwise, shift n >>= 1 and increment pos.

When to apply: Basic simulation.

Algorithm

  1. Step 1: If n == 0, return 0.
  2. Step 2: Initialize pos = 1.
  3. Step 3: While (n & 1) == 0: n >>= 1, pos++.
  4. Step 4: Return pos.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int getFirstSetBitPosBrute(int n) {
6 if (n == 0) return 0;
7 int pos = 1;
8 while ((n & 1) == 0) {
9 n >>= 1;
10 pos++;
11 }
12 return pos;
13}
14
15int main() {
16 cout << "Brute (18): " << getFirstSetBitPosBrute(18) << endl; // 2
17 cout << "Brute (19): " << getFirstSetBitPosBrute(19) << endl; // 1
18 cout << "Brute (0): " << getFirstSetBitPosBrute(0) << endl; // 0
19 return 0;
20}

Time & Space Complexity

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

2. Isolated Bit Power Scan

Intuition

Calculate lowest = n & (-n). Then shift lowest rightward until it reaches 1, counting how many shifts were performed.

When to apply: When understanding how bit isolation simplifies index location.

Algorithm

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

Time & Space Complexity

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

3. Two's Complement & Log2 (Constant Time)

Intuition

If n == 0, return 0. The expression n & (-n) isolates the lowest set bit as a single power of two 2^k. The 1-based index is k + 1 = log2(2^k) + 1.

When to apply: Optimal O(1) mathematical solution.

Algorithm

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

Rightmost Set Bit Isolation Trace: n = 18

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Compute n = 18 (binary 010010) and -n = -18 (two's complement 101110)
Visual state
Values and pointers at this exact step
pointers
S
010010
101110
0
↑ operands
1
Check / comparison
18 & -18
Decision / next transition
Evaluate bitwise AND.
Why this step matters

Step 1: Compute n = 18 (binary 010010) and -n = -18 (two's complement 101110).

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <cmath>
3
4using namespace std;
5
6class Solution {
7public:
8 int getFirstSetBit(int n) {
9 if (n == 0) return 0;
10 return (int)log2(n & (-n)) + 1;
11 }
12};
13
14int main() {
15 Solution sol;
16 cout << "Optimal (18): " << sol.getFirstSetBit(18) << endl; // 2
17 cout << "Optimal (19): " << sol.getFirstSetBit(19) << endl; // 1
18 cout << "Optimal (0): " << sol.getFirstSetBit(0) << endl; // 0
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 — Linear Bit ScanO(log n)O(1)Loop while (n & 1) == 0, shifting n >>= 1 and incrementing position counter.Sequential bit checking.
2.Better — Isolation + Bit ShiftingO(pos)O(1)Isolate lowest bit via n & (-n), then shift that isolated bit right until it equals 1.Shifting the isolated bit.
3.Optimal — Two's Complement & Log2 / CTZOptimalO(1)O(1)Compute lowest bit = n & (-n), and return log2(lowest bit) + 1 in branchless constant time.Single math / hardware instruction.

Common Pitfalls & Crucial Edge Cases

Returning 0-indexed position instead of 1-indexed position

The problem statement specifies 1-based indexing.

Forgetting the n = 0 guard

Computing log2(0) produces -Infinity or crashes.

Negation of INT_MIN in 32-bit signed integers

In C++, -INT_MIN overflows signed int. Cast to unsigned or handle separately.

Crucial Edge Cases to Validate:

  • n = 0 — Has no set bits; return 0 immediately.
  • n is odd (e.g. n = 19) — Lowest bit is bit 0 (position 1); returns 1.
  • n is a power of 2 (e.g. n = 16 = 10000_2) — Rightmost set bit is the only set bit (position 5).
  • n = INT_MIN (0x80000000) — Only bit 31 is set; returns position 32.

Interview Tips & Best Practices

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

  1. Write n & -n immediately and explain two's complement arithmetic to demonstrate low-level computer architecture fluency.
  2. Mention that built-ins like __builtin_ctz(n) + 1 (count trailing zeros) compile directly to the hardware BSF/TZCNT instructions.
  3. Walk through a quick binary example (e.g. n = 12 = 1100_2 -> -12 = ...0100_2 -> 12 & -12 = 4 -> position 3).

Quick Comprehension Check

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

1.What does the expression n & -n isolate in binary?

2.Once you have isolated the single set bit val = (n & -n), how do you find its 1-indexed position?

3.What should be returned if n = 0?

Back to DSA Sheet