Turn on the rightmost 0-bit

Problem

Given an integer x, set (turn on) the rightmost 0 bit (least-significant zero) and return the resulting value. If there is no 0 bit in the relevant word width, the value remains unchanged.

Examples

Example 1

Input: x = 0b10100011
Output: 0b10100111
Explanation: the rightmost zero is turned into 1.

More examples

Input: x = 0b10111100  => Output: 0b10111101
Input: x = 0b01110111  => Output: 0b01111111
Input: x = 0b00000001  => Output: 0b00000011
Input: x = 0b11111111  => Output: 0b11111111 (no zero to set)

Solution

Method 1 — x | (x + 1) (recommended)

Intuition

Adding 1 to x fills the first (rightmost) zero bit and zeroes all lower bits. OR-ing x with x+1 therefore sets that zero without clearing any other set bits. If x has no zero in the considered width, x+1 may overflow and the OR leaves x unchanged.

Approach

• Compute result = x | (x + 1).
• Handle signedness/width concerns depending on the language: mask to the intended bit-width if necessary.

Code

C++

class Solution {
 public:
    unsigned int turnOnRightmostZero(unsigned int x) {
        return x | (x + 1u);
    }
};

Go

package main

func turnOnRightmostZero(x uint32) uint32 {
        return x | (x + 1)
}

Java

class Solution {
    public int turnOnRightmostZero(int x) {
        return x | (x + 1);
    }
}

Python

class Solution:
        def turn_on_rightmost_zero(self, x: int) -> int:
                return x | (x + 1)

Complexity

• ⏰ Time complexity: O(1), constant-time arithmetic and bitwise operations.
• 🧺 Space complexity: O(1).

Method 2 — Explicit scan (alternate)

Intuition

Find the index of the rightmost zero and set it explicitly with a mask. This is explicit and safe across languages where overflow behavior is a concern.

Approach

• Iterate bit positions i = 0..(w-1) (where w is the word width) and check (x >> i) & 1.
• When a zero is found, return x | (1 << i).
• If no zero is found, return x.

Code

C++

class Solution {
 public:
    unsigned int turnOnRightmostZeroScan(unsigned int x, unsigned int width=32) {
        for (unsigned int i = 0; i < width; ++i) {
            if (((x >> i) & 1u) == 0u) return x | (1u << i);
        }
        return x;
    }
};

Go

package main

func turnOnRightmostZeroScan(x uint32, width uint) uint32 {
        for i := uint(0); i < width; i++ {
                if ((x >> i) & 1) == 0 {
                        return x | (1 << i)
                }
        }
        return x
}

Java

class Solution {
    public int turnOnRightmostZeroScan(int x, int width) {
        for (int i = 0; i < width; ++i) {
            if (((x >> i) & 1) == 0) return x | (1 << i);
        }
        return x;
    }
}

Python

class Solution:
        def turn_on_rightmost_zero_scan(self, x: int, width: int = 32) -> int:
                for i in range(width):
                        if ((x >> i) & 1) == 0:
                                return x | (1 << i)
                return x

Complexity

• ⏰ Time complexity: O(w), where w is the word width in bits (e.g., 32 or 64) — worst-case scans all bits.
• 🧺 Space complexity: O(1).

Notes

• Method 1 is constant-time and preferred. Method 2 is safer in environments where overflow or undefined behavior for x+1 could be an issue, or when you explicitly want to control word width.