Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Toggle Rightmost Unset Bit

EASYProblemSolveExternal Links

Description

Given a non-negative integer n, find the rightmost bit that is 0 (unset) in its binary representation and set it to 1 (turn it on). Return the resulting number.

In other words, scan the binary digits of n from right to left, locate the first position where the bit is 0, flip that single bit to 1, and return the new value.

If all bits within the current binary length of n are already 1 (for example, n = 15 which is 1111), then the rightmost unset bit is the next higher-order position. Setting that bit effectively prepends a 1 to the binary representation.

Examples

Example 1

Input: n = 6

Output: 7

Explanation: The binary representation of 6 is 110. Scanning from the right, bit0 is 0 — this is the rightmost unset bit. Setting bit0 to 1 gives 111, which is 7.

Example 2

Input: n = 15

Output: 31

Explanation: The binary representation of 15 is 1111. All four bits are already set. The rightmost unset bit is at position 4 (the next higher position). Setting it gives 11111, which is 31.

Example 3

Input: n = 21

Output: 23

Explanation: The binary representation of 21 is 10101. Scanning from the right: bit0 is 1 (set), bit1 is 0 (unset) — this is the rightmost unset bit. Setting bit1 to 1 gives 10111, which is 23.

Constraints

  • 1 ≤ n ≤ 10^9

Editorial

Brute Force

Intuition

The most natural way to solve this problem is to examine each bit of the number one by one, starting from the rightmost (least significant) bit, and stop as soon as we find a 0.

Think of it like walking down a row of light switches from right to left. Each switch is either ON (1) or OFF (0). You walk along, checking each switch. The moment you find one that is OFF, you flip it ON and stop — your job is done.

In binary terms, we can check whether bit at position pos is 0 using the expression (n >> pos) & 1. If this gives 0, we have found the rightmost unset bit. To set (flip) it to 1, we use n | (1 << pos). This creates a number with a single 1 at the target position and ORs it with n, which turns on exactly that bit without affecting any others.

Step-by-Step Explanation

Let's trace through with n = 21 (binary: 10101):

Step 1: Initialize pos = 0. We will check bits from position 0 (rightmost) moving left.

Step 2: Check bit at position 0: (21 >> 0) & 1 = 21 & 1 = 1. Bit0 is 1 (set). This is not what we are looking for. Move to the next position.

Step 3: Increment pos to 1. Check bit at position 1: (21 >> 1) & 1 = 10 & 1 = 0. Bit1 is 0 (unset). We found the rightmost unset bit!

Step 4: Create a mask with a 1 at position 1: mask = 1 << 1 = 2 (binary 00010).

Step 5: Set the bit: result = n | mask = 21 | 2 = 10101 | 00010 = 10111 = 23.

Result: Return 23.

Brute Force — Scanning Bits Right to Left — Watch how we examine each bit from the rightmost position, skipping set bits until we find the first unset bit, then flip it on using a bitmask.

Algorithm

  1. Initialize pos to 0 (start at the rightmost bit)
  2. While the bit at position pos is set (i.e., (n >> pos) & 1 == 1):
    • Increment pos by 1
  3. Create a bitmask: mask = 1 << pos
  4. Set the bit: result = n | mask
  5. Return result

Code

class Solution {
public:
    int setBit(int n) {
        int pos = 0;
        while ((n >> pos) & 1) {
            pos++;
        }
        return n | (1 << pos);
    }
};
class Solution:
    def setBit(self, n: int) -> int:
        pos = 0
        while (n >> pos) & 1:
            pos += 1
        return n | (1 << pos)
class Solution {
    static int setBit(int n) {
        int pos = 0;
        while (((n >> pos) & 1) == 1) {
            pos++;
        }
        return n | (1 << pos);
    }
}

Complexity Analysis

Time Complexity: O(log n)

In the worst case, we scan through all bits of the number before finding an unset bit. A number n has at most ⌊log₂(n)⌋ + 1 bits. For example, if n = 15 (binary 1111), we scan all 4 bits before moving to position 4. With n up to 10^9, we scan at most about 30 bit positions.

Space Complexity: O(1)

