Create a word with a single 1-bit at the position of the rightmost 0-bit

Problem

Create a word with a single 1-bit at the position of the rightmost 0-bit in an unsigned word x. If the input is all 1s, the output should be 0.

Examples

Example 1

1
2
3

Input:  x = 0b01011011
Output: 0b00000100
Explanation: the rightmost `0` in `x` (from LSB) is at position 2; result has a single `1` at that position.

Solution

Method 1 – Bit trick: ~x & (x + 1)

Intuition

x + 1 sets the rightmost 0 bit of x to 1 and clears the 1 bits to its right. The complement ~x has 1 where x has 0. AND-ing ~x and (x + 1) leaves a single 1 at the rightmost 0 position and clears other bits. If x is all 1s, (x + 1) overflows to 0 (for fixed-width unsigned words) and the result is 0.

Approach

• Treat x as an unsigned word of width w (machine word or explicit width).
• Compute res = (~x) & (x + 1).
• If using unbounded integers (Python), mask with mask = (1 << w) - 1 to restrict to w bits: res & mask.

Edge cases

• If x has no zero bits (all ones), (x + 1) wraps to 0 and res becomes 0.
• Use unsigned types to avoid undefined or implementation-defined signed behavior in languages like C/C++.

Dry Run

1
2
3
4

x            = 01011011
~x           = 10100100
x + 1        = 01011100
~x | (x + 1) = 00000100

Code

1
2
3
4
5
6

class Solution {
 public:
  unsigned singleOneAtRightmostZero(unsigned x) {
    return (~x) & (x + 1u);
  }
};

1
2
3
4
5

package main

func SingleOneAtRightmostZero(x uint) uint {
    return ^x & (x + 1)
}

1
2
3
4
5

class Solution {
    public int singleOneAtRightmostZero(int x) {
        return (~x) & (x + 1);
    }
}

1
2
3
4

class Solution:
    def single_one_at_rightmost_zero(self, x: int, width: int = 32) -> int:
        mask = (1 << width) - 1
        return ((~x) & (x + 1)) & mask

Complexity

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