Start practising

Set the rightmost unset bit

Easy Bit Manipulation Tricks to remember Original on GeeksforGeeks

Set the rightmost unset bit is a easy bit manipulation problem solved with the tricks to remember pattern. The best approach, optimal (n | (n + 1)), runs in O(1) time and O(1) space. Below are 2 approaches in Java, from scan bits from the right up.

Problem

Set the rightmost 0 bit of n (below its highest set bit) to 1 and return the result. If every bit is already 1, return n unchanged.

Examples

Example 1

Input
n = 6
Output
7
Why
110 → 111.

Example 2

Input
n = 15
Output
15
Why
1111 has no unset bit below its highest set bit, so it stays the same.

Constraints

  • 1 <= n <= 10^9

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Scan bits from the rightO(log n)O(1)
Optimal (n | (n + 1))O(1)O(1)

1Scan bits from the right

TimeO(log n)
SpaceO(1)

Find the lowest 0 bit by checking bits from position 0 upward and set it.

  1. If n + 1 is a power of two, all bits are set: return n.
  2. Find the smallest i with bit i == 0; return n | (1 << i).
Java
class Solution {
    static int setBit(int n) {
        if ((n & (n + 1)) == 0) return n;
        int i = 0;
        while (((n >> i) & 1) == 1) i++;
        return n | (1 << i);
    }
}

2Optimal (n | (n + 1))

TimeO(1)
SpaceO(1)

Adding 1 flips the trailing 1s to 0 and the rightmost 0 to 1. OR with the original restores the trailing 1s, so only that one bit changes.

  1. If (n & (n + 1)) == 0, return n (no unset bit below the top).
  2. Return n | (n + 1).
Java
class Solution {
    static int setBit(int n) {
        if ((n & (n + 1)) == 0) return n;
        return n | (n + 1);
    }
}

Edge cases to test

  • All bits already set (2^k - 1): return n unchanged

Hints

Hint 1

n + 1 turns the rightmost 0 into 1 (and clears the 1s below it). OR it with n to keep those 1s.

FAQ

What is the best time complexity for Set the rightmost unset bit?

Optimal (n | (n + 1)) runs in O(1) time and O(1) extra space.

Which pattern does Set the rightmost unset bit use?

It is a bit manipulation problem that uses the tricks to remember pattern. Other problems with the same pattern: Number of 1 Bits, XOR of 1 to n Numbers.

Is there a brute force solution for Set the rightmost unset bit?

Yes. Scan bits from the right takes O(log n) time and O(1) space. Find the lowest 0 bit by checking bits from position 0 upward and set it.

Which edge cases should I test for Set the rightmost unset bit?

All bits already set (2^k - 1): return n unchanged.