Turn off the rightmost contiguous string of 1’s

Problem

Given an integer x, clear (turn off) the rightmost contiguous run of 1 bits and return the resulting integer. For example:

Examples

Example 1

Input: x = 0b01011100
Output: 0b01000000
Explanation: the rightmost contiguous run `111` is cleared.

Solution

Method 1 — Arithmetic trick: ((x & -x) + x) & x (recommended)

Intuition

lsb = x & -x isolates the least-significant set bit. Adding lsb to x propagates a carry through the trailing 1-run and clears that run, while setting the bit immediately left of the run. AND-ing the sum with the original x clears that newly set bit and leaves higher bits intact, resulting in the rightmost contiguous 1-run turned off.

Approach

• Compute lsb = x & -x (isolate least-significant set bit).
• Compute y = x + lsb.
• Return result = y & x (this clears the rightmost contiguous run of 1s).
• Works for unsigned integers; be mindful of signed/unsigned semantics in some languages.

Example

x =  0101 1100
-x =  1010 0100
x & -x = 0000 0100  (lsb)
x + lsb = 0110 0000
(x + lsb) & x = 0100 0000

Code

C++

class Solution {
 public:
  unsigned int clearRightmostRun(unsigned int x) {
    unsigned int lsb = x & -x;
    return (x + lsb) & x;
  }
};

Go

package main

func clearRightmostRun(x uint32) uint32 {
    lsb := x & -x
    return (x + lsb) & x
}

Java

class Solution {
  public int clearRightmostRun(int x) {
    int lsb = x & -x;
    return (x + lsb) & x;
  }
}

Python

class Solution:
    def clear_rightmost_run(self, x: int) -> int:
        lsb = x & -x
        return (x + lsb) & x

Complexity

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

Method 2 — Explicit loop: clear trailing ones one-by-one (alternate)

Intuition

If you repeatedly remove the least-significant set bit while it remains adjacent to the rightmost run, you clear the whole contiguous run. This is simple and explicit but costs proportional to the run length.

Approach

• While the least-significant bit of x is 1 (or while the rightmost set bit remains at the same or lower position), clear it using x = x & (x - 1).
• Stop when the bit immediately right of the current position is zero.

Detailed steps (one common implementation):

1. Let lsb = x & -x.
2. While x & lsb != 0:
   • Set x = x & (x - 1) to clear that rightmost 1.
   • Update lsb = x & -x if desired, or continue checking the trailing bit.
3. Return x.

This clears the contiguous trailing 1s starting from the least-significant set bit.

Code

C++

class Solution {
 public:
  unsigned int clearRightmostRunLoop(unsigned int x) {
    if (x == 0) return 0u;
    unsigned int lsb = x & -x;
    while ((x & lsb) != 0u) {
      x = x & (x - 1u);
    }
    return x;
  }
};

Go

package main

func clearRightmostRunLoop(x uint32) uint32 {
    if x == 0 { return 0 }
    lsb := x & -x
    for (x & lsb) != 0 {
        x = x & (x - 1)
    }
    return x
}

Java

class Solution {
  public int clearRightmostRunLoop(int x) {
    if (x == 0) return 0;
    int lsb = x & -x;
    while ((x & lsb) != 0) {
      x = x & (x - 1);
    }
    return x;
  }
}

Python

class Solution:
    def clear_rightmost_run_loop(self, x: int) -> int:
        if x == 0:
            return 0
        lsb = x & -x
        while (x & lsb) != 0:
            x = x & (x - 1)
        return x

Complexity

• ⏰ Time complexity: O(k), where k is the length of the rightmost contiguous 1-run (number of trailing ones cleared).
• 🧺 Space complexity: O(1).

Notes

• Method 1 is constant-time and preferred. Method 2 is instructive and shows the explicit process; use it if you need to operate per-bit.
• The formula relies on two's-complement arithmetic for -x and is standard in bit manipulation practice. Original reference is preserved in source_links.