Find Rightmost Unset Bit of a Number

Problem

Given a non-negative integer n, find the position of the rightmost unset (zero) bit in its binary representation.

Positions in this page are 1-based (i.e., least-significant bit has position 1). Return -1 if no unset bit exists in the considered word (or 0 for a mask result — see each method).

Examples

Example 1

Input: n = 11  # 0b1011
Output: 2

Example 2

Input: n = 6   # 0b110
Output: 1

Example 3

Input: n = 13  # 0b1101
Output: 2

Solution

We present three approaches: isolate mask using ~n & (n+1), scan bits, and a logarithm-based variant. Method 1 is preferred.

Method 1 — Extract mask using ~n & (n+1) (recommended)

Intuition

Adding 1 to n flips the least-significant unset bit to 1 and clears any lower set bits. Bitwise ~n turns unset bits to 1. Intersection ~n & (n+1) therefore isolates the rightmost unset bit as a mask.

Approach

• If n has all bits set for the considered word width, there may be no unset bit — decide on sentinel (-1 for position).
• Compute mask = (~n) & (n + 1).
• To obtain 1-based position from mask, compute the index of the single set bit in mask.

Edge cases:

• n == ~0u for fixed-width words → no unset bits (return -1).

Code

C++

class Solution {
 public:
  int rightmost_unset_pos(unsigned int n) {
    unsigned int mask = (~n) & (n + 1u);
    if (mask == 0u) return -1; // no unset bit in this word
    return __builtin_ctz(mask) + 1;
  }
};

Go

package main

import "math/bits"

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

Java

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

Python

class Solution:
    def rightmost_unset_pos(self, n: int) -> int:
        mask = (~n) & (n + 1)
        if mask == 0:
            return -1
        return mask.bit_length()

Complexity

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

Method 2 — Right-to-left scan

Intuition

Check bits from LSB moving left until an unset bit (0) is found.

Approach

• If considering infinite-width integers, n always has unset bits; for fixed-width, check full width.
• Initialize pos = 1.
• While (n & 1) == 1: n >>= 1, pos += 1.
• Return pos.

Code

C++

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

Go

func RightmostUnsetScan(n uint) int {
    pos := 1
    for (n & 1) == 1 {
        n >>= 1
        pos++
    }
    return pos
}

Java

class Solution {
    public int rightmostUnsetScan(int n) {
        int pos = 1;
        while ((n & 1) == 1) { n >>= 1; pos++; }
        return pos;
    }
}

Python

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

Complexity

• ⏰ Time complexity: O(b) where b is the number of consecutive trailing set bits.
• 🧺 Space complexity: O(1).

Method 3 — Logarithm on isolated mask (not recommended)

Intuition

If mask = (~n) & (n+1) isolates the unset-bit as a power-of-two, then position = 1 + log2(mask).

Approach

• Compute mask = (~n) & (n+1).
• Compute pos = 1 + floor(log2(mask)) (avoid floating rounding issues).

Code

C++ (sketch)

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

Java (sketch)

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

Python

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

Complexity

• ⏰ Time complexity: O(1).
• 🧺 Space complexity: O(1).

Notes & References

• Method 1 is robust and efficient; prefer platform builtins for trailing-zero counts when available.
• Source examples are listed in source_links in frontmatter.