We use only a single integer variable pos to track the current bit position, and a mask value. No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force approach works correctly, but it has a loop that iterates through bit positions one at a time. In the worst case — when all existing bits are set (like n = 15 = 1111) — we scan through all log(n) bits before finding the unset position.

The fundamental question is: can we find and set the rightmost unset bit in a single operation, without scanning at all?

Key insight: When you add 1 to any number, the binary addition carries through all the rightmost consecutive 1 bits and flips the first 0 bit to 1. For example, 10101 + 1 = 10110. The carry propagated through bit0 (which was 1), and stopped at bit1 (which was 0, now becomes 1 in n+1). If we then OR the original number with n + 1, we get all the original set bits plus the newly set bit. This gives us a direct O(1) formula: n | (n + 1).

Optimal Approach - Bitwise OR with n + 1

Intuition

The optimal approach uses a beautiful property of binary addition combined with the OR operation.

When you compute n + 1, something very specific happens in binary: the addition carries through all consecutive 1 bits at the rightmost end, flipping them to 0, and then flips the first 0 bit to 1. For example:

  • n = 21 = 10101, n + 1 = 22 = 10110
  • n = 15 = 01111, n + 1 = 16 = 10000
  • n = 6 = 110, n + 1 = 7 = 111

Notice that n + 1 always has the rightmost unset bit of n turned ON. However, it may also have turned OFF some bits that were ON in n (the carry propagation). To keep all original set bits AND also include the newly set bit, we simply OR the two values: n | (n + 1).

Think of it this way: n knows which bits were already ON, and n + 1 knows where the next bit should be set. Combining them with OR merges both pieces of information — you keep everything that was already set and add exactly one new bit.

This works for all cases including when all bits are already set (like n = 15 → 31), because the carry propagates all the way and sets the next higher-order bit.

Step-by-Step Explanation

Let's trace through with n = 21 (binary: 10101):

Step 1: We have n = 21. In binary: 10101. We need to find and set the rightmost 0 bit.

Step 2: Compute n + 1 = 22. In binary: 10110. The addition carried through bit0 (was 1, now 0), and stopped at bit1 (was 0, now 1). Notice bit1 — the rightmost unset bit — is now set in n + 1.

Step 3: Compute n | (n + 1) = 21 | 22. Bit-by-bit OR:

  • bit4: 1 | 1 = 1
  • bit3: 0 | 0 = 0
  • bit2: 1 | 1 = 1
  • bit1: 0 | 1 = 1 ← this is the key bit that changes
  • bit0: 1 | 0 = 1

Step 4: Result = 10111 = 23.

Let's also verify with n = 15 (binary: 01111):

Step 5: n + 1 = 16 = 10000. The carry propagated through all four set bits.

Step 6: n | (n + 1) = 15 | 16 = 01111 | 10000 = 11111 = 31. The next higher-order bit was set correctly.

Result: The formula n | (n + 1) works in all cases with a single operation.

Optimal — n | (n + 1) Sets the Rightmost Unset Bit — Watch how adding 1 to n flips the rightmost unset bit, and OR-ing preserves all original set bits plus the new one. Two examples are shown: n=21 (normal case) and n=15 (all bits set).

Algorithm

  1. Compute n + 1
  2. Compute n | (n + 1)
  3. Return the result

Why it works: Adding 1 to n causes a binary carry that propagates through all consecutive rightmost 1 bits and flips the first 0 bit to 1. The OR with the original n then restores any bits that were turned off by the carry propagation. The net effect is that exactly one bit changes: the rightmost 0 bit becomes 1.

Code

class Solution {
public:
    int setBit(int n) {
        return n | (n + 1);
    }
};
class Solution:
    def setBit(self, n: int) -> int:
        return n | (n + 1)
class Solution {
    static int setBit(int n) {
        return n | (n + 1);
    }
}

Complexity Analysis

Time Complexity: O(1)

The solution performs exactly two operations regardless of the size of the input: one addition (n + 1) and one bitwise OR (n | (n + 1)). Both are single CPU instructions that execute in constant time. Unlike the brute force which scans through up to 30 bits, this approach does zero scanning.

Space Complexity: O(1)

No additional variables or data structures are needed beyond the computation itself. The result is produced directly from the arithmetic expression.