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

1
2
3

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

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

1
2
3
4
5

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

Code

1
2
3
4
5
6
7

class Solution {
 public:
  unsigned int clearRightmostRun(unsigned int x) {
    unsigned int lsb = x & -x;
    return (x + lsb) & x;
  }
};
1
2
3
4
5
6

package main

func clearRightmostRun(x uint32) uint32 {
    lsb := x & -x
    return (x + lsb) & x
}
1
2
3
4
5
6

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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;
  }
}
1
2
3
4
5
6
7
8

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.