Find Rightmost Set Bit of a Number

Problem

Given a non-negative integer n, find the position of its rightmost set bit (least-significant 1) in its binary representation.

Positions in this page are 1-based (i.e., the least-significant bit has position 1).

Examples

Example 1

Input: n = 1
Output: 1

Example 2

Input: n = 6  # 0b110
Output: 2

Example 3

Input: n = 11 # 0b1011
Output: 1

Example 4

Input: n = 24 # 0b11000
Output: 4

Solution

Below are three common approaches to obtain the rightmost set bit (either its value as a mask, or its 1-based position).

Method 1 — Extract mask using n & -n (recommended)

Intuition

The expression n & -n isolates the lowest set bit as a mask (a power of two). For example, if n = 0b10110, then n & -n = 0b10.

Approach

• If n == 0 there is no set bit; return a sentinel (e.g., 0 for mask or -1 for position).
• Compute mask = n & -n (two's complement arithmetic).
• To get the 1-based position from mask, compute the index of that single set bit.

Edge cases:

• n == 0 → return -1 (position) or 0 (mask).

Code

C++

class Solution {
 public:
  // returns 1-based position of rightmost set bit, or -1 if none
  int rightmost_pos(unsigned int n) {
    if (n == 0) return -1;
    unsigned int mask = n & -static_cast<int>(n);
    return __builtin_ctz(mask) + 1;  // ctz = count trailing zeros (0-based)
  }
};

Go

package main

import "math/bits"

func RightmostPos(n uint32) int {
    if n == 0 { return -1 }
    mask := n & -n
    return bits.TrailingZeros32(mask) + 1
}

Java

class Solution {
    public int rightmostPos(int n) {
        if (n == 0) return -1;
        int mask = n & -n;
        return Integer.numberOfTrailingZeros(mask) + 1;
    }
}

Python

class Solution:
    def rightmost_pos(self, n: int) -> int:
        if n == 0:
            return -1
        mask = n & -n
        # bit_length() on a power-of-two gives the 1-based index
        return mask.bit_length()

Complexity

• ⏰ Time complexity: O(1) — constant-time bit operations on fixed-size words.
• 🧺 Space complexity: O(1).

Method 2 — Right-shift scan

Intuition

Scan bits from LSB to MSB until you encounter a 1; count how many shifts were required.

Approach

• If n == 0 return -1.
• Initialize pos = 1.
• While (n & 1) == 0: n >>= 1, pos += 1.
• Return pos when (n & 1) == 1.

Code

C++

class Solution {
 public:
  int rightmost_pos_scan(unsigned int n) {
    if (n == 0) return -1;
    int pos = 1;
    while ((n & 1u) == 0u) { n >>= 1; ++pos; }
    return pos;
  }
};

Go

func RightmostPosScan(n uint) int {
    if n == 0 { return -1 }
    pos := 1
    for (n & 1) == 0 {
        n >>= 1
        pos++
    }
    return pos
}

Java

class Solution {
    public int rightmostPosScan(int n) {
        if (n == 0) return -1;
        int pos = 1;
        while ((n & 1) == 0) { n >>= 1; pos++; }
        return pos;
    }
}

Python

class Solution:
    def rightmost_pos_scan(self, n: int) -> int:
        if n == 0:
            return -1
        pos = 1
        while (n & 1) == 0:
            n >>= 1
            pos += 1
        return pos

Complexity

• ⏰ Time complexity: O(b) where b is the index of the first set bit (worst-case word size).
• 🧺 Space complexity: O(1).

Method 3 — Using logarithm on the isolated mask (not recommended)

Intuition

If you isolate the rightmost set bit as mask = n & -n, then its position equals 1 + log2(mask). This uses floating-point math and may be prone to rounding errors; builtins are preferred.

Approach

• Compute mask = n & -n.
• Compute position as 1 + floor(log2(mask)) (or log2(mask) with careful rounding).

Code

C++ (sketch)

int rightmost_pos_log(unsigned int n) {
  if (n == 0) return -1;
  unsigned int mask = n & -static_cast<int>(n);
  return 1 + static_cast<int>(std::log2(mask));
}

Java (sketch)

int rightmostPosLog(int n) {
  if (n == 0) return -1;
  int mask = n & -n;
  return 1 + (int)(Math.log(mask) / Math.log(2));
}

Python

def rightmost_pos_log(n: int) -> int:
    if n == 0:
        return -1
    mask = n & -n
    from math import log2
    return 1 + int(log2(mask))

Complexity

• ⏰ Time complexity: O(1) (but uses floating-point ops).
• 🧺 Space complexity: O(1).

Notes & References

• Prefer Method 1 (bit trick) or platform builtins (ctz / TrailingZeros) for correctness and speed.
• Original article and a sample implementation are listed in source_links in the frontmatter.